4
$\begingroup$

The problem follows,

What is the smallest composite number n, such that $n \vert 2^n-2$

Initially, I thought if we frame the question such that $2^n$ is congruent to $2 \mod n$, we can use the phi function. Through Fermat's little theorem we know that $2^{\phi(n)}$ is congruent to $1 \pmod n$. Thus I tried finding numbers such that the $\phi(n)\vert n$. However, the answer to this problem is 341 and it doesn't fall under the restrictions I gave it.

What am I missing?

$\endgroup$
  • $\begingroup$ $2^{\phi(n)}$ is 1 mod n, not 2 $\endgroup$ – Bogdan Simeonov Apr 29 '17 at 18:28
2
$\begingroup$

We know that $341$ is the smallest base-2 Fermat pseudoprime, i.e., the smallest composite number $n$ satisfying $2^{n-1}\equiv 1 \bmod n$, i.e., satisfying $2^n\equiv 2\bmod n$. So the answer is indeed $n=341=11\cdot 31$ and all "restrictions" are satisfied.

$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.