khb1109   2년 전

제목이 곧 내용입니다.


B진법을 입력받고, D를 각 문자하나하나 입력받은 후 정수로 변환 후 sum이라는 공간에 저장시켰습니다. 그 후 나머지 연산을 하여

문제를 해결은 했는데, 왜 이런 결과가 나오는지 궁금해서 질문드립니다.

chogahui05   2년 전

k*(a^n) mod (a-1) 이 k mod (a-1)과 같다는 것을 보이는 것이군요? (단 0<=k<a) -- (A)

사실 증명이 맞는진 모르겠지만..

(A)가 성립한다면 k*(a^n) - k를 a-1로 나눈 건 0이다 또한 맞군요.

k*(a^n) - k = k(a^n - 1) = k(a-1)(a^(n-1) + ... + 1) = (a-1)Q 꼴로 나타내 지네요.

(a^(n-1) + ... + 1)도 정수, k도 정수네요. A가 정수이고 B도 정수이면 A*B도 정수네요. 여기에 (a-1)이 붙었네요.

(a-1)Q는 a-1로 나눠지네요? Q가 정수니까..

QED.

댓글을 작성하려면 로그인해야 합니다.