# 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!

-

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 '10 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 '10 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 –  Casebash Aug 22 '10 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. –  Aryabhata Aug 22 '10 at 14:36

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\:$ works, since $\; 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$ yields $\rm\ x \equiv 144 \equiv 35$.

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|ab\Rightarrow p|a$ or $\rm p|b$) - hence unique factorization; it's essentially Gauss, Disquisitiones Arithmeticae, Art. 13, 1801. It 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\ (mod\ p)\:$. See my sci.math post on 2002\12\9 for further discussion.

-
See this answer for many more examples. –  Bill Dubuque Jul 24 '12 at 18:26

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 '10 at 6:34
To calculate modular inverse you need to use your extended Euclid's algorithm. (The procedure is there in the Wikipedia link.) –  KalEl Aug 22 '10 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.) –  KalEl Aug 22 '10 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 '10 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". –  KalEl Aug 22 '10 at 9:30

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.

-