A 14

Peter

A 14

**Posted:** Fri May 25, 2007 2:24 am

TomciO

Let $p$ be the smallest prime divisor of $n$ and let $k$ be the order of $n$ mod $p$ . Then of course: $k>1$ , $k|n$ , $k|p-1$ which implies that $n$ has a prime divisor smaller than $p$ , contradiction.

**Posted:** Fri May 25, 2007 2:24 am

ZetaX

#3

Solution by Christian Hirsch (similar, but still different):

Assume that $n$ is the smallest number $>1$ with that property. Then let $k = \gcd(n,\varphi(n)) <n$ and see that $2^k \equiv 1 \mod n$ (by $2^n , 2^{\varphi(n)} \equiv 1 \mod n$ ), thus $k|2^k-1$ .
By minimality we have $k=1$ , giving $2 \equiv 1 \mod n$ , contradiction.

**Posted:** Fri May 25, 2007 2:24 am

manjil

#4

A nice solution

**Posted:** Sun Aug 10, 2008 5:50 pm

_________________
Manjil P. Saikia

Joao Pedro Santos

#5

Let $p$ be the smallest prime divisor of $n$ . So we have $2^n\equiv_p1$ , which means that $ord_p2|n$ , but by the Fermat's Little Theorem, $\mbox{ord}_p2\le p - 1$ , so $\mbox{ord}_p2 = 1$ , so $2\equiv_p1$ , which is impossible.

**Posted:** Mon Dec 28, 2009 4:32 am