Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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!

share|cite|improve this question
up vote 4 down vote accepted

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.

share|cite|improve this answer
1  
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
1  
@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$. See here for a vivid 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|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.

share|cite|improve this answer

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

share|cite|improve this answer
    
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.

share|cite|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.