# Fast Euler's Phi function and linear congruence

I am trying to solve $5k \equiv 2\mod7$ with Euler's phi function. $5$ and $7$ are relatively prime so we can write:

1. $5^{\phi(7)} \equiv 1\mod7$.
2. Multiply by $5^{-1}$: $5^{\phi(7)-1} \equiv 5^{-1}\mod 7$
3. We know $\phi(7) = 6$ since $\phi(p) = p - 1$ for any prime $p$
4. Thus, we have $5^5 \equiv 5^{-1}\mod7$

To check my solution I compute $5\cdot5^5\mod7$ which is 1. So I see that I have a $5^{-1}$. Now, I can solve the congruence:

1. $5k\cdot5^{-1} \equiv 2\cdot5^{-1}\mod7$
2. $k \equiv 2\cdot5^{-1}\mod7$
3. Substitute $5^5$ for $5^{-1}$: $k \equiv 2\cdot5^5\mod7$

I have a solution, but can I simplify $k$? If I can could someone list a set of values for $k$ (is the solution for $k$ unique)? Also, is there a faster, algorithmic but intuitive way to solve this congruence?

-

Hint $\rm\ mod\ 7\!:\ 5 \equiv -2\ \Rightarrow\ \dfrac{1}{5}\,\equiv\, -\dfrac{1}2\,\equiv\, 3,\$ since $\rm\:mod\ 2n\!+\!1\!:\,\ 2n\,\equiv\, -1\ \Rightarrow\ n\,\equiv\, -\dfrac{1}2$

Remark $\$ Generally one can employ the Extended Euclidean Algorithm to efficiently compute modular inverses. The above computation is an optimization for the frequent special case where the modulus is $\equiv \pm1\:$ modulo the number being inverted ($= 2$ above), hence the algorithm terminates in a single step. Euler's phi theorem is not a computationally efficient method to compute inverses for large moduli (but it is useful for theoretical purposes, such as deducing the existence of inverses for elements coprime to the modulus, as well as for other purposes).

As for uniqueness: if $\rm\ a\,x' \equiv b \equiv a\, x\:$ then multiplying both sides by $\rm\:a^{-1}\:$ yields $\rm\: x'\equiv x.$

Beware $\$ The above use of fractions in modular arithmetic is valid only when the denominator is a unit (invertible); else it is a zero-divisor so the quotient need not be unique, e.g. mod $\rm\:10,\:$ $\rm\:4\,x\equiv 2\:$ has solutions $\rm\:x\equiv 3,8,\:$ so the "fraction" $\rm\:x \equiv 2/4\pmod{10}$ cannot designate a unique solution. Indeed, the solution $\rm\:x\equiv 1/2\equiv 3\pmod 5\:$ requires cancelling $\,2\,$ from the modulus too, since $\rm\:10\:|\:4x-2\iff5\:|\:2x-1.\:$

Generally the grade-school rules of fraction arithmetic apply universally (i.e. in all rings) where the denominators are units (invertibles). This fundamental property will be clarified conceptually when one learns about the universal properties of fractions rings and localizations.

-
$$\frac{1}{5}=5^{-1}=3\pmod 7\Longrightarrow 5k=2\pmod 7\Longrightarrow k=2\cdot 5^{-1}=2\cdot 3=6=-1\pmod 7$$
I would agree that Euler's function is quite messy but it is very simple to find the solution using information that I know. How do you know that $5^{-1} = 3\mod7$?? I am looking for an algorithmic approach such that I can quickly compute the inverse. –  CodeKingPlusPlus Sep 23 '12 at 18:50
Simple: what number multiplied by $\,5\,$ equals $\,1\pmod 7\,$? –  DonAntonio Sep 23 '12 at 18:53
I really don't know, but it seems to me that there is no definite way but to apply Euclides algorithm, which can be pretty lengthy: $$7=1\cdot 5 + 2\,\,,\,\,5=2\cdot 2+1\,\,,\,\,2=1\cdot 2\Longrightarrow 1=3\cdot 5+(-2)\cdot 7\Longrightarrow 5\cdot 3 = 1\Longleftrightarrow 5^{-1}=3\pmod 7$$ –  DonAntonio Sep 23 '12 at 19:20