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