수학 나머지 연산 역원(Modular multiplicative inverse)를 알아보겠습니다. ​ 나머지 연산 글에서 나눗셈은 적용되지 않는다는 사실을 알았습니다. https://shwoghk14.blogspot.com/2023/01/modular-arithmetic.html 그래서 우리는 역원을 이용하여 곱셈을 활용해야 합니다. 역원이란 둘을 곱했을 때, 1이 되는 수를 말합니다. 5의 역원은 1/5입니다. 이것을 나머지 연산에 표현하면 이렇게 표현합니다. 나머지 연산의 역원은 다음과 같은 방법으로 구합니다. A^-1 자리에 0~(M-1)까지 숫자를 넣어가면서 1이 되는 것을 찾습니다. ​ ​ 24 mod 11의 역원을 찾아봅시다. 위의 그림에서 6을 곱했을 때 나머지가 1이 나옵니다. 따라서 24 mod 11의 역원은 6이 됩니다. ​ ​ 그럼 위의 나눗셈 식을 다시 해볼까요? 48/24 mod 11을 역원을 이용해서 곱셈 법칙으로 계산 가능합니다. 역원이 존재하기 위해서는 조건이 필요합니다. A와 M이 최대 공약수가 1 인 서로소여야 합니다.  ​ 유클리드 호제법(Euclidean algorithm)을 사용하면 최대 공약수가 1인 것을 쉽게 찾을 수 있습니다. https://shwoghk14.blogspot.com/2019/03/euclidean-algorithm.html 우리가 역원을 찾던 행위를 확장 유클리드 호제법을 사용하면 수식으로 표현할 수 있습니다. 여기서 y가 A^-1이 됩니다. ​ ​ ...

수학 나머지 연산(Modular arithmetic)을 알아보겠습니다. ​ 나머지 연산이란 어떤 숫자를 나누고 남은 나머지를 말합니다. 보통 나눗셈은 몫을 구하는 용도인데요. 나머지 연산은 나머지에 관심을 가져주는 연산입니다. ​ ​ 표현은 아래와 같이 합니다. 24를 11로 나눴을 때 나머지는? 답은 2입니다. 11 * 2 + 2 ​ ​ 아래와 같이 같은 나머지를 가지는 두 나머지 연산이 있습니다. 이 둘은 합동(Congruence)라고 하며, 다음과 같이 표기합니다. 합동 관계는 다음과 같은 특징이 있습니다. a = b + km a - b = km 즉 두 숫자를 뺀 값이 m의 배수가 되면 됩니다. 위의 24 ≡ 35 (mod 11)의 경우 35 - 24 = 11이 되어 1 x 11이 되므로 합동 관계가 맞습니다. ​ ​ 음수에 대한 나머지 연산의 경우 다음과 같이 구합니다. -24보다 큰 11의 배수를 더합니다. 여기선 33이 크네요. 그러면 3*11 - 24 = 9 즉 9 mod 11과 같습니다. ​ 나머지 연산의 산술 특징을 알아봅시다. 두 수의 합 나머지 연산은 각 각의 나머지 연산 더하기 나머지 연산을 한 것과 같습니다. (A + B) mod M = (A mod M + B mod M) mod M ​ 예시 25 mod 11 = (11 mod 11 + 14 mod 11) mod 11 25 mod 11 = 3 (0 + 3) mod 11 = 3 ​ 증명은 다음과 같습니다. ...

수학 조합(Combination)을 알아보겠습니다. ​ 조합은 순서와 상관없이 나올 수 있는 경우의 수를 말합니다. 기호는 다음과 같이 사용합니다. ​ 총 n 개가 있고, 여기서 r 개를 고르는 걸 의미합니다. 이것을 수식으로 쓰면 이렇게 됩니다. 예를 들어 1, 2, 3, 4, 5가 적힌 공을 5 개가 있고, 여기서 3 개를 뽑는 것이라고 한다면 다음과 같이 표현됩니다. 이 경우, 나올 수 있는 경우의 수는 무엇일까요? 10 가지입니다. ​ ​ 조합의 다른 특징은 두 조합의 값이 같다는 것입니다. 이것을 적용해 보면 다음과 같습니다. n 개중 n 개를 뽑는 것과 n 개중 0 개를 뽑는 경우의 수는 1입니다. 순열과의 차이점을 알아볼까요? 아래는 순열의 설명입니다. https://shwoghk14.blogspot.com/2022/12/permutation.html 5 개의 공 중에서 2 개를 뽑는 경우를 생각해 봅시다. 1, 2, 3, 4, 5 ​ 순열 순서를 상관하므로. 20 가지 1, 2 1, 3 1, 4 1, 5 2, 1 2, 3 2, 4 2, 5 3, 1 3, 2 3, 4 3, 5 4, 1 4, 2 4, 3 4, 5 5, 1 5, 2 5, 3 5, 4 조합 순서를 상관하지 않으므로. 10 가지 1, 2 1, 3 1, 4 1, 5 2, 3 2, 4 2, 5 3, 4 3,...

수학 최소공배수, 최대공약수를 알아보겠습니다. ​ 두 수가 있을 때의 경우를 보겠습니다. 최소공배수(Least Common Multiple, LCM)는 각 수의 곱한 것이 서로 만나는 가장 작은 수를 말합니다. 예를 들어 4와 5가 있다고 치면, 4, 8, 12, 16, 20 5, 10, 20 이렇게 두 수는 20에서 만납니다. 4와 5의 최소공배수는 20입니다. ​ 최대공약수(Greatest Common Divisor, GCD)는 두 수가 가진 약수 중에 가장 큰 수를 말합니다. 4의 약수는 1, 2, 4 5의 약수는 1, 5 두 수가 공통으로 가지는 약수 중에 가장 큰 수는 1입니다. 4와 5의 최대공약수는 1입니다. ​ ​ 하나 더 해봅시다. 12와 6이 있습니다. 12 6, 12 12와 6의 최소공배수는 12입니다. ​ 1, 2, 3, 4, 6, 12 1, 2, 3, 6 12와 6의 최대공약수는 6입니다. ​ 이렇게 일일이 하나씩 대조해 보는 게 아니라 계산하는 방법이 존재합니다. 앞에 나와있는 숫자를 곱하면 최대공약수입니다. 2 x 3 = 6 ​ 그리고 앞에 있는 숫자와 밑에 있는 숫자를 모두 곱한 것이 최소공배수입니다. 2 x 3 x 2 x 1 = 12 그런데, 자세히 보면 최대공약수는 최소공배수를 구할 때 들어갑니다. A x B x a x b = 최소 공배수 최대공약수 x 2 x 1 = 최소공배수 ​ 그리고 신기한 것은 12 * 6을 최대공약수와 최소공배수로 표현할 수 있습니다. 12 = A x B x a 6 = A x B x b 12 x 6 = A x B x A x B x a x b 최대공약수 = A x B 최소공배수 = A x B x a x b 12 x 6 = 최대...

수학 순열(Permutation)을 알아보겠습니다. ​ 순열은 순서대로 무엇인가를 뽑는 경우의 수를 나타냅니다. 기호로는 이렇게 표현하는데요. ​ 총 n 개가 있고, 여기서 r 개를 고르는 걸 의미합니다. 이것을 수식으로 쓰면 이렇게 됩니다. 예를 들어 1, 2, 3, 4, 5가 적힌 공 5 개가 있고, 여기서 3 개를 뽑는 것이라고 한다면 다음과 같이 표현됩니다. 이 경우, 나올 수 있는 경우의 수는 무엇일까요? 5 x 4 x 3으로 답은 60입니다. 위의 수식을 사용해서 표현하면 이렇게 되는데요. 결론은 5 x 4 x 3으로 동일합니다. 기억하기에는 이게 더 편한 것 같네요. ​ ​ 만약 똑같은 것이 들어있는 순열이라면 어떻게 구해야 할까요? 5, 5, 3, 3, 2가 적힌 공이 있습니다. 5 개를 꺼낼 때 경우의 수는 어떻게 구할까요? 같은 것이 있는 경우에는 다음과 같은 수식을 사용합니다. 같은 것끼리는 자리를 앞뒤로 변경해도 같기 때문에 나누기합니다. 같은 개수를 분모로 나눕니다. 현재는 5가 2 개, 3이 2 개라서 2!2!로 나눕니다. 답은 30 가지 경우의 수가 있군요. ​ 끝. ​ 카테고리: Math

수학 분산(Variance)과 표준편차(Standard deviation)의 차이를 알아보겠습니다. ​ 분산과 표준편차의 역할은 크게 다르지 않습니다. 데이터가 얼마나 잘 모여있는냐를 알아볼 수 있는 지표입니다. 분산과 표준편차의 역할이 같다면 왜 굳이 두 개를 만들었을까요? ​ 그 이유는 평균과의 단위 차이 때문입니다. ​ 예를 들어 길이 m(미터)가 있습니다. 분산의 경우 제곱을 하기 때문에 단위가 ㎡이 됩니다. ㎡은 여러분도 아시다 싶이 넓이 단위입니다. 하지만, 평균의 경우 길이 단위 m이기 때문에 길이와 넓이는 비교를 할 수가 없죠. 그래서 표준편차가 존재합니다. 표준편차는 m 단위입니다. 분산에 Root(근호)를 씌우기 때문에 넓이 단위가 길이 단위로 변환됩니다. ​ ​ 그래서 우리가 분산과 표준편차가 같은 역할을 하지만 따로 만들게 되었습니다. ​ ​ 끝. 카테고리: Math

수학 표준편차(Standard deviation)에 대해서 알아보겠습니다. ​ 분산을 이용합니다. https://shwoghk14.blogspot.com/2020/03/variance.html 분산에 근호(루트)를 씌웁니다. ​ 예를 들어봅시다. 1, 2, 3, 4, 5가 있습니다. ​ 평균을 구합니다. 15 / 5 = 3 ​ 분산을 구합니다. (1 - 3)^2 + (2 - 3)^2 + (3 - 3) ^2 + (4 - 3)^2 + (5 - 3)^2 = 10 10 / 5 = 2 ( 모분산) 10 / 4 = 2.5 (표본분산) ​ 분산에 근호를 씌웁니다. 모표준편차는 1.41 표본표준편차는 1.58 입니다. ​ 정규분포로 넘어가게 되면, 표준편차가 σ시그마입니다. ​ ​ 끝. 카테고리: Math ​

수학 분산(Variance)에 대해서 알아보겠습니다.​ 분산은 평균으로부터 얼마나 멀리 떨어져 있는지를 알 수 있게 해줍니다. ​ 공식은 다음과 같습니다. ​ 1. 평균을 구합니다. 모든 수의 합 / 모든 개수 = 평균 ​ 2. 개별 수 - 평균을 합니다. ​ 3. 2 번에서 구한 개별 값을 제곱을 합니다. ​ 4. 3 번에서 제곱한 값을 모두 더합니다. ​ 5. 모든 개수의 수로 나눕니다. (모평균은 모든 개수의 수, 표본평균은 모든 개수의 수 - 1) ​ ​ 예를 들어 설명하겠습니다. 1, 2, 3, 4, 5가 있습니다. ​ 1. 평균을 구합니다. (1 + 2 + 3+ 4 + 5) / 5 = 3 ​ 2. 개별 수 - 평균을 합니다. 1 - 3 = -2 2 - 3 = -1 3 - 3 = 0 4 - 3 = 1 5 - 3 = 2 ​ 3. 2 번에서 구한 개별 값을 제곱을 합니다. (-2)^2 = 4 (-1)^2 = 1 0^2 = 0 1^2 = 1 2^2 = 4 ​ 4. 3 번에서 제곱한 값을 모두 더합니다. 4 + 1 + 0 + 1 + 4 = 10 ​ 5. 모든 개수의 수로 나눕니다. 10 / 5 = 2 (모분산) 10 / (5 - 1) = 2.5 (표본분산) ​ 끝. 카테고리: Math

수학 평균(Mean)에 대해서 알아보겠습니다. ​ 평균은 수들은 중간 값을 구할 수 있습니다. 공식은 다음과 같습니다. 모든 항목의 합 / 모든 항목의 수 ​ 예를 들어보겠습니다. 1, 2, 3, 4, 5가 있다면, 1+2+3+4+5(모든 항목의 합) / 5(모든 항목의 수) 15/5 = 3 평균은 3이 됩니다. ​ 끝. 카테고리: Math

원시근(Primitive root modulo n)에 대해서 알아보겠습니다. φ(n)의 집합 A가 있고, 원소로는 {a, b, c, d}를 포함하고 있을 때, a부터 d까지 차례로 원소 값 하나씩 거듭제곱하여(a, a², a³, ...) 양의 정수 n으로 나눴을 때, 나머지가 집합 A의 원소 값{a, b, c, d}을 전부 포함하고 있는 원소 값을 찾습니다. 만약 원소 b가 φ(n)의 값을 모두 가지게 된다면, b는 n의 원시근이 됩니다. ​ 예시를 들어보겠습니다. A = φ(5) = {1, 2, 3, 4} ​ ​ 1 (mod 5) = 1, 1 (mod 5) = 1 ..... 결과가 {1} 2( mod 5) = 2, 4 (mod 5) = 4, 8 (mod 5) = 3, 16 (mod 5) = 1, ... 결과가 {1, 2, 3, 4} (원시근) 3 (mod 5) = 3, 9 (mod 5) = 4, 27 (mod 5) = 2, 81 (mod 5) = 1, ... 결과가 {1, 2, 3, 4} (원시근) 4 (mod 5) = 4, 16 (mod 5) = 1, 64 (mod 5) = 4, ... 결과가 {1, 4} ​ 2와 3만이 φ(5) 원소 {1, 2, 3, 4}가 나옵니다. 따라서, 2와 3은 5의 원시근입니다. ​ 끝. 카테고리: Math

나머지(modulo)에 대해서 알아보겠습니다. 나머지는 어떤 수를 나누었을 때, 남는 값을 나타냅니다. ​ 일반적인 나누기는 몫을 나타냅니다. 14 ÷ 8 = 1.75 ​ 나머지 표현은 다음과 같이 합니다. 14 (mod 8) = 6 또는 14 ≡ 6 (mod 8) ​ Modulo의 우리나라 용어는 법(法)이 있습니다. 법 8에 대한 14의 값은 6이다. 6과 14는 법 8에 대해 합동이다. 끝. 카테고리: Math

서로소(Coprime)에 대해서 알아보겠습니다. 서로소는 양의 두 정수의 관계를 나타내는 말입니다. 양의 정수 n과 양의 정수 m이 있습니다. n과 m의 최대 공약수(Greatest Common Divisor)가 1인 경우 서로소가 됩니다. ​ 예시로 알아봅시다. 양의 정수 n을 14, 양의 정수 m을 15로 정합니다. 14의 약수는 1, 2, 7, 14 ​ 15의 약수는 1, 3, 5, 15 ​ 14와 15, 모두에 속한 가장 큰 약수는 1이 됩니다. 따라서 14와 15는 서로소가 됩니다. 끝. 카테고리: Math

오늘은 오일러 파이 함수(Euler's phi(totient) function)에 대해서 알아보겠습니다. φ()로 나타냅니다. ​ 오일러 파이 함수는 임의의 양의 정수 n을 1부터 n까지 숫자와 서로소 비교를 하여 구한 서로소 개수입니다. ​ 예제를 들어 쉽게 말하면, 임의의 양의 정수 n을 5로 정해봅시다. 표현은 φ(5)로 나타냅니다. ​ 5와 1은 서로소입니다. 5와 2는 서로소입니다. 5와 3은 서로소입니다. 5와 4는 서로소입니다. 5와 5는 서로소가 아닙니다. ​ φ(5) = 4가 됩니다. 끝. 카테고리: Math

유클리드 호제법에 대해서 알아보겠습니다. 유클리드 호제법을 사용하면, 최대 공약수(Greatest common factor)를 쉽게 구할 수 있습니다. ​ G(a, b) = G(b, r) 여기서 r는 a/b의 나머지 ​ 1024와 54로 예를 들어보겠습니다. G(1024, 54) = G(54, 52) = G(52, 2) = G(2, 0) = 2 즉, 1024와 54의 최대 공약수는 2입니다. ​ 1024 = 1, 2, 4, 8, 16, 32, 64, 128, ,256, 512, 1024 54 = 1, 2, 3, 6, 9, 18, 27, 54 ​ ​ 증명은 아래와 같습니다. ​ G(a, b)를 a와 b의 최대 공약수로 정의를 내립니다. ​ 유클리드 호제법은 a와 b가 정수(Ζ)이고, 조건 a ≥ b, b > r ≥ 0를 만족할 때, a = bq + r가 성립됩니다. 이때, G(a, b) = G(b, r)을 나타내고 있습니다. 끝. 카테고리: Math