1
$\begingroup$

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!

$\endgroup$

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.