lehmer'stotientproblem
Lehmer's Totient Problem
phi(n) | n-1 => n prime
Proof:
clearly phi(p^m) does not divide p^m-1
therefore let p|n,q|n [p,q distinct primes]
phi(p)=p-1, phi(q)=q-1
(p-1)(q-1)|n-1 with pq|n
WLOG, by symmetry p=q
Lehmer's Totient Problem
phi(n) | n-1 => n prime
Proof:
clearly phi(p^m) does not divide p^m-1
therefore let p|n,q|n [p,q distinct primes]
phi(p)=p-1, phi(q)=q-1
(p-1)(q-1)|n-1 with pq|n
WLOG, by symmetry p=q