I am attempting a two-part problem on proofs and I am stuck on the second part. I think I have answered the first part correctly. (Note: these proofs are RSA-related, hence the variables)
Here is the first part with my answer:
Prove that if $\gcd(e, φ(N)) = 1$ then $e$ has a unique multiplicative inverse modulo $φ(N)$.
Consider a sequence of numbers in modulo $φ(N)$ from $0$ up to $φ(N) – 1$.
Given that there are only $φ(N)$ distinct values in the modulo, it follows that $de ≡ 1\mod φ(N)$ for one unique value, where $d$ is the multiplicative inverse.
Let $ef = eg (\mod φ(N))$ for the non-negative distinct numbers $f, g$.
This means that $(f – g)e = 0 \mod φ(N)$.
Since $e$ and $φ(N)$ are coprime it implies that $(f – g)$ is a multiple of $φ(N)$ which is not possible since both $f$ and $g$ were numbers less than $φ(N)$. QED.
The second question is as the title states:
Prove that if $\gcd(e, φ(N)) > 1$, then a multiplicative inverse does not exist.
My first thought was proving this by contradiction i.e. assuming that there exists a multiplicative inverse when $\gcd(e, φ(N)) > 1$. But I'm not quite sure how to continue from there. Please help.
Best Answer
Bezut's Lemma: Let $a,b>0$. Then $GCD(a,b)=1\iff\exists x,y$ such that $ax+by=1$
Assume the multiplicative inverse of $e$ does exist modulo $\varphi(N)$. Call it $y$. Then $\varphi(N)|(ey-1)\Rightarrow \exists k$ such that $k\varphi(N)=ey-1$, so $1=ey+(-k)\varphi(N)$
However, we know that this cannot be true, by the above Lemma, so we have a contradiction. Thus there must not have been a multiplicative inverse of $e$