Jump to content

Wikipedia:Reference desk/Archives/Mathematics/2012 October 12

From Wikipedia, the free encyclopedia
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

[edit]

Congruence question

[edit]

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

Ah, n-1 is divisible by the multiplicative order of 2 modulo p2. -- Toshio Yamaguchi (tlkctb) 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 ordp2 2? -- Toshio Yamaguchi (tlkctb) 10:18, 12 October 2012 (UTC)[reply]

By the Euler–Fermat theorem, ordp2(2) divides φ(p2) = (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]