Respuesta :

LammettHash

4, 5, and 7 are mutually coprime, so you can use the Chinese remainder theorem right away.

We construct a number [tex]x[/tex] such that taking it mod 4, 5, and 7 leaves the desired remainders:

[tex]x=3\cdot5\cdot7+4\cdot2\cdot7+4\cdot5\cdot6[/tex]

  • Taken mod 4, the last two terms vanish and we have

[tex]x\equiv3\cdot5\cdot7\equiv105\equiv1\pmod4[/tex]

so we multiply the first term by 3.

  • Taken mod 5, the first and last terms vanish and we have

[tex]x\equiv4\cdot2\cdot7\equiv51\equiv1\pmod5[/tex]

so we multiply the second term by 2.

  • Taken mod 7, the first two terms vanish and we have

[tex]x\equiv4\cdot5\cdot6\equiv120\equiv1\pmod7[/tex]

so we multiply the last term by 7.

Now,

[tex]x=3^2\cdot5\cdot7+4\cdot2^2\cdot7+4\cdot5\cdot6^2=1147[/tex]

By the CRT, the system of congruences has a general solution

[tex]n\equiv1147\pmod{4\cdot5\cdot7}\implies\boxed{n\equiv27\pmod{140}}[/tex]

or all integers [tex]27+140k[/tex], [tex]k\in\mathbb Z[/tex], the least (and positive) of which is 27.

Otras preguntas