Find smallest integer x>0 that solves congruence: 11x ≡ 6(mod68)

[alexarosea]

I don't understand the hint, but I found that S is 31 and T is -5. I just don't know what to do next, and my sheets from my professor aren't helping..

Find the smallest positive integer [FONT=MathJax_Math]x[/FONT] that solves the congruence:

[FONT=MathJax_Main]11​

[FONT=MathJax_Math]x[/FONT][FONT=MathJax_Main]≡[/FONT][FONT=MathJax_Main]6[/FONT][FONT=MathJax_Main]([/FONT][FONT=MathJax_Main]mod[/FONT][FONT=MathJax_Main]68[/FONT][FONT=MathJax_Main])[/FONT]
(Hint: From running the Euclidean algorithm forwards and backwards we get​

(Hint: From running the Euclidean algorithm forwards and backwards we get [FONT=MathJax_Main]1[/FONT][FONT=MathJax_Main]=[/FONT][FONT=MathJax_Math]s[/FONT][FONT=MathJax_Main]([/FONT][FONT=MathJax_Main]11[/FONT][FONT=MathJax_Main])[/FONT][FONT=MathJax_Main]+[/FONT][FONT=MathJax_Math]t[/FONT][FONT=MathJax_Main]([/FONT][FONT=MathJax_Main]68[/FONT][FONT=MathJax_Main])[/FONT]. Find [FONT=MathJax_Math]s[/FONT] and use it to solve the congruence.)[/FONT]​

 

[Dr.Peterson]

I don't understand the hint, but I found that S is 31 and T is -5. I just don't know what to do next, and my sheets from my professor aren't helping..

Find the smallest positive integer [FONT=MathJax_Math]x[/FONT] that solves the congruence:

11x ≡ 6 (mod 68)
(Hint: From running the Euclidean algorithm forwards and backwards we get 1 = s(11) + t(68). Find s and use it to solve the congruence.)
​

​

The congruence you are trying to solve is equivalent to finding the smallest positive value of x for which

11x = 68k + 6 for some integer k.
​

That is,

11x - 68k = 6
​

You have found that

11s + 68t = 1 for s=31 and t=-5.
​

Do you see a connection now? What can you do to this equation to obtain values for your x and k? (There will be a little more work to do after that.)

 

[HallsofIvy]

11x- 68k= 6

Euclidean algorithm:

11 divides into 68 6 times with remainder 2: 1(68)- 6(11)= 2.
2 divides into 11 5 times with remainder 1: 1(11)- 5(2)= 1.
Replace that "2" with 68- 6(11): 11- 5(68- 6(11))= 31(11)- 5(68)= 1.

Multiply both sides by 6: 186(11)- 30(68)= 6.
So one solution is x= 186, k= 30.

But then x= 186- 68i, k= 30- 11i is also a solution for any integer i: 11(186- 68i)- 68(30- 11i)= 11(186)- 11(68)i- 68(30)+ 68(11)i= 6.

In particular, taking i= 2, x= 186- 136= 50 is the smallest positive value of x.

Checking: 11(50)= 550= 8(68)+ 6= 6 (mod 68).