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 으로
댓글 없음:
댓글 쓰기