To prove that $n$ does not divide $1+(3^n)$.

$n$ is an odd integer greater than $1$. How do I prove that $n$ does not divide $1+(3^n)$. I have proved the case when $n$ is a prime by using Fermat's Theorem. Can I get some help for the general case?

• Try to divide and check the rest of the division – Nathanael Skrepek Mar 25 '17 at 10:33
• p is a prime divisor of n. e is the max power of p such that p^e divides n. If n=m(p^e) then i get p divides ((3^m)+1), again using fermats theorum. i'm stuck after this. – tony Mar 25 '17 at 10:41

The case $n=3$ is obvious. Let $n\ge 5$.

Let $p$ be the least prime divisor of $n$ ($p$ must be odd and greater than $3$).

Then $3^{2n}\equiv 1\pmod{p}$ and $3^{p-1}\equiv 1\pmod{p}$

by Fermat's Little Theorem.

I.e. $\text{ord}_p(3)\mid 2n$ and $\text{ord}_p(3)\mid p-1$.

I.e. $\text{ord}_p(3)\mid \gcd(2n,p-1)=2$.

I.e. either $3^2\equiv 1\pmod{p}$ or $3\equiv 1 \pmod{p}$.

I.e. either $p\mid 8$ or $p\mid 2$. But $p$ must be odd, contradiction.

• Is it necessary that $p$ be the least ? – MR_BD Mar 25 '17 at 10:43
• @LeilaHatami Since $p$ is the least prime divisor of $n$, we get $\gcd(n,p-1)=1$. – user236182 Mar 25 '17 at 10:43
• wow! thanks. How did you get this idea? – tony Mar 25 '17 at 10:49
• @tony I've seen similar solutions before. – user236182 Mar 25 '17 at 10:49
• can you recommend a good beginners book for number theory. – tony Mar 25 '17 at 10:51