View Single Post
Old 2021-09-23, 12:35   #55
Dr Sardonicus
Dr Sardonicus's Avatar
Feb 2017

4,993 Posts

I don't know about the approach in its entirety, but I can confirm the congruence.

If 2n-1 == 1 (mod n), and p is a prime for which p|n, then 2n-1 == 1 (mod p).

Consequently, if m is the least positive integer for which 2m == 1 (mod p) [m is the multiplicative order of 2 (mod p)] then m divides n-1.

We thus have n == 1 (mod m). Since 2p-1 == 1 (mod p) m also divides p-1, so p == 1 (mod m), and n == p (== 1) (mod m).

Since by hypothesis p divides n, we have n == p (== 0) (mod p).

Now m divides p-1, so m and p are relatively prime. By CRT we have n == p (mod mp).
Dr Sardonicus is offline   Reply With Quote