Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
add comment

2 Answers 2

up vote 3 down vote accepted

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.

share|improve this answer
add comment

Unless you're required explicitly to use Euler's function the above is unduly messy:

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

share|improve this answer
    
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 can understand that now, however what do we do when the numbers become difficult to compute in our minds? –  CodeKingPlusPlus Sep 23 '12 at 18:58
    
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
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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