[대학교이상] 정수론 질문

[크랑랑크앙랑(skybluepian)]

Carmichael 수의 정의 : gcd(a,n)=1인 모든 정수 a에 대해 a^(n-1)≡1 (mod n)이 성립인데

이 경우에 n이 Carmichael 수이면 gcd(a,n)=1이냐 아니냐에 상관없이 모든 정수 a에 대해 a^n≡a (mod n)이 성립한다는데

이걸 어케 증명할 수 있음?

[크랑랑크앙랑(skybluepian)]

추가) n은 합성수 - dc App

[익명(27.35)]

보통 n이 square free임을 먼저 증명함 p가 소수일 때, n = m × p^k (gcd(m, p) = 1)라고 하고, x가 p^k에서의 primitive root라고 하면 중국인의 나머지 정리에 의해 a = 1 mod m, a = x mod p^k 가 존재하고 a^(n - 1) = x^(n - 1) = 1 mod n를 만족함

[익명(27.35)]

그럼 라그랑주 정리에 의해 phi(p^k) = p^(k - 1)(p - 1) | n - 1인데, n - 1과 n은 서로소라서 k = 1이 될 수 밖에 없고, (p - 1) | (n - 1)를 만족해야 함

[익명(27.35)]

그럼 n의 모든 소수 인수에 대하여 페르마 소정리를 적용해주고 중국인의 나머지 정리 한번 때리면 원하는 결과를 얻을 수 있음

[익명(27.35)]

x^(n - 1) = 1 mod p^k *

[크랑랑크앙랑(skybluepian)]

Burton 교과서에서는 모든 a에 대해 a^n = a (mod n)이 성립한다는 걸 기본전제로 깔고 square-free임을 증명하던데 원래 중간과정이 있구나 ㄱㅅㄱㅅ 읽어볼게 - dc App

[크랑랑크앙랑(skybluepian)]

아 교과서 배치상 primitive root가 더 뒤에 나와서 뺐나보네 - dc App

[익명(1.255)]

square free를 증명하는 다른 방법 n = p^k * m, p: 소수, gcd(p, m) = 1로 썼을 때 어떤 p에 대해 k가 1보다 크다면 k에 대한 귀납법과 오일러 공식으로 gcd(a, p^2) = 1일 때 a^{p^k m - 1} = a^{pm - 1} mod p^2 임을 보일 수 있고 gcd(1 + pm, p^k) = 1, gcd(1 + pm, m) = 1이라서 gcd(1 + pm, n) = 1인데 (1 + pm)^{pm - 1} mod p^2 는 1이 아님: mod p^2를 취하면 1 - pm이고 m은 p의 배수가 아니니까 이는 모순이고 n은 square free primitive root를 안 가져와도 되는 증명이라는 것 이상의 의미는 없는듯함

[크랑랑크앙랑(skybluepian)]

ㄱㅅㄱㅅ 한번 참고해볼게 - dc App