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$

5 Answers 5

Reset to default
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$
2
  • $\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$
    – Lutz Lehmann
    Nov 10, 2018 at 9:36
  • $\begingroup$ @LutzL, Thanks for your valuable feedback $\endgroup$
    – lab bhattacharjee
    Nov 10, 2018 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$
8
  • $\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, 2018 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, 2018 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, 2018 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, 2018 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, 2018 at 17:06

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .