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

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.

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$

• Could you reformulate how it is a contradiction? I understand that a Diophantine equation $ax+bx=c$ has solutions if $\gcd(a,b)$ divides $c$... Is it that if the equation has a solution then there is an inverse? help – user9750060 Jan 4 '16 at 23:02
• @Evelyn I reworded and expanded it. Does that make sense now? – Stella Biderman Jan 4 '16 at 23:25
• This makes a lot of sense - thank you so much! – user9750060 Jan 5 '16 at 15:15
• Is there any particular reason you removed the "accepted" tag from my answer? – Stella Biderman Jan 9 '16 at 23:17
• @Evelyn see above question – Stella Biderman Jan 27 '16 at 15:18

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

• One thing I am a tad confused by is this: "But $k$ also divides $e$ hence $de$. This implies that $k|1$ contradiction." I understand how $k$ is a factor of $e$ and therefore $de$. But I don't see how this implies that $k|1$... Could you explain please – user9750060 Jan 6 '16 at 13:35
• @Evelyn If $k$ divides two numbers, it also divides their difference: $k|de$ and $k|de-1$ implies that $k| (de)-(de-1)$. – N. S. Jan 6 '16 at 14:52