# Find a remainder when dividing some number $n\in \mathbb N$ with 30

A number n when you divide with 6 give a remainder 4, when you divide with 15 the remainder is 7. How much is remainder when you divide number $$n$$ with $$30$$?

that mean $$n=6k_1+4$$, $$n=15k_2+7$$, and $$n=30k_3+x$$, so I need to find $$x$$. And $$30=6*5$$ or I can write $$30=2*15$$, maybe this can do using congruence bit I stuck there if I use that $$4n\equiv x \pmod{30}$$, and I can write $$n\equiv x\pmod{2*15}$$, since $$n\equiv 7 \pmod{15}$$ and using little Fermat's little theorem $$n\equiv 1 \pmod 2$$ so then $$n\equiv 7 \pmod{30}$$ is this ok?

Rename $$k_1\to a$$ and $$k_2 \to b$$. We have: $$6a +4 = 15b+7\implies 2a=5b+1 \implies b=2c+1$$ So $$n = 15(2c+1)+7 = 30c+22$$ so $$x=22$$.

$$n\equiv4\pmod6\implies n\equiv4\pmod3\equiv1\ \ \ \ (1)$$

$$n\equiv4\pmod6\implies n\equiv4\pmod2\equiv0\ \ \ \ (2)$$

$$n\equiv7\pmod{15}\implies n\equiv7\pmod3\equiv1\ \ \ \ (1)$$

$$n\equiv7\pmod{15}\implies n\equiv7\pmod5\equiv2\ \ \ \ (3)$$

Apply Chinese Remainder Theorem on $$(1),(2),(3)$$

Alternatively,

$$n\equiv7\pmod{15}\implies n=15k+7$$ where $$k$$ is any integer

$$15k+7\equiv k+1\pmod2\implies k$$ must be odd $$=2m+1$$(say)

$$n=15(2m+1)+7$$

• Perhaps it should be mentioned explicitly that the remainders are indeed compatible, as the two remainders mod 3 coincide. This is not always the case. The second approach as written would also work if the first remainder were 2. – LutzL Nov 10 '18 at 9:36
• @LutzL, Thanks for your valuable feedback – lab bhattacharjee Nov 10 '18 at 9:54

$$n\equiv 7\pmod{\!15}\!\iff\! n\equiv 7,\color{#c00}{22}\pmod{\!30}\,$$ $$\Rightarrow\,n\equiv 1,\color{#c00}4\pmod{6}$$

Numbers that have remainder $$4$$ by division with $$6$$ are $$...-8,~-2,~4,~ 10,~ 16,~ 22,~ 28,~ 34,~ 40,~ 46,~ 52,~ 58,~...$$ Numbers that have remainder $$7$$ by division with $$15$$ are $$...,-8,~ 7,~ 22,~ 37,~ 52,~ ...$$ Common in both sequences are $$-8,~ 22,~ 52$$ Now detect and confirm the pattern.

Alternatively: $$n\equiv 4 \pmod{6} \Rightarrow 5n\equiv 20 \pmod{30};\\ n\equiv 7 \pmod{15} \Rightarrow 2n\equiv 14 \pmod{30}.$$ Add the two: $$7n \equiv 34\equiv 4 \pmod{30} \Rightarrow \\ 91n\equiv n\equiv 52 \equiv 22 \pmod{30}.$$

• If you take the difference here you get $3n\equiv 6 \bmod 30$ and since $3$ is a factor of $30$ you get $n\equiv 2 \bmod 10$ which offers $2, 12 , 22$ to try in the original equations. – Mark Bennet Nov 10 '18 at 12:12
• @MarkBennet, thank you for suggesting the good shortcut, but I want to minimize wordiness and make it self-explanatory. – farruhota Nov 10 '18 at 13:48
• @Mark & farruhota Also, because $\,\ldots \Rightarrow 7n\equiv 4$ is a unidirectional arrow, the argument only deduces that $\,n\equiv 22\,$ is necessary. It need not be sufficient, so we need to check it is a solution. (vs. an extraneous root). This is a common beginner error so it is worth explicit mention in answers. But here it is simpler to check the two possibilities $n\equiv 7\pmod{\!15}\!\iff\! n\equiv 7,\color{#c00}{22}\pmod{\!30}\,$ as in my answer. – Bill Dubuque Nov 10 '18 at 16:52
• @BillDubuque Noted: you will see that in my comment I did refer to checking back in the original equations. And yes, reducing more quickly to two possibilities rather than three is more efficient. – Mark Bennet Nov 10 '18 at 17:00
• @Mark Yes, I saw that. For balance - I sought to "maximize wordiness" to help readers avoid that pitfall! – Bill Dubuque Nov 10 '18 at 17:06