"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!
On
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.
$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}$.