2
$\begingroup$

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?

$\endgroup$
1
$\begingroup$

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

$\endgroup$
1
$\begingroup$

$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$

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – LutzL Nov 10 '18 at 9:36
  • $\begingroup$ @LutzL, Thanks for your valuable feedback $\endgroup$ – lab bhattacharjee Nov 10 '18 at 9:54
1
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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}.$$

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Mark Bennet Nov 10 '18 at 12:12
  • $\begingroup$ @MarkBennet, thank you for suggesting the good shortcut, but I want to minimize wordiness and make it self-explanatory. $\endgroup$ – farruhota Nov 10 '18 at 13:48
  • $\begingroup$ @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. $\endgroup$ – Bill Dubuque Nov 10 '18 at 16:52
  • $\begingroup$ @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. $\endgroup$ – Mark Bennet Nov 10 '18 at 17:00
  • $\begingroup$ @Mark Yes, I saw that. For balance - I sought to "maximize wordiness" to help readers avoid that pitfall! $\endgroup$ – Bill Dubuque Nov 10 '18 at 17:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.