정리 5.1 해설

[전공만점80]

안녕하세요 여기서 교수님께서 예를 드실 때 ka=pq+r로 말씀하시면서 k가 1부터 p-1까지의 수라서 p와 서로소라 하셨는데 서로소가 아닐 수도 있는거 아닌가요? 예를들어 p=6과 k=4를 비교하면 어떻게 되는건가요?

그리고 교수님께서  일반적으로 a합동b (mod n)에서 ac합동 bc (mod n)를 계산할 때 mod에 따로 곱하진 않으셨는데 ac합동bc (mod n) 에서 a합동b (mod n/gcd(c,n))을 알려주고 나신 후 부터는 곱셈계산 이후에 역으로 나눗셈을 해보시면서 mod n/gcd(c,n)을 고려해보시던데 정리 4.2 에서는 따로 mod계산을 고려하지 않는것 같습니다. 일반적으로 a합동b (mod n)에서 ac합동 bc (mod n)를 계산할때도 mod n/gcd(c,n)를 고려해야하는건가요?

[Printemps]

(ⅰ) p는 소수입니다. 따라서 1부터 p-1은 p와 서로소입니다.(6은 소수가 아니므로 적절한 예가 될 수 없습니다.)
(ⅱ) 네, 고려해야합니다.