Q:

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:

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$.
We use Extended Euclidean Algorithm (not sure about this part, I keep messing things up), so this is where I'm stuck at.

Thanks!

A:

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.  

A:

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)$
Refer to http://en.wikipedia.org/wiki/Modular_multiplicative_inverse

A:

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.

