Not understanding Simple Modulus Congruency

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

Refer to http://en.wikipedia.org/wiki/Modular_multiplicative_inverse

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.