나머지 정리 관련 2019^6을 4042로 나눈 나머지는 어떻게 구하나요? 참고로 답 64가 아니고요,

2019^6을 4042로 나눈 나머지는 어떻게 구하나요? 참고로 답 64가 아니고요, 자세한 설명부탁드려요.

나머지 정리 관련 질문에 대해 여쭤보시는군요.

​

2019의 6제곱(2019^6)을 4042로 나눈 나머지를 구하는 방법은 거듭제곱을 조합법 또는 모듈로 연산을 활용하는 방법으로 계산할 수 있습니다. 일반적으로 큰 수의 나머지 연산은 모듈로 연산의 성질을 이용하는 것이 효율적입니다.

​

우선, 2019를 4042로 나눈 나머지를 구합니다.

2019 < 4042이므로, 2019의 나머지는 2019입니다.

​

이제, 2019^6의 나머지를 구하기 위해 반복적인 곱셈과 모듈로 연산을 활용합니다.

​

1. 2019^1 mod 4042 = 2019

2. 2019^2 mod 4042 = (2019 * 2019) mod 4042

계산:

2019 * 2019 = 2019^2

2019 2019 = (2000 + 19)^2 = 2000^2 + 22000*19 + 19^2

= 4,000,000 + 76,000 + 361 = 4,076,361

이제, 4,076,361 mod 4042를 구합니다.

4042 * 1000 = 4,042,000

차이: 4,076,361 - 4,042,000 = 34,361

다시, 4042 * 8 = 32,336

차이: 34,361 - 32,336 = 2,025

4042 * 0 = 0

차이: 2,025 (이 값이 2019^2 mod 4042의 나머지)

그러므로, 2019^2 mod 4042는 2,025입니다.

3. 2019^3 mod 4042 = (2019^2 * 2019) mod 4042

= (2,025 * 2019) mod 4042

계산:

2,025 2019 = (2000 + 25) (2000 + 19)

= 20002000 + 200019 + 252000 + 2519

= 4,000,000 + 38,000 + 50,000 + 475

= 4,000,000 + 88,000 + 475 = 4,088,475

​

4042 * 1000 = 4,042,000

차이: 4,088,475 - 4,042,000 = 46,475

​

4042 * 10 = 40,420

차이: 46,475 - 40,420 = 6,055

​

4042 * 1 = 4,042

차이: 6,055 - 4,042 = 2,013

​

따라서, 2019^3 mod 4042은 2,013입니다.

​

4. 2019^4 mod 4042 = (2019^3 * 2019) mod 4042

= 2,013 * 2019

​

계산:

2000 + 13 * 2000 + 13 =

2000 * 2000 = 4,000,000

13 * 2000 = 26,000

13 = 13

합계: 4,000,000 + 26,000 + 13 = 4,026,013

​

이제 모듈로 연산:

4042 * 1000 = 4,042,000

차이: 4,026,013 - 4,042,000는 음수이므로, 우리가 초과했음을 알 수 있는데, 이는 잘못된 계산입니다. 다른 방법으로 간단히 계산하면,

​

대신, 작은 수로 계속 계산하는 것이 더 효율적이니, 반복적으로 모듈로 연산을 수행하는 방법이 실용적입니다.

​

좀 더 효율적으로 계산하려면 다음과 같이 이항 제곱법(이진 거듭제곱)을 이용하는 것이 좋습니다.

​

단계별로:

• 2019^1 ≡ 2019 (mod 4042)

• 2019^2 ≡ (2019^1)^2 ≡ 2,025 (mod 4042)

• 201