0
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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$

$\endgroup$
  • $\begingroup$ 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 $\endgroup$ – user9750060 Jan 4 '16 at 23:02
  • $\begingroup$ @Evelyn I reworded and expanded it. Does that make sense now? $\endgroup$ – Stella Biderman Jan 4 '16 at 23:25
  • 1
    $\begingroup$ This makes a lot of sense - thank you so much! $\endgroup$ – user9750060 Jan 5 '16 at 15:15
  • $\begingroup$ Is there any particular reason you removed the "accepted" tag from my answer? $\endgroup$ – Stella Biderman Jan 9 '16 at 23:17
  • $\begingroup$ @Evelyn see above question $\endgroup$ – Stella Biderman Jan 27 '16 at 15:18
0
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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 $\endgroup$ – user9750060 Jan 6 '16 at 13:35
  • $\begingroup$ @Evelyn If $k$ divides two numbers, it also divides their difference: $k|de$ and $k|de-1$ implies that $k| (de)-(de-1)$. $\endgroup$ – N. S. Jan 6 '16 at 14:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.