2
$\begingroup$

This question already has an answer here:

Prove that for a given prime $p$ and each $0 < r < p-1$, there exists a $q$ such that

$$rq \equiv 1 \bmod p$$

I've only taken one intro number theory course (years ago), and this just popped up in a computer science class (homework). I was assuming that this proof would be elementary since my current class in an algorithm cours, but after the few basic attempts I've tried it didn't look promising. Here's a couple approaches I thought of:


(reverse engineer)

To arrive at the conclusion we would need

$$rq - 1 = kp$$

for some $k$. A little manipulation:

$$qr - kp = 1$$

That looks familiar, but I can't see anything from it.


(sum on $r$)

$$\sum_{r=1}^{p-2} r = \frac{(p-2)(p-1)}{2} = p\frac{p - 3}{2} + 1 \equiv 1 \bmod p$$

which looks good but I don't know how to incorporate $r$ int0 the final equality.


(Wilson's Theorem—proved by Lagrange)

I vaguely recall this theorem, but I was looking at it in an old book and it wasn't easy to see how we arrived there. Anyways, $p$ is prime iff $$(p-1)! \equiv -1 \bmod p$$

Here the $r$ multiplier is built in to the factorial expression so I was thinking of adding $2$ to either side

$$(p-1)! + 2 \equiv 1 \bmod p$$

which is a dead end (pretty sure). But then I was thinking, maybe multiplying Wilson't Thm by $(p+1)$? Then getting

$$(p+1)(p-1)! = -(p+1) \bmod p$$

which I think results in

$$(p+1)(p-1)! = 1 \bmod p$$

of which $r$ is a multiple and $q$ is obvious. But I'm not sure if that's valid.

$\endgroup$

marked as duplicate by Bill Dubuque elementary-number-theory Jan 22 at 1:48

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

  • $\begingroup$ Your Wilson's theorem is a good approach, since you can multiply by $-1\equiv p-1$ on both sides to get $1$. Now you know that each of the numbers $1\lt r\lt p-1$ is a divisor of $(p-1)!$, so you can separate out each one individually and arrive at your conclusion... $\endgroup$ – abiessu Jan 22 at 1:29
  • $\begingroup$ suggest you learn the simplest type of continued fractions, as this is an algorithm used for a variety of computing tasks. For consecutive convergents, the cross product is $\pm 1.$ Doing the fraction for $\frac{p}{r},$ the penultimate convergent shows the Bezout coefficients discussed in the answer by Thomas. $\endgroup$ – Will Jagy Jan 22 at 1:33
  • 2
    $\begingroup$ Beware that common proofs of Wilson's theorem are based on the result you are trying to prove, so using Wilson would be circular in that case. $\endgroup$ – Bill Dubuque Jan 22 at 1:51
4
$\begingroup$

There are lots of proofs of this, and which is best for you will depend very much on what results you know already. Here is one which uses only the following fact:

  • if $p$ is prime and $x,y$ are integers and $p\mid xy$, then $p\mid x$ or $p\mid y$.

Now let $p$ be prime and $0<r<p$. Consider the numbers $$r,\ 2r,\ 3r,\ldots,\ (p-1)r\ .\tag{$*$}$$ Firstly, these are all different modulo $p$. Proof: if $ar\equiv br\pmod p$, then $$\eqalign{p\mid ar-br\quad &\Rightarrow\quad p\mid(a-b)r\cr &\Rightarrow\quad p\mid a-b\qquad [\hbox{since $p\not\mid r$}]\cr &\Rightarrow\quad a=b\qquad [\hbox{since $0<a,b<p$.}]\cr}$$ Secondly, none of the numbers is divisible by $p$. Proof: the numbers are $ar$ with $p\not\mid a$ and $p\not\mid r$.

Finally, this means that in $(*)$ there are $p-1$ different numbers modulo $p$ with the possible values $1,2,\ldots,p-1$ modulo $p$. So they must take each value once each. In particular, one of the numbers $ar$ is $1$ modulo $p$.

$\endgroup$
2
$\begingroup$

Continued fraction for $\frac{137}{73}$

$$ \frac{ 137 }{ 73 } = 1 + \frac{ 64 }{ 73 } $$ $$ \frac{ 73 }{ 64 } = 1 + \frac{ 9 }{ 64 } $$ $$ \frac{ 64 }{ 9 } = 7 + \frac{ 1 }{ 9 } $$ $$ \frac{ 9 }{ 1 } = 9 + \frac{ 0 }{ 1 } $$ Simple continued fraction tableau:
$$ \begin{array}{cccccccccc} & & 1 & & 1 & & 7 & & 9 & \\ \frac{ 0 }{ 1 } & \frac{ 1 }{ 0 } & & \frac{ 1 }{ 1 } & & \frac{ 2 }{ 1 } & & \frac{ 15 }{ 8 } & & \frac{ 137 }{ 73 } \end{array} $$ $$ $$ $$ 137 \cdot 8 - 73 \cdot 15 = 1 $$

$\endgroup$
  • $\begingroup$ Simpler: $\bmod 73\!:\ \dfrac{1}{137}\equiv \dfrac{1}{-9}\equiv\dfrac{8}{-72}\equiv \dfrac{8}1\ $ by Gauss's algorithm $\ \ $ $\endgroup$ – Bill Dubuque Jan 22 at 15:42
2
$\begingroup$

Theorem:If $g $ is the greatest common divisor of $r $ and $p $, then there exists integers $q $ and $k $ such that $$g=\text{gcd}(r,p)=rq+kp . $$ You can find a proof here.

Note that $r $ and $p$ are co-primes. So $\text{gcd}(r,p)=1$. Then by above mentioned theorem, we have$$\text{gcd}(r,p)=1=rq+kp.$$

Can you conclude now?

$\endgroup$

Not the answer you're looking for? Browse other questions tagged or ask your own question.