Wednesday, April 18, 2018

elementary number theory - 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!


Answer



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.


No comments:

Post a Comment

analysis - Injection, making bijection

I have injection $f \colon A \rightarrow B$ and I want to get bijection. Can I just resting codomain to $f(A)$? I know that every function i...