# Elementary number theory question involving extrapolating remainders from mod a to a mod (multiple of a) , in this case from mod 72 to mod 216

Question :- A four-digit number when divided by 7,8 and 9 leave remainders of 4,1,2 respectively. What could be a possible remainder when the number is divided by 216.

I need help in understanding the solution given by the professor in class

Number has to be of form $$7a+4, 8b+1, 9c+2$$

On combining these three kind of numbers into one family we get $$504k+137$$

Now from the next step I am getting confused :-

He said since $$gcd(504,216)=72$$

and $$504k+137$$ is $$72a+65$$ kind of number

therefore with 216 we will have $$65, 137, 209$$ as remainders

Why will these three remainders exist for sure and none of them is getting eliminated ?

This is similar to a problem I had asked earlier If p is a prime number greater than 3, then what all remainders are possible when $(p^3+15)$ is divided by 18? , where in by extending the remainders from mod 6 to mod 18 we got a list of "possible" remainders finally from which only 2 had survived upon checking , however in this current question none of the three remainders are getting eliminated. Why is this happening ?

• $\!\!\bmod 216\!:\ 137\!+\!504\Bbb Z = \overbrace{137\!+\!\color{#c00}{504\Bbb Z\! +\! 216\Bbb Z} = 137\!+\!\color{#c00}{72\Bbb Z}}^{\textstyle \gcd(504,216) = 72} = \overbrace{65,137,209}^{\textstyle \color{#0a0}3\ \rm values}\,$ by $\rm\color{#c00}{Bezout}$ & $\,216/72=\color{#0a0}3\ \$ Mar 25 at 17:22
• Hi Bill, I am not able to understand what you are trying to convey with that comment. Could you please elaborate on it; Can you also explain the reasoning without Bezout Mar 25 at 17:32
• Precisely what don't you understand? Mar 25 at 18:41
• I did not understand the what you did in red font and from there how did you reach 65 , 137, 209 Mar 25 at 18:43
• By Bezout: $\,a\Bbb Z + b\Bbb Z := \{ax+by\ :\ x,y\in \Bbb Z\} = \{\gcd(a,b)z\ :\ z\in \Bbb Z\} = \gcd(a,b)\Bbb Z.\,$ Finally $\,x\equiv 137\equiv 65\pmod{72}\iff x\equiv 65,\, 65\!+\!72,\, 65\!+\!(\color{#c00}{3}\!-\!1)72 \pmod{\!\color{#c00}3\cdot 72}\,$ follows as here. $\ \$ Mar 25 at 18:59

I hope you have understood till $$504k+137$$.
The number is of the form $$504k+137 = 72(7k+1)+65 = 72a+65$$ Now, $$72 \times 3 = 216$$. So, $$72(l+3)+65 \equiv 72l+65 \pmod {216}$$for any integer $$l$$. Thus, it is enough to analyse remainders modulo $$216$$ when $$a = 0,1,2$$, after that, the values will repeat. $$72a+65 \equiv 72(0)+65,72(1)+65,72(2)+65 \equiv 65,137,209 \pmod{216}$$ Try taking a few values of $$k$$, and see if you spot the repeating thing.

We took the $$\gcd$$ of $$216$$ and $$504$$ because:

1. We need a common divisor of the two numbers, so that we reduce modulo $$504$$ to modulo $$72$$, and then from there to modulo $$216$$. Not easy if we choose any number not a factor of the two.
2. The this common divisor $$d$$ should be such that $$504/k$$ ($$7$$ in this case) and $$216/k$$ ($$3$$ here) are coprime. Otherwise, we will not be able to choose any integral value for $$a$$. Therefore, this $$d$$ has to be the $$\gcd$$.

In fact $$kx \equiv km \pmod{kn} \iff x \equiv m \pmod n$$

• Hi @D S , thank you for the solution, what is this $a+3$ in the expression ? Mar 25 at 18:27
• Simpler: $\, x\equiv 137\pmod{\!7\cdot\color{#c00}{72}}\,\Rightarrow\, x\equiv 137\equiv 65\pmod{\!\color{#c00}{72}}$ by here $\ \$ Mar 25 at 18:28
• @BillDubuque I did it the long way so that the OP understands that.
– D S
Mar 25 at 18:29
• Unlikely the OP would be able to able to infer the general idea (congruence persistence mod factors of the modulus) from this special casse given what you wrote, so it is important to be explicit. Also this doesn't explain where $72$ comes from, and why "none of them is getting eliminated". It is essential to read the prior question for context. Mar 25 at 18:33
• @DS , thanks for the edit , but I wanted to understand how you came with $l+3$ after stating $72*3=216$ Mar 25 at 18:35