Find all odd n such that n|3^{n}+1

[LCSphysicist]

Homework Statement

Find all odd n such n|3^{n}+1

Relevant Equations

.

Find all odd n such $n|(3^{n}+1)$

I don't know exactly what to do, the same problem can be stated as to seek solutions of this equation:
$3^{n} = 2 + n \mu$

But if so, we are outing from Number theory and going to Calculus, so i don't like this way to solve.

Do you know another method?

Now the only prime number i can find is 2 using Fermat theorem, so i think the solutions aren't primes, this may help.

 

[Mark44]

Homework Statement:: Find all odd n such n|3^{n}+1
Relevant Equations:: .

Find all odd n such $n|(3^{n}+1)$

I don't know exactly what to do, the same problem can be stated as to seek solutions of this equation:
$3^{n} = 2 + n \mu$

I don't have any advice on this problem, but I don't think the above is right. If n is odd, and n divides $3^n + 1$, then $3^n + 1$ has to be an integer multiple of n.
IOW, $3^n + 1 = kn = k(2m + 1)$, where m is an integer.
So the equation is $3^{2m + 1} + 1 = 2km + k$

But if so, we are outing from Number theory and going to Calculus, so i don't like this way to solve.

I don't see that the equation has anything to do with calculus.

Do you know another method?

Now the only prime number i can find is 2 using Fermat theorem, so i think the solutions aren't primes, this may help.

But 2 isn't odd, so doesn't satisfy the requirement of an odd number n that divides $3^n + 1$.

 

[fresh_42]

I suspect that only $n=1$ solves the equation. Looks like playing around with theorems by Euler, Fermat, and Legendre- and Jacobi symbols. Modulo $4$ is often the key to number theory problems.

 

[Vanadium 50]

I often attack these problems by trying some numbers and seeing what insight I get.

n = 1 works.
n from 3 to 27 do not.
Conjecture: only 1 works.

I would then set about trying to prove that.

 

[LCSphysicist]

I don't have any advice on this problem, but I don't think the above is right. If n is odd, and n divides $3^n + 1$, then $3^n + 1$ has to be an integer multiple of n.
IOW, $3^n + 1 = kn = k(2m + 1)$, where m is an integer.
So the equation is $3^{2m + 1} + 1 = 2km + k$
I don't see that the equation has anything to do with calculus.
But 2 isn't odd, so doesn't satisfy the requirement of an odd number n that divides $3^n + 1$.

Oh yes the equation i wrote above was wrong, i appreciate your correction.

"I don't see that the equation has anything to do with calculus."

We could changing values and see how the graph of y = 3^{2m + 1} + 1 - (2km + k) behave with it, but you have more knowledge than me, so probably it has no sense indeed.

" But 2 isn't odd, so doesn't satisfy the requirement of an odd number n that divides 3n+1. "
As i said, 2 is the only prime, it was just a way to say that there is no odd prime that satisfy this :)

@fresh_42 and @Vanadium 50 has a good point, i will try to find a contradiction by absurd that may arise if n is different from 1, and post here what i found.

 

[fresh_42]

If $n=p\cdot m$, then $p|n|(3^n+1)=((3^m)^p+1)$. It may be easier to concentrate on such primes, i.e. show that they do not exist.

 

[Vanadium 50]

If $n=p\cdot m$, then $p|n|(3^n+1)=((3^m)^p+1)$. It may be easier to concentrate on such primes, i.e. show that they do not exist.

I think you have it. Those "primes" are all even.

 

[fresh_42]

I think the typical minimum principle can help here. Let $n$ be the smallest number such that $n|(3^n+1).$ Then we have an equation $n\cdot m = 3^{n-1}+\ldots+3+1\equiv 1 \mod 2.$ Setting $n=2r+1,m=2s+1$ should lead to a smaller solution of the same equation.

 

[Office_Shredder]

Since 1 is in fact the smallest n that satisfies this, it seems like you need to try something different?

Also I don't think $3^2+1=3+1$ (n=2) so I don't understand why nm equals the thing you say it does. Maybe I'm reading it wrong.

The only marginally clever thing I've figured out so far is that along with not being divisible by 2, n is not divisible by 3 either.

 

[fresh_42]

Since 1 is in fact the smallest n that satisfies this, it seems like you need to try something different?

Also I don't think $3^2+1=3+1$ (n=2) so I don't understand why nm equals the thing you say it does. Maybe I'm reading it wrong.

The only marginally clever thing I've figured out so far is that along with not being divisible by 2, n is not divisible by 3 either.

Yes, I confused $3^n+1$ with $3^n-1$ in my scribblings and divided what shouldn't have been divided, sorry. The solution $n=1$ can easily be excluded by concentrating on a minimal prime factor of $n$, so that would be less a problem.

Edit (to be taken with caution since it is quite late at night here):
Maybe the idea can be saved. Let's write
\begin{align*}
n\cdot m' &=3^n+1=(3^{n-1}-3^{n-2}+3^{n-3}\mp \ldots -3+1)\cdot (3+1)\\
n\cdot \dfrac{m'}{4}&=n\cdot m = 3^{n-1}-3^{n-2}+3^{n-3}\mp \ldots -3+1 \equiv 1 \mod 3 \,,\quad \equiv 1 \mod 2\\
(2r+1)\cdot (2s+1)&=4rs+2s+2r+1=3^{n-1}-3^{n-2}+3^{n-3}\mp \ldots -3+1\\
2(2rs+r+s)&=3\cdot (3^{n-2}-3^{n-3}+3^{n-4}\mp \ldots +3-1)
\end{align*}
That's where I thought we could possibly reach a smaller solution in case $n>1$ by cancelling $2$ and $3$ from
$$
\dfrac{2rs+r+s}{3}=\dfrac{3^{n-2}-3^{n-3}+3^{n-4}\mp \ldots +3-1}{2}
$$