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

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.

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.