4
$\begingroup$

Let $a$ be an integer, $a\ge2$. If $a^{m}+1\mid a^{n}+1$ then prove that $m\mid n$.

Actually I know a similar proof which is, $a^{m}-1\mid a^{n}-1 \iff m\mid n$, but I can't prove this. I also need some examples of the question. Can't seem to find any correlation between the two proofs.
I seem to not find examples where $a$ is something different from $2$ and taking $m=2$.
Please help. I think 4-5 examples might help me to see the proof.

$\endgroup$
3
  • $\begingroup$ Specialize this more general result on their gcd (but a direct proof is easier) $\endgroup$ – Bill Dubuque May 17 '19 at 19:28
  • $\begingroup$ Note: $3^3+1$ divides $3^9+1, 3^{15}+1, 3^{21}+1,...$ $\endgroup$ – J. W. Tanner May 17 '19 at 19:31
  • $\begingroup$ @J.W.Tanner I see a pattern. Don't know if correct but I see it for $2^2+1,3^2+1,3^3+1,3^4+1$. That it is the third multiple,sixth multiple,ninth multiple of m which makes $a^n+1$ divisible by $a^m+1$. I guess it is correct for all primes . Thanks btw for it giving me little hint. Well seeing if I can find the proof or not. $\endgroup$ – Love Invariants May 17 '19 at 19:38
4
$\begingroup$

Suppose $\gcd(m,n)=d$. $$s=\gcd(a^{2m}-1,a^{2n}-1)=a^{2d}-1$$ But obviously $a^m+1\mid s$, so $$a^m+1\mid a^{2d}-1,$$ so $$m < 2d\Rightarrow d>\frac m2.$$ But $d\mid m$, so $d=m$ which means $m\mid n$.

$\endgroup$
2
  • $\begingroup$ Nice solution, the kind of I was looking after. $\endgroup$ – Love Invariants May 18 '19 at 8:28
  • $\begingroup$ @LoveInvariants For proofs of the first displayed equation see here. One is very similar to the proof in my answer (which proves a stronger result) $\endgroup$ – Bill Dubuque May 18 '19 at 12:41
0
$\begingroup$

$U_{k} = a^{k} + 1$ are terms of a Lucas sequence; hence, $U_{m} | U_{n}$ iff $m | n$.

$\endgroup$
3
  • $\begingroup$ Can you attach an article about Lucas sequence? I can't find any about what you said. $\endgroup$ – Love Invariants Jul 10 '19 at 12:47
  • $\begingroup$ Most of what I know about the Lucas sequences comes from D. H. Lehmer's "An Extended Throy of Lucas' Functions" published (1930) in the Annals of Mathematics. You should be able to access it with JSTOR or request it through interlibrary loan. I do not have an electronic copy. $\endgroup$ – mlchristians Jul 10 '19 at 14:59
  • $\begingroup$ Ok I will see . $\endgroup$ – Love Invariants Jul 12 '19 at 18:05
0
$\begingroup$

Hint $ $ By below $\, c = a^{M}+1\mid a^{(M,N)}+1\, $ so $\,\small \overbrace{(M,N)= M}^{\textstyle {\large \Rightarrow}\,M\mid N\ }\ $ (else $\,\small (M,N)< M)$

Theorem $\,\ \begin{align}c\mid a^M+1\\ c\mid a^N+1\end{align}\,$ $\Rightarrow\ \begin{align}&c\mid a^{\large d}+1\\ &\!d = {\small (M,N)}\end{align}\ \ \,$ Proof $\ $ Let $\,\begin{align} {\small M} &= dm\\ {\small N} &=\, dn\end{align}\,\ $ so $\ (m,n)=1$

$\!\!\bmod c\!:\ a^{\large dm}\equiv -1\equiv a^{\large dn}\Rightarrow a^{\large 2dm}\equiv 1\equiv a^{\large 2dn}\,$ thus $\,{\rm ord}\, a^{\large 2d}$ divides coprimes $\,m,n\,$ so it is $1,\,$ thus $\,\color{#c00}{a^{\large 2d}\equiv 1}.\,$ $\,(m,n)=1^{\phantom{I^{I^I}}}\!\!\!\!\!\!\Rightarrow m\,$ or $\,n\,$ odd, wlog $\,n = 1\!+\!2j^{\phantom{I^I}\!\!\!\!}\,$ so $\ {-}1\equiv a^{\large dn}\!\equiv a^{\large d}(\color{#c00}{a^{\large 2d}})^{\large j}\!\equiv a^{\large d}$

$\endgroup$
1
  • $\begingroup$ The Theorem is excerpted from this Theorem which computes the gcd $\,(a^M+1,a^N+1)\ \ $ More simply we could compute $\, a^N+1 \bmod a^M+1,\,$ but the Theorem is stronger and more insightful (and not much more work). $\endgroup$ – Bill Dubuque May 17 '19 at 23:20

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.