0
$\begingroup$

"Determine $d$ as $d^{-1} \equiv e \bmod \phi(n)$, i.e., $d$ is the multiplicative inverse of $e \bmod \phi(n)$." (number $5$).

I'm looking at this, and i'm not sure what the $\equiv$ means in this instance? I know the rest of the values, but what does $\equiv$ mean right now?

Thanks in advance!

$\endgroup$
3
  • 4
    $\begingroup$ Congruence modulo $\varphi(n)$. $\endgroup$
    – user61527
    Jan 4, 2014 at 21:04
  • $\begingroup$ It's $d^{-1}$ not $d-1$. You type it by typing "d^{-1}". It is the inverse in the unit group of $n$. So that means $n$ divide $de-1$. $\endgroup$
    – Gina
    Jan 4, 2014 at 21:06
  • $\begingroup$ If the answer below does not suffice then please either edit this question to elaborate and/or ask the answerer for clarification in the comments. There was no need to ask another question on essentially the same topic. $\endgroup$ Jan 10, 2014 at 19:08

2 Answers 2

1
$\begingroup$

$a^{-1}$ is the general notation for the multiplicative inverse of $a$, which is the element $b$ such that $ab = 1$. You have surely encountered this in $\mathbf{R}$, for example $2^{-1} = 1/2$ because $2\times (1/2) = 1$.

It's the same idea here, except that we do not use the standard equality, but congruence modulo $\phi(n)$. So, say I take $p = 11$, $q = 13$, this gives $n = 143$ and $\phi(n) = 120$. If I take $e = 7$, then $d = 7^{-1} = 103$ because $103\times 7 = 721$ and $721\equiv 1 \bmod{120}$.

$\endgroup$
5
  • $\begingroup$ I have been staring at this for a while, and i have a question. how does "If I take e=7, then d=7−1=103 because 103×7=721 and 721≡1 mod 120." work? i'm super confused. i understand the 2x0.5 = 1 thing, that makes sense. i've even done inverse work for school. but that last part doesnt make the least bit of sense to me. could you please explain that a bit more? thanks :) $\endgroup$
    – PulsePanda
    Jan 5, 2014 at 0:31
  • $\begingroup$ What do you mean by "how does it work"? Surely you can see that $103\times 7 \equiv 1 \bmod{120}$. $\endgroup$
    – fkraiem
    Jan 5, 2014 at 10:46
  • $\begingroup$ no, actually, as far as i'm aware, 1mod120 is 1, for mod being the remainder of the two divisors. thus, 1/120 has a remainder of 1 as you cannot evenly divide 1 by 120. so no, i dont see it. $\endgroup$
    – PulsePanda
    Jan 6, 2014 at 0:13
  • $\begingroup$ You are confusing two things. $x \bmod n$ is indeed the remainder of $x$ when divided by $n$, but $a \equiv b \bmod n$, with the $\equiv$ sign, means that $a$ and $b$ are congruent modulo $n$, meaning that $n$ divides $a-b$. $\endgroup$
    – fkraiem
    Jan 6, 2014 at 0:19
  • $\begingroup$ ahhhhhhhhhhhhhhhh ok then that makes sense! thanks! $\endgroup$
    – PulsePanda
    Jan 6, 2014 at 3:39
0
$\begingroup$

This is improper (though generally accepted) use of the notation, and you have a right to be confused. What it means is no more and no less than $1\equiv de\pmod{\phi(n)}$, which according to the definitions means that in $\def\Z{\Bbb Z}\Z$ one has that $1-de$ is an integer multiple of $\phi(n)$. This means that in the quotient ring $\Z/\phi(n)\Z$ the class of $d$ has a multiplicative inverse (necessarily unique), namely the class of$~e$; this can be expressed by writing "$d^{-1}=e$ in $\Z/\phi(n)\Z$" using the convention that an integer can be interpreted as standing for its own class when used to designate an element of some $\Z/k\Z$. (More generally integers can be unambiguously used to designate an element in any specified ring, and it is very convenient to not have to dress them up so as to indicate the change of status each time an integer is so interpreted.) Note the order of events: upon interpreting the integers $d,e$ in $\Z/\phi(n)\Z$ they change status, then the element designated by $d$ has an inverse, and this inverse is equal (not congruent) to the element designated by $e$.

The temptation is strong (too strong for some) to write "$d^{-1}=e$ in $\Z/\phi(n)\Z$" as a single formula "$d^{-1}\equiv e\pmod{\phi(n)}$"; the motivation is that "$a=b$ in $\Z/\phi(n)\Z$" and "$a\equiv b\pmod{\phi(n)}$" mean the same thing whenever $a,b$ are any integers. However $d^{-1}$ is not, and cannot designate, an integer; in fact there is no sensible meaning one can give to $d^{-1}$ so that a congruence relation with $e$ would hold for it. Indeed before taking any congruence $d^{-1}$ can only mean the rational number $\frac1d$, and $\frac1d-e\in\Bbb Q$ is definitely not an integer multiple of $\phi(n)$. So the only way to make sense out of $d^{-1}\equiv e\pmod{\phi(n)}$ is to assume that the influence of the congruence operator $\equiv$ "creeps into" its argument $d^{-1}$ and changes the meaning of the inversion operation to become inversion in $\Z/\phi(n)\Z$ (which is not how congruence relations usually work, also note that afterwards there is no place for a congruence relation, as the modular reduction has already taken place). Or maybe one should just to accept the use of the congruence as a lazy way to say that the whole expression should be interpreted in the quotient ring.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .