4

This is going to sound like a stupid question, but I cannot understand how I get this result (I understand why, but it looks like there is no relation). For $p, q$ primes why do we have this?

$$p\, (p^{-1}\!\bmod q) + q\,(q^{-1}\!\bmod p) = pq + 1$$

I don't see the relation between the left and right side, but still it works.

Bill Dubuque
  • 272,048
David 天宇 Wong
  • 195
  • 7
  • can you explain more about your expression? – SiXUlm Mar 16 '16 at 19:46
  • 1
    As far as I'm concerned, this is ill-defined, you work either modulo $p$ or modulo $q$. – Captain Lama Mar 16 '16 at 19:46
  • 3
    In this context, I believe that $p^{-1}\pmod q$ represents the integer which is congruent to $p^{-1}$ mod $q$ between ${0,\cdots,q-1}$ but treated as an integer, not as an element of $\mathbb{Z}/q$. – Michael Burr Mar 16 '16 at 19:49
  • 1
    It's seems to me like your post is related to the Chinese remainder theorem. That seems worth mentioning – Ben Grossmann Mar 16 '16 at 19:59
  • It doesn't look like modular arithmetic. If by "mod" you mean the reminder operation: a mod b := l, where $a = b k + l$ and $0 \le l < b$, then just put it into the expression. – Andrew Mar 16 '16 at 20:02
  • yes it is related to CRT, the special case when $y = 1 \mod p$ and $y = 1 \mod q$ then $y = 1 \mod pq$, but this is the equation itself that I wrote. – David 天宇 Wong Mar 16 '16 at 21:28
  • anyone? I still can't get it... Maybe garner's way is clearer ( http://e-maxx-eng.github.io/algebra/chinese-remainder-theorem.html ) – David 天宇 Wong Mar 17 '16 at 03:29
  • Bezout form: $,\gcd(a,b)!=!1!\iff! a(a^{-1}!\bmod b)-b(-b^{-1}!\bmod a) = 1\ \ $ – Bill Dubuque Nov 25 '23 at 03:18

2 Answers2

5

Of course it is tacitly assumed that $p\ne q$.

I'm interpreting $\ p^{-1}\>{\rm mod}\> q$ as the unique $x\in[1\>..\>q-1]$ with $xp=1\>{\rm mod}\> q$, and similarly $\ q^{-1}\>{\rm mod}\> p$ as the unique $y\in[1\>..\>p-1]$ with $yq=1\>{\rm mod}\> p$. If $x$ and $y$ are determined in this way the number $n:=xp+yq$ satisfies $$ n\leq 2pq-p-q$$ and $$n=1\ {\rm mod}\> p,\qquad n=1\ {\rm mod}\> q\ .\tag{2}$$ The number $n':=pq+1$ satisfies $(2)$. On the other hand, by the Chinese remainder theorem there can be no other such number in the interval $[\,pq,\> 2pq-p-q\,]$. It follows that $n=n'$.

If you want to avoid the CRT you can argue as follows: As ${\rm gcd}(p,q)=1$ there are $x$, $y\in{\mathbb Z}$ with $$xp-yq=1\ .$$ After adding a suitable $kq$ to $x$, and at the same time $kp$ to $y$ we may assume $x\in[1\>..\>q-1]$. It follows that $$yq=xp-1\in[p-1\>..\>pq-p-1]\ ,$$ which then implies $y\in[1\>..\>p-1]$. It follows that $y':=p-y\in[1\>..\>p-1]$ as well, and we now have $$xp+y'q=xp+(p-y)q=pq+1\ ,$$ which is the claimed formula.

Christian Blatter
  • 226,825
2

First, let's clarify the question, since one of the commenters was confused: By $$p \cdot (p^{-1} \mod q)$$ the question means to find $ p^{-1}\mod q$, transform that into the unique integer $\bar{p} \in \Bbb{N} : \bar{p} \equiv p^{-1}\mod q \wedge 0\leq \bar{p} < q$, and then multiply, in the ordinary field of integers, $p\cdot \bar{p}$.

With that understanding in place, here is your proof that $s = p \cdot (p^{-1} \mod q) + q \cdot (q^{-1} \mod p) = pq+1$ assuming $p,q$ prime:

Lemma 1: $p \cdot (p^{-1} \mod q) \equiv 1 \mod q$. Proof: This is just the definition of the inverse, mod $q$.

Corollary 2: $s \equiv 1 \mod q$. Proof: $s = p \cdot (p^{-1} \mod q) + qk$ where $k$ is some integer (which happens to be $(q^{-1} \mod p)$) so $s \equiv 1 + 0 \mod q$.

Corollary 3: $s \equiv 1 \mod p$. This is the same statement as corollary 2, exchanging $p$ and $q$.

Lemma 4: $s \equiv 1 \mod (pq)$. This is so by corollaries 2 and 3, along with the statement that $p$ and $p$ are coprime.

Lemma 5: $s > 1$. Proof: each of the terms in $s$ is a positive integer, so $s \geq 1+1$.

Lemma 6: $p \cdot (p^{-1} \mod q) < pq$ and $q \cdot (q^{-1} \mod p) < qp$. Proof: $p^{-1} \mod q < q$; multiply both sides of that relation by $p$. Similarly for the assertion about $q \cdot (q^{-1} \mod p)$.

Corollary 7: $s = p \cdot (p^{-1} \mod q) + q \cdot (q^{-1} \mod p) < 2pq$.

Theorem: $s=pq+1$. Proof: by lemma 5 and corollary 7, $1 < s < pq$. By lemma 4, $s = kpq + 1$ for some integer $k$. The unique value of the form $kpq + 1$ between $1$ and $2pq$ is $pq+1$.

Q.E.D.

Mark Fischler
  • 41,743