Find an integer a which satisfies a ≡ 5 (mod 8) and a ≡ 3 (mod 7)

Question

We are learning congurence class part for an intro course. This is a sample exam question without a solution.

I have poor idea about this problem.

My idea is : suppose there is an a satisfies it.

then I have

7a ≡ 35 (mod 56) and 8a ≡ 24 (mod 56)

then by doing the substraction I get

a ≡ -11 (mod 56)

then

a ≡ 45 (mod 56)

That is all the steps I can do up to now.

Any hint plz?

Thank you in advance.

==========

Addition: actually I found it is the correct anwser that a = 45. But I am not really sure why it is the answer. I got this answer suprisingly..

Answer 1

You can use the method of adding the modulus to solve a problem like this:

$\pmod{8}: a\equiv 5\equiv 13\equiv 21\equiv 29\equiv 37\equiv 45$.

We note that $45$ also satisfies the $\mod{7}$ congruence.

So the solution is $a\equiv 45\pmod{56}$.

Answer 2

I'm not sure this is gonna help you because this solution may not be one you are looking for, however it just uses very simple idea.

Suppose that $$ a \equiv 5 \;\text{(mod 8)} \quad a\equiv 3 \;\text{(mod7)} $$

Then $a+11$ must be divisible by both $8$ and $7$. So $a+11 \equiv 0 \; \text{(mod $56$)}$. Which gives unique solution up to mod $56$.

Answer 3

${\rm mod}\ 8\!:\,\ a\equiv 5\iff a = \color{#0a0}{5+ 8n}$

${\rm mod}\ 7\!:\,\ 3\equiv a\equiv \color{#0a0}{5+8n}\equiv 5+n\iff n\equiv -2\equiv 5\iff \color{#c00}{n = 5+7k}$

So we conclude $\ a = 5+8\color{#c00}n = 5+8(\color{#c00}{5+7k}) = 45 + 56k$