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 페르마의 작은 정리 를 이용하면 간단히 증명되는데
한번 살펴 볼까요.

가 소수이고, <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle a}"><semantics><annotation encoding="application/x-tex">{\displaystyle a}</annotation></semantics></math>가 정수일 필요는 없고 <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle p}"><semantics><annotation encoding="application/x-tex">{\displaystyle p}</annotation></semantics></math>와 서로소이면 성립한다. 

​페르마의 소정리에 따르면, 법 <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle p}"><semantics><annotation encoding="application/x-tex">{\displaystyle p}</annotation></semantics></math>에서 <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle a^{p}}"><semantics><annotation encoding="application/x-tex">{\displaystyle a^{p}}</annotation></semantics></math>와 <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle a}"><semantics><annotation encoding="application/x-tex">{\displaystyle a}</annotation></semantics></math>는 서로 합동이다.

<math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle a^{p}\equiv a{\pmod {p}}}"><semantics><annotation encoding="application/x-tex">{\displaystyle a^{p}\equiv a{\pmod {p}}}</annotation></semantics></math>

위 식은 <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle p\mid a}"><semantics><annotation encoding="application/x-tex">{\displaystyle p\mid a}</annotation></semantics></math>일 때 자명하게 성립한다. 만약 <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle p\nmid a}"><semantics><annotation encoding="application/x-tex">{\displaystyle p\nmid a}</annotation></semantics></math>일 경우, 양변을 약분하여 다음과 같이 쓸 수 있다.

<math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle a^{p-1}\equiv 1{\pmod {p}}\qquad (a\neq 0)}"><semantics><annotation encoding="application/x-tex">{\displaystyle a^{p-1}\equiv 1{\pmod {p}}\qquad (a\neq 0)}</annotation></semantics></math>

​

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 으로