Mathematics desk
< October 11	<< Sep \| Oct \| Nov >>	October 13 >

Welcome to the Wikipedia Mathematics Reference Desk Archives
The page you are currently viewing is an archive page. While you can leave answers for any questions shown below, please ask new questions on one of the current reference desk pages.

October 12

Congruence question

How could it be proven that if p is a prime number and n an integer such that 2^n-1 ≡ 1 (mod n) with p²| n implies 2^p-1 ≡ 1 (mod p²)? I understand that from p² | n it follows that 2^n-1 ≡ 1 (mod p²), but how does 2^p-1 ≡ 1 (mod p²) follow from that? --Toshio Yamaguchi (tlk−ctb) 09:04, 12 October 2012 (UTC)[reply]

Ah, n-1 is divisible by the multiplicative order of 2 modulo p². -- Toshio Yamaguchi (tlk−ctb) 10:06, 12 October 2012 (UTC)[reply]

Okay, then I have a follow up question: How do I know that p-1 is a multiple of ord_p² 2? -- Toshio Yamaguchi (tlk−ctb) 10:18, 12 October 2012 (UTC)[reply]

By the Euler–Fermat theorem, ord_p²(2) divides φ(p²) = (p − 1)p, hence also gcd(n − 1,(p −1)p). Since n − 1 is coprime to p, this gcd divides p − 1.—Emil J. 14:22, 12 October 2012 (UTC)[reply]