$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?

  • $\begingroup$ Try to divide and check the rest of the division $\endgroup$ – Nathanael Skrepek Mar 25 '17 at 10:33
  • $\begingroup$ 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. $\endgroup$ – tony Mar 25 '17 at 10:41

Prove it by contradiction.

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.

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

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.