2

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.

Question:

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

David K
  • 98,388
Krio
  • 65
  • 1
    Type it out, please. It shows a lack of effort on your part when you just take a screenshot and link the image. – Fine Man Oct 29 '16 at 00:49
  • 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 – Krio Oct 29 '16 at 00:50
  • @Krio Yes, that would be best. – Hayden Oct 29 '16 at 00:54
  • @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. – Fine Man Oct 29 '16 at 00:54
  • @sirjony kk donesorry about that – Krio Oct 29 '16 at 00:58

2 Answers2

2

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

Doug M
  • 57,877
0

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

Steven Alexis Gregory
  • 26,769