[Math] Fast Euler’s Phi function and linear congruence

elementary-number-theorymodular arithmetic

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?

Best Answer

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.

Related Question