# Not understanding Simple Modulus Congruency

Hi this is my first time posting on here... so please bear with me :P

I was just wondering how I can solve something like this:

$$25x ≡ 3 \pmod{109}.$$

If someone can give a break down on how to do it would be appreciated (I'm a slow learner...)!

Here is proof that I've attempted:

1. Using definition of modulus we can rewrite $$25x ≡ 3 \pmod{109}$$ as $25x = 3 + 109y$ (for some integer $y$). We can rearrange that to $25x - 109y = 3$.

2. We use Extended Euclidean Algorithm (not sure about this part, I keep messing things up), so this is where I'm stuck at.

Thanks!

Here's an alternative method that is due to Gauss. Scale the congruence so to reduce the leading coefficient. Hence we seek a multiple of $$\:25\:$$ that is smaller $$\rm(mod\ 109)\:.\$$ Clearly $$\,4 = \lfloor 109/25\rfloor\,$$ works: $$\; 4\cdot25\equiv 100 \equiv -9 \;$$ has smaller absolute value than $$25$$. Scaling by $$\,4\,$$ yields $$\rm\, -9\ x \equiv 12.\;$$ Similarly, scaling this by $$\,12 = \lfloor 109/9\rfloor$$ yields $$\rm\ x \equiv 144 \equiv 35$$. See here for a vivid alternative presentation using fractions.

This always works if the modulus is prime, i.e. it will terminate with leading coefficient $$1$$ (versus $$0$$, else the leading coefficient would properly divide the prime $$\rm\:p\:$$). It's a special case of the Euclidean algorithm that computes inverses mod $$\:\rm p\:$$ prime. This is the way that Gauss proved that irreducible integers are prime (i.e. that $$\,\rm p\mid ab\Rightarrow p\mid a\,$$ or $$\,\rm p\mid b$$), hence unique factorization; it's essentially Gauss, Disquisitiones Arithmeticae, Art. 13, 1801, which iterates $$\rm (a,p) \to (p \;mod\; a, p)\;$$ i.e. $$\rm a\to a' \to a'' \to \cdots,\; n' = p \;mod\; n \;$$ instead of $$\rm (a,p) \to (p \;mod\; a,\: a)$$ as in the Euclidean algorithm. It generates a descending chain of multiples of $$\rm\ a\pmod{\!p}.\,$$

For further discussion see this answer and my sci.math post on 2002\12\9.

You need to just 'divide' by 25 and get the solution.

$25x=3(mod\ 109)$

$\Rightarrow 25^{-1}25x=25^{-1}3 (mod\ 109)$

$\Rightarrow x=25^{-1}3 (mod\ 109)$

Now $25^{-1}=48$, since $25*48=1200=1(mod\ 109)$. So we have -

$x=48*3=35(mod\ 109)$

• Hi thanks for the reply, can you please explain how you got Now 25−1=48, since 25∗48=1200=1(mod 109)?
– KaliKelly
Aug 22, 2010 at 6:34
• To calculate modular inverse you need to use your extended Euclid's algorithm. (The procedure is there in the Wikipedia link.) Aug 22, 2010 at 6:38
• Let me know if you have trouble understanding why $48=25^{-1}$. (The reason it is so is 25*48=109*11+1.) Aug 22, 2010 at 7:29
• Okay I've used EEA, I got 25(48) - 109(11) = 1. I googled how to do it following this: mast.queensu.ca/~math418/m418oh/m418oh04.pdf Which was what you got... in one line, while I took a dozen lines. BTW, how do I use the fancy math formatting on my posts?
– KaliKelly
Aug 22, 2010 at 7:40
• The fancy formatting is done by a component called MathJax, which is basically a TeX formatter using Javascript. So for example 25^{−1} in-between two dollar signs looks like looks like $25^{-1}$ automatically when you post. You can google TeX formatting to learn how it works, and for anything on this site which interests you, you can right-click the mathematical equation to "view source". Aug 22, 2010 at 9:30

The extended euclidean algorithm is used to find x and y such that ax + by = gcd of a and b.

In our case $a = 109$ and $b = 25$.

So we start as follows.

Find remainder and quotient when we divide $109$ by $25$ and write the remainder on the left hand side.

So we get

9 = 109 - 25*4.

Now we get two new numbers $25$ and $9$. Write the remainder on the left hand side again.

7 = 25 - 9*2.

So we have two new numbers, 9 and 7.

In the extended algorithm, we use the formula for 9 in the first step

7 = 25 - (109 - 25*4)*2 = 25*9 - 109*2.

Now

2 = 9 - 7*1

= (109-25*4) - (25*9 - 109*2) = 109*3 - 25*13

Now write

1 = 7 - 3*2

i.e.

1 = (25*9 - 109*2) - 3*(109*3 - 25*13)

i.e. 1 = 25*48 - 109*11

Thus $25x - 109y = 1$ for $x = 48$ and $y = 11$.

So $25x - 109y = 3$ for x = 48*3 = 144 and y = 11*3 = 33.

Therefore 144*25 = 3 (mod 109).

If you need a number $\le 109,$

$144 = 109 + 35$.

So we have (109+35)*25 = 3 (mod 109).

Which implies 35*25 = 3 (mod 109).

Thus $x = 35$ is a solution to your equation, which we found using the extended euclidean algorithm.

Hope that helps.

• Cool you typed all that just for me! ^_^ I understand until here: So 25x - 109y = 3 for x = 48*3 = 144 and y = 11*3 = 33. Can you explain why you multiplied by 3?
– KaliKelly
Aug 22, 2010 at 8:08
• Yes!! I got it! Hahaha so glad I found this site :D:D:D:D:D Thanks to the both of you!!
– KaliKelly
Aug 22, 2010 at 8:58
• Note that we have only shown that the numbers congruent to 35 mod 109 are a solution. However, as 25 is relatively prime to 109, multiplying by 25 permutates the elements of integers mod 109 and so this group of elements is the unique solution Aug 22, 2010 at 10:58
• @Case: Or just simply, if 25x1 = 25x (mod 109) then since 25 and 109 are relatively prime, x = x1 mod 109, because 25(x-x1) is divisible by 109. Aug 22, 2010 at 14:36

I meant this as a comment to the discussion after Student's answer but it seems that I don't have the option (reputation too low?) so I'll post it as an answer. Sorry.

In order to compute quickly the inverse of 25 mod 109, note that $25=5^2$. Thus $25^{-1}=t^2$ where $t=5^{-1}$ mod 109. On the other hand, computing the inverse of 5 modulo any number $N$ ending with 9 (or 4) is immediate since it is just $(N+1)/5$. Thus $25^{-1}=((109+1)/5)^2=22^2=48$.

Moral: when performing actual computations always look for easy tricks that allow shortcuts.