페르마의 작은 정리

어떻게 Fermat's Little Theorem을 사용하여 다음을 계산합니까?페르마의 작은 정리

2^1,000,006 mod 101 
2^-1,000,005 mod 11

2009-05-19 jinsungy

일반 숙제 문제를 게시하는 대신 문제 해결 방법과 정보를 추가 할 수 있습니다. – sth

질문의 타당성을 위해 Upvoted. 핵심 프로세스를 이해하지 못한다면이 문제를 "시작"할 방법이 없습니다. 개략적으로 두 단계이므로 어떻게 시작했는지 설명하십시오. –

두 번째 방정식에 음수 기호가있는 이유는 무엇입니까? 누군가 제발 설명해, 그건 나에게 이해가되지 않습니다. – Unknown

당신이 알고있는^(P-1) === 1 모드 P, 그래서 ...

2^10 === 1 개 모드 11
2^(- 1000005) = 2^(- 1,000,000) * 2^- (- 5) = 1 * 2^(- 5) = 2^(- 5) * 2^(10) = 32 mod 11 = -1 = 10

, 더 큰 숫자를 처리하는 방법을 볼 수 있습니까? 과정은 동일합니다.

그것은 모두 FLT입니다. 나는 엉망이 됐어.^

2009-05-19 23:36:21

2^-5 === 2^6 (mod 11). –

그래, 분명히이 오류 (또는 적어도 나쁜 표기)에 오류가 있습니다. 시정이 필요하지만 어디서부터 시작해야할지 모르겠습니다. – Noldorin

그러면 2^1,000,006 mod 101 ... 2^1,000,000 * 2^6 = 1 * 32 = 32 mod 101 = -5? – jinsungy

101 이후

및 (11)는, 소수이다 (각각)^100 2^10 (2)는 2^(100) 및 (2)의 조건에서 2^1,000,006을 표현하는 1 개 모드 (101) 및 제

시도 합동 2^10의 관점에서 -1000005입니다. 각 문제를 계산하기 쉬운 것으로 줄일 수 있어야합니다.

2009-05-19 23:37:18

이것은 갈 길이 될 것 같습니다. 또한, 그것은 단지 OP를 안내하므로 좋은 대답입니다. – Noldorin

답변