contestada

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.)

Respuesta :

[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

Otras preguntas