I really don't know how to tackle this proof because it has mod in it. There's 3 parts to the question. You don't have to answer all three parts (would be cool to check answer with though), I just need a starting point so get this proof rolling.


Relatively Prime: Means if two numbers' greatest common divisor is $1$. Let $a$ and $n$ be two natural numbers. Prove that if $a$ and $n$ are relatively prime, there exists a unique natural number $b < n$ such that $ab \equiv_n 1$ by doing the following:

a) Prove that $$\exists b \in \mathbb N, b < n \land ab\equiv_n 1. \tag1$$

b) Add to equation ($1$) in part (a) to express that $b$ is unique.

c) Now prove $b$ is unique.

(If you need a picture of the question Question picture

  • 1
    $\begingroup$ Type it out, please. It shows a lack of effort on your part when you just take a screenshot and link the image. $\endgroup$ – Fine Man Oct 29 '16 at 0:49
  • $\begingroup$ I actually tried but I couldn't get the modulus typed out properly so I resorted to posting a picture, if you still want however I can type it out and someone can edit it properly $\endgroup$ – Krio Oct 29 '16 at 0:50
  • $\begingroup$ @Krio Yes, that would be best. $\endgroup$ – Hayden Oct 29 '16 at 0:54
  • $\begingroup$ @Krio -- That ought to do. There are plenty of MathJax wizards on Math.SE (I'm not one of them) that can fine tune the formatting. $\endgroup$ – Fine Man Oct 29 '16 at 0:54
  • $\begingroup$ @sirjony kk donesorry about that $\endgroup$ – Krio Oct 29 '16 at 0:58

if $\gcd (a,n) = 1$ then by the Euclidean algorithm there exists integer $x$ and $y$ such that $ax + ny = 1$

or $ax \equiv 1 \pmod n$

We have not shown that $0<x<n$

if $ax \equiv 1\pmod n \implies a(x-n) \equiv 1\pmod n$

$x$ is not in the desired interval, there exists a $z$ such that $x-zn = b$ with $b$ in the the interval.

$ab \equiv 1\pmod n, 0<b<n$

Is b unique? Suppose there were another, $ac \equiv 1\pmod n$

$a(c-b)\equiv 0\pmod n$

But that is only possible if $n|(c-b)$


$(1.)$ There exist $x$ and $y$ such that $ax+ny = 1$. Then $ax \equiv_n 1$.

$(2.)$There exists integers $q$ and $b$ such that $x = qn + b$ where $0 \le b < n$. We see, in this case, that $0 < b < n$.

$(3.)$ Suppose $0<b,b'<n$ and $ab \equiv_n ab' \equiv_n 1$.

Then $a(b-b') \equiv_n 0$.

What follows is a proof that, if $a$ and $n$ are relatively prime, then $b-b' =0$.

So $n$ divides $a(b-b')$.

Since $ax+ny=1$, then $a(b-b')x + n(b-b')y = b-b'$.

Since $n$ divides $a(b-b')$, it divides $a(b-b')x$.
Clearly $n$ divides $n(b-b')y$.
So $n$ must divide $b-b'$.

Since $0 < b < n$ and $-n < -b' < 0$, then $-n < b-b' < n$.

The only multiple of $n$ between $-n$ and $n$ is $0$. So b-b' = 0$.

Hence $b=b'$. So $b$ is unique.


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.