7
$\begingroup$

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

$\endgroup$
  • 1
    $\begingroup$ Is $c$ allowed to be $1$? $\endgroup$ – Fimpellizieri Sep 1 '16 at 5:52
  • $\begingroup$ @Fimpellizieri Well, $1$ is a positive integer and relatively prime to $n$, so yes. $\endgroup$ – 6005 Sep 1 '16 at 6:30
  • $\begingroup$ 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$. $\endgroup$ – Fimpellizieri Sep 1 '16 at 6:42
  • 1
    $\begingroup$ @Fimpellizieri: Letting $c$ be $1$ is extremely restrictive - powers don't often differ by $1$. Maybe you're thinking of letting $b$ be $1$. $\endgroup$ – Zev Chonoles Sep 1 '16 at 12:19
1
+50
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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

$\endgroup$
  • 1
    $\begingroup$ Why is $c$ relatively prime to $n$? $\endgroup$ – Aravind Sep 2 '16 at 9:04
  • $\begingroup$ 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. $\endgroup$ – B. Goddard Sep 2 '16 at 13:29

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.