5
$\begingroup$

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!

$\endgroup$
4
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ 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? $\endgroup$ – KaliKelly Aug 22 '10 at 8:08
  • $\begingroup$ Yes!! I got it! Hahaha so glad I found this site :D:D:D:D:D Thanks to the both of you!! $\endgroup$ – KaliKelly Aug 22 '10 at 8:58
  • $\begingroup$ 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 $\endgroup$ – Casebash Aug 22 '10 at 10:58
  • 1
    $\begingroup$ @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. $\endgroup$ – Aryabhata Aug 22 '10 at 14:36
8
$\begingroup$

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.

$\endgroup$
5
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Hi thanks for the reply, can you please explain how you got Now 25−1=48, since 25∗48=1200=1(mod 109)? $\endgroup$ – KaliKelly Aug 22 '10 at 6:34
  • $\begingroup$ To calculate modular inverse you need to use your extended Euclid's algorithm. (The procedure is there in the Wikipedia link.) $\endgroup$ – KalEl Aug 22 '10 at 6:38
  • $\begingroup$ Let me know if you have trouble understanding why $48=25^{-1}$. (The reason it is so is 25*48=109*11+1.) $\endgroup$ – KalEl Aug 22 '10 at 7:29
  • $\begingroup$ 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? $\endgroup$ – KaliKelly Aug 22 '10 at 7:40
  • $\begingroup$ 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". $\endgroup$ – KalEl Aug 22 '10 at 9:30
2
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy