Does $x^n+1 \equiv 0 \pmod{n}$ imply $\text{gcd}(x+1,n)>1$?
My feeling is that it shouldn't be too hard to prove, but I just can't figure it out. For $n$ prime it is clear since $x^n \equiv x \pmod{n}$ in that case.
Asked
Active
Viewed 94 times
2
1 Answers
1
This is quite a nice question and the answer to it is yes. Firstly, notice that if $n$ is even than $x$ should be odd. So $gcd(x+1,p)=2>1$ Let's take the case when $n$ is odd. Consider the canonical representation of the integer $$n=p_1^{\alpha_1}*p_2^{\alpha_2}*_{...}*p_k^{\alpha_k} $$ where $$p_1<p_2<_{...}<p_k$$ Since $$x^n+1=0 \space\ (mod \space\ n)$$ we can write $x^n+1=0 \space\ (mod \space\ p_1)$ and since $n$ is odd this is equivalent to $(-x)^n-1=0 \space\ (mod \space\ p_1)$ so $(-x)^n=1 \space\ (mod \space\ p_1)$. Because of the fact that $p_1$ is the smallest prime which divides $n$ then we have $gcd(p_1-1,n)=1$. From Bezout identity we know that there exist $a,b \in Z$ such that $c=a*(p_1-1)+b*n=1$. From here it follows $(-x)^c=-x=1 \space\ (mod \space\ p_1)$. So this means $p_1|(-x-1)$ so eventually $p_1|(x+1)$. Hence we conclude that $gcd(x+1,n)\ge p_1>1$ which completes the proof.
Sota Antonino
- 303
-
the exponent of the highest power of $p$ which divides $n$. – user236182 Mar 09 '16 at 00:28
-
Yeah you are right I'm going to fix it now. – Sota Antonino Mar 09 '16 at 00:29
-
$p$ doesn't have to divide $n$ (for the lemma to be true), but $n$ has to be odd. – user236182 Mar 09 '16 at 00:30
-
I am afraid the last one you said is just a special case of the general lemma. – Sota Antonino Mar 09 '16 at 00:33
-
Please re-read the LTE paper. Your claim is wrong. Let $x=y=1$, $n=2$, $p=2$. – user236182 Mar 09 '16 at 01:08
-
Instead of "$p\mid n$" it should be "$n$ is odd" – user236182 Mar 09 '16 at 01:08