A.6 · Congruences, divisibility and arithmetic functions

학부 GRE 준비. 검토된 ETS 범위 내의 로컬 목표; 이는 공식 시험이나 점수 예측기가 아닌 독자적 교육 과정입니다.

선행지식: 유클리드 알고리즘, 소인수 및 연산 arithmetic.

• 최대공약수 조건을 사용하여 선형 동치식 풀이
• 서로소 동치식들을 중국 여남정리에 결합하라
• Euler 정리 역원ABLE 잔차에만 적용하십시오
• 소수 지수 분해 가능성을 이용해 최소 허용 정수 구하기

동치식: 나눗셈의 나머지가 같아, 두 수의 차가 나눗수로 나누어질 때 성립하는 등식.

토이엔트(totient): 양수 정수 모듈러스와 서로 소인 잔차의 개수입니다.

방정식 ax≡b (mod n)은 d=gcd(a,n)이 b를 나눌 때만 해가 존재합니다. 그렇다면 a, b, n을 d로 나누어 역원ABLE 계수를 갖는 방정식을 얻습니다. 이는 n/d modulo에서 하나의 잔차 해를 가지며, n modulo에서 d개의 서로 다른 해를 가집니다. 계수만 나누고 원래 모듈러스를 유지하면 일반적으로 해를 잃습니다. 소인분해는 또 다른 나뉘임 도구를 제공합니다: n^k가 소수 거듭제곱의 곱 p^a로 나뉘어야 할 때, n의 각 소수 지수는 ceil(a/k) 이상이어야 합니다. 이러한 최소 지수들은 독립적으로 가장 작은 양수 허용 가능한 n을 만듭니다. n⁴이 2⁷·3⁵로 나뉘려면, n은 2²과 3²을 포함해야 하므로 최소값은 36입니다. 이는 modular 나눗셈으로 해결되는 동치식이 아닌 소수 지수 조건입니다.

확장 유클리드 알고리즘은 gcd(a,n)을 ua+vn 형태로 표현한다. 만약 gcd가 1이라면, u는 a의 나눗수 n에 대한 역원이다. 환원 후 요구된 범위 내 대표자를 선택한다. 7과 26에 대해, 1=15·7−4·26이므로, 15은 7의 나눗수 26에 대한 역원이다; 부호 오류를 잡기 위해 곱을 확인하라.

For coprime positive moduli m,n, the Chinese remainder theorem gives exactly one solution modulo mn for each pair of residue conditions. Substitute x=r+mk into the second congruence and solve for k. If the moduli are not coprime, their residue values must agree modulo gcd(m,n); when consistent, uniqueness is modulo the least common multiple, not the product.

Euler 토이엔트 phi(n)은 n과 서로 소인 잔차를 세합니다. 서로 다른 소수 약수 p에 대해, phi(n)=n times the product of (1−1/p)입니다. Euler 정리에 따르면 gcd(a,n)=1일 때만 a^phi(n)≡1이 성립합니다. 소수인 경우는 Fermat's little theorem입니다. 이 조건을 확인한 후에만 지수를 줄이십시오; 비단위원은 반복적인 거듭제곱 아래에서 영이 될 수 있습니다.

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입니다.

식 a^phi(n)≡1은 임의의 a에 대해 거짓입니다. 예를 들어, 2는 modulo 8에서 역원이 아니며, 2^4는 modulo 8에서 0입니다.

$8x\equiv12\pmod{20}$를 완전히 풉니다. modulo 20에서의 7의 역원을 찾으십시오. 왜 오일러 정리를 사용하여 modulo 20에서 $2^8$을 1로 교체할 수 없는지 설명하십시오.

풀이 과정

최대공약수는 4이며 12을 나눕니다. 세 수를 모두 나누면 $2x\equiv3\pmod5$이 되므로 $x\equiv4\pmod5$입니다. modulo 20에서 네 가지 답은 $4,9,14,19$이며, 대입 시 매번 나머지가 12입니다. $7\cdot3=21$이므로, 7의 역원은 3입니다. 비록 $\phi(20)=8$이라 하더라도, 오일러 정리에는 단위가 필요합니다. 2과 20의 최대공약수는 2이며, 이는 $2^8=256\equiv16$이지 1이 아닙니다.

$x\equiv2\pmod6$, $x\equiv5\pmod9$을 풀거나 불일치를 증명하라. 유일성을 위한 나눗수를 명시하라. $2^5\cdot3^7$이 $n^3$을 나눌 수 있는 최소 양수 n을 구하라.

시도 후 확인

잔류는 최대공약수 셋에 대해 일치한다. $x=2+6k$을 배치: 그러면 $6k\equiv3\pmod9$, 따라서 $2k\equiv1\pmod3$과 $k\equiv2\pmod3$. 따라서 $x\equiv14\pmod{18}$. 나눗수는 최소공배수이며, 54이 아니다. 분해 가능 문제에 대해, n의 소수 지수를 쓰라. 이들은 $3a\ge5$, $3b\ge7$을 만족해야 하므로, $a\ge2$, $b\ge3$이다. 최소 n은 $2^2\cdot3^3=108$이며, 다른 소수 인자는 이를 증가시킬 뿐이다.