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