동余, divisibility 및 산술 함수
도입됨| English | 의미 |
|---|---|
| congruence/ˈkɒŋɡruːəns/ | 동치류 |
| totient/ˈtəʊʃənt/ | 오일러 함수 |
답에 앞서 결정하기
- 한 기계가 4분마다 한 사이클을, 다른 기계가 7분마다 한 사이클을 반복합니다. 동시 위치(simultaneous position)는 소수점 근사가 아닌 동余 문제(congruence problem)입니다.
- 목표: 최대공약수(gcd) 조건을 사용하여 선형 동余방정식을 풀이하는 것입니다.
관계 파악하기
- 방정식 ax≡b (mod n)는 d=gcd(a,n)가 b를 나눌 때만 해를 가집니다. 만약 그렇다면 a, b, n을 d로 나누어 가역 계수를 갖는 방정식을 얻으십시오. 이는 n/d 위에서 하나의 잔류 해를 가지며, n 위에서 d개의 서로 다른 해를 가집니다. 계수는 나누되 원래의 항등식(modulus)을 유지하면 일반적으로 해가 잃어질 수 있습니다. 소인수분해는 또 다른 나눈 도구입니다: n^k가 소인수의 제곱 product p^a에 의해 나어야 할 때, n의 각 소인수 지수는 ceil(a/k) 이상이어야 합니다. 이러한 최소 지수들은 독립적으로 가장 작은 양의 허용 가능한 n을 결정합니다. n⁴이 2⁷·3⁵에 의해 나뉘려면, n은 2²과 3²을 포함해야 하므로, 최소값은 36입니다. 이는 동余Division으로 푸는 문제가 아니라 소인수 지수 조건입니다.
- 서로소인 동余방정식을 중국여남정리(Chinese remainder theorem)와 결합하십시오.
How many distinct solutions modulo 18 satisfy 6x≡12?
난이도 1/5 · 100 코인 + 오늘 첫 완료 시 소액 보너스
gcd(6,18)=6 divides 12, so there are six solutions; after dividing the modulus too, x≡2 modulo 3.
정의 규칙 활용하기
- 확장 유클리드 알고리즘은 gcd(a,n)를 ua+vn 형태로 표현합니다. 만약 gcd가 1이라면, u는 n modulo a의 역수(inverse)입니다. 환원 후 필요한 범위 내의 대표원을 선택하십시오. 7과 26의 경우, 1=15·7−4·26이므로, 15는 7 modulo 26의 역수입니다. 부호 오류를 잡기 위해 곱을 확인하십시오.
- 오일러 정리는 가역 잔류(invertible residues)에만 적용하십시오.
What is the least nonnegative x with x≡1 modulo 3 and x≡2 modulo 5?
난이도 1/5 · 100 코인 + 오늘 첫 완료 시 소액 보너스
Among 1,4,7,10,13 modulo 15, only 7 has residue 2 modulo 5.
조건 확인
- 서로소인 양의 합동수 m, n에 대해 중국 여정정리는 각 쌍의 잔차 조건에 대해 합동수 mn에 대해 정확히 하나의 해를 제공한다. x=r+mk를 두 번째 합동식에 대입하여 k에 대해 풀라. 합동수가 서로소가 아니면, 그 잔차 값들은 gcd(m,n)에 대해 일치해야 합니다; 일관될 경우, uniqueness는 곱이 아닌 최소공배수에 따라 결정됩니다.
- 소수 지수 나눈임을 사용하여 허용 가능한 최소 정수를 찾으십시오.
6x≡9 modulo 15를 풀라. gcd는 3이며 9을 나눕니다. 세 수치를 모두 나누어 2x≡3 modulo 5를 얻습니다; 2의 역수는 3이므로, x≡9≡4 modulo 5입니다. 원본의 합동수 15에 대한 해는 4,9,14입니다. x≡2 modulo 4이고 x≡3 modulo 7일 때, x=2+4k로 씁니다; 그러면 4k≡1 modulo 7이 되어, k≡2을 줍니다. 따라서 x≡10 modulo 28입니다.
phi(12) equals ____.
난이도 1/5 · 100 코인 + 오늘 첫 완료 시 소액 보너스
The coprime residues are 1,5,7,11, or use 12(1−1/2)(1−1/3)=4.
문제 형식 적용하기
- 오일러의 토이엔트 phi(n)은 n과 서로소인 잔차의 개수를 세합니다. 서로 다른 소수 약수 p에 대해, phi(n)=n times the product of (1−1/p)입니다. 오일러의 정리(a^phi(n)≡1)는 gcd(a,n)=1일 때만 성립합니다. 소수의 경우는 페르마의 소정리입니다. 이 조건을 확인한 후 지수만 줄이십시오; 비단위원은 반복된 거듭제곱 하에서 0이 될 수 있습니다.
- 소수 지수 나눈임을 사용하여 허용 가능한 최소 정수를 찾으십시오.
식 a^phi(n)≡1은 임의의 a에 대해 거짓입니다. 예를 들어, 2는 modulo 8에서 역원이 아니며, 2^4는 modulo 8에서 0입니다.
다음 중 이 사례에 부합하는 답안은 무엇입니까?
최대공약수 조건을 이용하여 선형 동余방정식을 풀다
x≡0 modulo 4 and x≡1 modulo 6 have a simultaneous solution.
난이도 1/5 · 100 코인 + 오늘 첫 완료 시 소액 보너스
The first condition makes x even, the second makes it odd; residues disagree modulo gcd(4,6)=2.
구분을 유지하기
- 합동성 — 합동수가 차이를 나누기 때문에 잔차의 등가임.
- 토이엔트 — 양의 합동수 modulus와 서로소인 잔차의 개수.
- gcd 조건을 사용하여 선형 합동식을 푼다.
- 서로소인 동余방정식을 중국여남정리(Chinese remainder theorem)와 결합하십시오.
- 오일러 정리는 가역 잔류(invertible residues)에만 적용하십시오.
- 소수 지수 나눈임을 사용하여 허용 가능한 최소 정수를 찾으십시오.
Match each term with its precise meaning in this lesson.
난이도 2/5 · 140 코인 + 오늘 첫 완료 시 소액 보너스
Keep the distinctions stated in the teaching example.
Put this lesson’s reasoning or event sequence in order.
난이도 3/5 · 200 코인 + 오늘 첫 완료 시 소액 보너스
The order follows the stated process; check each stage before the next.