I'm trying to prove that at least one Fermat liar exists for a composite number n when $gcd(\phi(n), n-1) > 1$.

I can see how if n was prime, then the gcd would equal 1, but I'm not sure how to flip this for the above statement.

Another thought I had was that $\phi(n)$ would potentially divide n-1? (In which case, it's a simple application of Euler's Theorem), but I'm not sure how to prove that..

Any nudges would be appreciated!


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.