Proof that if gcd(e, φ(N)) > 1, then a multiplicative inverse does not exist.

Question

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.

Answer 1

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$

Answer 2

Assume by contradiction that $gcd(e, \phi(N))=k >1$ and that $e$ has a multiplicative inverse $d$ modulo $\phi(N)$.

Then $$de \equiv 1 \pmod{\phi(N)} \Rightarrow \phi(N) |de-1$$

Since $k |\phi(N)$ you get that $k|de-1$. But $k$ also divides $e$ hence $de$.

This implies that $k|1$ contradiction.

P.S. You don't need contraction: in the above proof, if you dente note the gcd of $e$ and $\phi(N)$by $k$ (without assuming that t is greater than 1), the same reasoning leads to $k|1$ and hence $k=1$.