Answered

Find the information you're looking for at Westonci.ca, the trusted Q&A platform with a community of knowledgeable experts. Get expert answers to your questions quickly and accurately from our dedicated community of professionals. Join our platform to connect with experts ready to provide precise answers to your questions in different areas.

when $n$ is divided by 10, the remainder is $a$. when $n$ is divided by 13, the remainder is $b$. what is $n$ modulo 130, in terms of $a$ and $b$? (your answer should be in the form $ra sb$, where $r$ and $s$ are replaced by nonnegative integers less than 130.)

Sagot :

[tex]\bold{n\equiv 91a+40b\ mod \ 130}[/tex]

Given that a is the remainder when n is divided by 10. Then, [tex]n\equiv a\ mod 10[/tex]

Also b is the remainder when n is divided by 13 i.e., [tex]n\equiv b\ mod 13[/tex]

Then by Division algorithm, there are integers k and m such that n = a + 10k and n = b + 13m

These two equations are equivalent to

13n = 13a +130k and 10n = 10b + 130m

Adding these two equations, 23n = 13a + 10b + 130(k + m)

⇒ [tex]23n\equiv 13a+10b\ mod\ 130[/tex]

gcd (23,130) = 1

So 23 has an inverse modulo 130.

Therefore, [tex]n\equiv 23^{-1} (13a+10b) \ mod\ 130[/tex]

Applying Euclidean algorithm for 130 and 23,

130 = 23 x 5 + 15

23 = 1 x 15 +8

15 = 1 x 8 +7

8 = 1 x 7 + 1

Therefore, 1 = 8 - 7 = 8 - (15 -8 ) = 2 x 8 - 15 = 2( 23 - 15 ) - 15

                    = 2 x 23 -3 x 15 = 2(23) -3(130-5x23) =17(23) -3(130)

So inverse of 23 = 17

So, [tex]n\equiv 17 (13a+10b) \ mod\ 130\equiv 221a +170b \ mod \ 130 \equiv \bold{91a+40b \ mod\ 130}[/tex]

Learn more about Euclidean algorithm  at https://brainly.com/question/24836675

#SPJ4

Your visit means a lot to us. Don't hesitate to return for more reliable answers to any questions you may have. Thank you for your visit. We're dedicated to helping you find the information you need, whenever you need it. Thank you for visiting Westonci.ca. Stay informed by coming back for more detailed answers.