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.