2 의 15승 더하기 1 이 11로 나누어 지는지가 궁금 하기도 하나요?

문제) 2^15 + 1 이 11의 배수임을 증명하라.

풀이 1) 합동 산술(合同算術 modular arithmetic) 이용

2^4 ㅌ 5 ( mod 11 ) 이고
2^8 ㅌ 5^2 ㅌ 3 ( mod 11 ) 이다.
따라서 2^15 ㅌ 2^4 . 2^8 . 2^3 ㅌ 5 . 3 . 2^3 ㅌ -1 ( mod 11) 이다.
따라서 2^15 + 1 ㅌ -1 + 1 ㅌ 0 (mod 11 )이다.
고로 2^15 + 1 이 11 로 나누어 떨어진다.
<KMO Bible p 2.1>

modular arithmatics을 다르게 표현하면 다음과 같다.
2의 4승 16은   11로 나누면 5가 남고
2의 8승 256은 11로 나누면 3이 남고
2의 15승은 2의 4승 곱하기 2의 8승 곱하기 2의 3승이니까
나머지는 5 *3 *8=120
 120 나누기 11은 몫 10과 나머지 10  이다.
2의 15승이 11로 나누면 10이 남으니까 1을 더하면 11로 나누어 떨어진다.
2^15 + 1 이 11 의 배수다.

설명 )
2의 15승 은 2를 15번곱하면   32768 이다.
2978 * 11 = 32758
32768 = 2^15 = 2978 * 11 + 10
2^15 +1 = 2978 * 11 + 10 + 1 = 2979 * 11 = 32769
32769 / 11 = 2979
나누어 떨어진다.

풀이 2) 인수분해 이용

x3+y3=(x+y)(x2-xy+y2)
2^15 + 1 =  (2^5)^3  + 1^3
             =  ( 2^5 + 1 )*(                  )
             =  (32 +1) * (                )
             = 33 * (                )
             = 3 * 11 * (               )
 11 곱하기 뭐니까 11의 배수 이군요.

풀이 3 )한국주니어수학올림피아드 대상

(Korean Junior Mathematical Olympiad, KJMO)

2를 15번 곱한수는 

2를 4번씩 곱한걸 3번 반복하고 다시 2를 3번 곱하면된다.

2의 15승은 2의 4승 곱하기 2의 4승 곱하기 2의 4승 곱하기 2의 3승 이다.

2를 4번곱한 16을 연속해서 3번 곱하면 16 * 16 *16 = 4096

2의 3승은 8

4096 * 8 =32768

32768 +1 =  32769

32769 나누기 11은 2979로 나머지가 영으로 11의 배수이다.

2를 15번 곱하고 1을 더한수를 11로 나누면 나머지 없이 딱 떨어지니 11의 배수다.

 증명종료
Q.E.D. 証明終了

또다르게 풀수 있으면 댓글 부탁 합니다.

문의 010- 3549- 5206