3
$\begingroup$

I think the following is true:

If $q$ is coprime to $a$ then $a\mid (nq-1)$ for some $n\in\mathbb Z$.

I have started to first reducing $n\in\mathbb Z$ to $n\in\{1,\ldots,a-1\}$ and then considering all the cases $q = ka + j$ for $j=1,2,3,\ldots,a-1$. I stopped at $j=3$ and found that this is kinda messy. Does anyone have an elegant proof for this (maybe using some results from number theory)?

[Note: question has been generalized from prime $q\nmid a$ to $\,q$ coprime to $a$]

$\endgroup$
2
  • 2
    $\begingroup$ It's a straight-forward application of Bézout's theorem. $\endgroup$
    – user228113
    Jun 17, 2017 at 19:56
  • $\begingroup$ Yeah!!! Thanks a lot. This was what I was looking for. $\endgroup$ Jun 17, 2017 at 20:01

3 Answers 3

2
$\begingroup$

[Note: this applies to the initial version of the question where prime $\,q\nmid a\ $]

If $q\not\mid a$, then $a^{q-1}\equiv1$ mod $q$, by Fermat's little theorem. Writing this as $a^{q-1}=1-nq$ with $n\in\mathbb{Z}$, then $q\ge2$ implies $a\mid a^{q-1}$, which means $a\mid(nq-1)$.

$\endgroup$
2
$\begingroup$

Below are a few ways to prove the gcd $\rm \,(c,m) = 1\iff c\,$ is invertible $\!\!\rm \pmod{\! m}$

By Euler's Theorem $\rm \,(c,m)=1\,\Rightarrow\,c^{\varphi(m)}\equiv 1\pmod m.\,$ Or use Bezout as below (for $\rm b\!=\!1)$

$$\rm \exists\, x\in\Bbb Z\!:\ cx\equiv b\!\!\!\pmod{\! m}\!\iff\! \exists\, x,y\in\Bbb Z\!:\ cx\!+\!my = b\!\overset{\rm\ Bezout}\iff\!\gcd(c,m)\mid b\qquad$$

Or use the following

Theorem $\ $ The following are equivalent for integers $\rm\:c,\, m.$

$(1)\rm\ \ \ gcd(c,m) = 1$
$(2)\rm\ \ \ c\:$ is invertible $\rm\,(mod\ m)$
$(3)\rm\ \ \ x\to cx+d\:$ is $\:1$-$1\:$ $\rm\,(mod\ m)$
$(4)\rm\ \ \ x\to cx+d\:$ is onto $\rm\,(mod\ m)$

Proof $\ (1\Rightarrow 2)\ $ By Bezout $\rm\, gcd(c,m)\! =\! 1\Rightarrow cd\!+\!km =\! 1\,$ for $\rm\,d,k\in\Bbb Z\,$ $\rm\Rightarrow cd\equiv 1\!\pmod{\! m}$
$(2\Rightarrow 3)\ \ \ \rm cx\!+\!d \equiv cy\!+\!d\,\Rightarrow\,c(x\!-\!y)\equiv 0\,\Rightarrow\,x\!-\!y\equiv 0\,$ by multiplying by $\rm\,c^{-1}$
$(3\Rightarrow 4)\ \ $ Every $1$-$1$ function on a finite set is onto (pigeonhole).
$(4\Rightarrow 1)\ \ \ \rm x\to cx\,$ is onto, so $\rm\,cd\equiv 1,\,$ some $\rm\,d,\,$ i.e. $\rm\, cd+km = 1,\,$ some $\rm\,k,\,$ so $\rm\gcd(c,m)=1$

See here for a conceptual proof of said Bezout identity for the gcd.

$\endgroup$
1
$\begingroup$

Because $\gcd(q,a)=1$ Euler's theorem applies $$q^{\varphi(a)} \equiv 1 \pmod{a}$$ and $n=q^{\varphi(a)-1}$.

$\endgroup$
2
  • 1
    $\begingroup$ So, you can even choose a power of $q$ for $n$... Nice, thanks! $\endgroup$ Jun 17, 2017 at 20:23
  • $\begingroup$ Here come the downvoters leaving no comments ... $\endgroup$
    – rtybase
    Mar 10, 2019 at 19:40

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .