# There are positive integers $a,b,c$ such that $m^a=1+n^bc$

Let $m$ and $n$ are relatively prime integers and $m>1,n>1$. Show that:There are positive integers $a,b,c$ such that $m^a=1+n^bc$ , and $n$ and $c$ are relatively prime

• Is $c$ allowed to be $1$? – Fimpellizieri Sep 1 '16 at 5:52
• @Fimpellizieri Well, $1$ is a positive integer and relatively prime to $n$, so yes. – 6005 Sep 1 '16 at 6:30
• I asked because it more or less trivializes the question. Consider the powers of $m$ modulo $n$, and bear in mind that since $m$ and $n$ are coprime one may divide by $m$ modulo $n$. – Fimpellizieri Sep 1 '16 at 6:42
• @Fimpellizieri: Letting $c$ be $1$ is extremely restrictive - powers don't often differ by $1$. Maybe you're thinking of letting $b$ be $1$. – Zev Chonoles Sep 1 '16 at 12:19

EDIT: I deleted the previous answer and replaced it with a simpler argument, although the idea is similar.

We know that $m^{\phi(n^2)}\equiv 1 \pmod{n^2}$, i.e. $$m^{\phi(n^2)}=1+n^2z.$$ If $(n,z)=1$ we are done, otherwise we use the following lemma.

Lemma. If $p$ is a prime and $p|n$ then $$(1+n^2z)^p=1+n^2(pz)c$$ with $(c,n)=1$.

Proof $$(1+n^2z)^p=1+\sum_{i=1}^{p-1} {p\choose i}(n^2z)^i+n^{2p}z^p=1+pn^2z(1+Cn)$$ because $p|{p\choose i}$ for $1\leq i\leq p-1$ and $p|n$. Finally $(n,1+Cn)=1$.

Now thanks to the previous lemma we start "feeding" prime factors of $n$ to $z$ until we can factor out a power of $n$, and we are left with $1+n^ac$ and $(c,n)=1$.

Since $m$ and $n$ are relatively prime, for any $b$ we have $m^{\phi(n^b)} \equiv 1 \mod{n^b}$, which is to say that there exists a $c$ such that $m^{\phi(n^b)} = 1+n^bc$.

• Why is $c$ relatively prime to $n$? – Aravind Sep 2 '16 at 9:04
• An excellent question. There are two things we can tweak. We can choose $b$ as we please, and having done so, if $r$ is the order of $m$ modulo $n^b$, we can choose any multiple of $r$ for $a$. Last night I thought it was obvious how to tweak these two. I seem to be dumber this morning. – B. Goddard Sep 2 '16 at 13:29