2019년 8월 1일 목요일

p가 7 이상의 소수일때, 11...1 ( p - 1 개의 1 ) 는 P의 배수임을 증명하시오. 페르마의 작은 정리

111...11
 ( p - 1 개의 1 ) 는  P의 배수임을 증명하시오
p가  7 이상의 소수일때

풀이

11...1 ( p - 1 개의 1 ) = 99...9 / 9
11...1 = ( 100...0 - 1 ) / 9 =  {10 ^ (p-1) -1 } / 9
이고, gcd(10,P) = 1 이므로, 페르마의 작은 정리 에 의하여  
10 ^ (p - 1) ㅌ 1 ( mod p) 이다.
따라서 11...1 ( p - 1 개의 1 ) 는  P의 배수이다.

<KMO BIBLE 정수론 4.14>

설명

문제해설

예1) 111111 = 7 * 15873

1 이 6개 있으니 소수 7의 배수

예2)  1111111111 ( 1이 10개 ) : 11 의 배수 인지?

1111111111 = 101010101 * 11 이니
1 이 10개 있는 수는 소수인 11의 배수 이군요.

7 이상의 소수 7,11,13,17,19,23....
1 이 22 개 있으면 23 의 배수...

모든 소수가 다 성립해야 증명되 었다 라고 할수있는데 난감하군요.
좋은 방법이 아니군요.
다른 방법을 찾아봐야 겠네요.

Fermat 페르마의 작은 정리 를 이용하면 간단히 증명되는데
한번 살펴 볼까요.

p 소수이고, a가 정수일 필요는 없고 p와 서로소이면 성립한다. 
페르마의 소정리에 따르면, 법 p에서 a^{p} a는 서로 합동이다.
a^{p}\equiv a{\pmod  p}
위 식은 p\mid a일 때 자명하게 성립한다. 만약 {\displaystyle p\nmid a}일 경우, 양변을 약분하여 다음과 같이 쓸 수 있다.

a^{{p-1}}\equiv 1{\pmod  p}\qquad (a\neq 0)



a = 10 이면  10 ^ p-1 ㅌ 1 ( mod P )
위의 ​페르마의 소정리 식은 P 가 소수이고


10의 p - 1 승을  p 로 나누면 나머지가 1이 남는다는 것을 말한다.
​가장 간단한 111111 이 7 로 나누어 지는지 살펴 보자.
​111111 = 999999/9 이다
999999 = 1000000 -1 이다.​
그래서 111111 = ( 1000000 -1 ) /9 이다.
111111 =  ( 10 ^ 6 - 1​ ) / 9 이다.
 페르마의 소정리 에 의해 10 의 6 승은 7로 나누면 나머지가 1 이다.
1 - 1 은 0 이니까 111111 은 7로 나누어 떨어지는 7의 배수다.

일반적으로 11...1 = ( 100...0 - 1 ) / 9 =  {10 ^ (p-1) -1 } / 9
인데 10의 p - 1 승은  p 로 나누면 나머지가 1 이다.



1 에서 1을 빼니, 0 이고 11...1 은 소수 p로  나누어 지고 p 의 배수라고 할수있다.

궁금한게 있으면 문의 하세요
010-3549-5206 으로

댓글 없음: