Find the smallest number that has a residue of 3 when divided by 5, and a residue of 4 when divided by 6 or 7 (without using modular arithmetic).

Question

I am not too sure how to tackle this without trial and error. I know I can write $n=5a+3=6b+4=7c+4$, however, where do I go next?

Answer 1

$6b + 4 \ne 7b +4$. then number so that $n = 6*(something) + 4$ is probably a different number then then number so that $n = 7*(something) + 4$.

So there are $a,b,c$ so that

$n = 5a + 3 = 6b + 4=7c + 4$

Also you ask for the smallest. There are infinite positive and infinite negative answers so I'm assuming $n$ is meant to be natural?

$6b = 7c$ so $6|c$ and $7|b$ and there is a $k$ so that $b=7k$ and $6b = 42k = 7c$ and $c = 6k$.

So $n = 5a + 3 = 42k + 4$

So $5a = 42k + 1$. And $42k + 1 = 40k + 2k +1$ so $5|2k+1$. Well.... I suppose it is trial and error but if we assume $k$ is non-negative the smallest way to do that is if $2k + 1 =5$ or $k = 2$.

$5a = 42*2 + 1 = 85$ and $a = 17$.

So $n = 5*17 + 3 = 42*2 + 4 = 88$

And indeed $88 \equiv 3 \pmod 5$ and $4\pmod 6$ and $4 \pmod 7$.

And it is the least non-negative as $k=2$ was the least non-negative value.

(Note: And $88 + 5*6*7m = 88+210m$ including $88-210=-122$ will do.)

Answer 2

If $n$ has a remainder of $4$ when divided by $6$ and $7$, then $n-4$ has a reminder of $0$, i.e. $n-4$ is a multiple of $6$ and $7$. The lowest common multiple of $6$ and $7$ is $42$, so $n-4$ is a multiple of $42$.

The smallest positive value of $n$ which leaves a remainder of $4$ when divided by $6$ or $7$ is therefore $0\times 42+4=4$. But this doesn't have the right remainder when divided by $5$. The next is $1\times 42+4=46$, which also doesn't work. The next is $2\times 42 +4=88$. This does give remainder $3$ when divided by $5$, so it is the answer.

Answer 3

Alternatively, using the division theorem

For $5*6*7=210$

So for $n$ there is unique $q, r;0\le r < 210$ so that $n = 210q + r$.

But $r$ itself can by divided by $5*6=30$; $5*7=35$ and $6*7=42$ so

$r = 30a + r_1; 0\le r_1< 30$ and as $r <210$, $0\le a < 7$

$r = 35b + r_2; 0 \le r_2< 35$ and $0\le b < 6$

And $r= 42c + r_3; 0\le r_3 < 42$ and $0\le c < 5$.

And so we have three equations for $n$:

$n = 210q +30a + r_1$

$n = 210q +35b + r_2$

$n = 210q +42c + r_3$

Furthermore we can divide $r_1,r_2,r_3$ by $5,6,7$ to get the following six equations.

$n = 210q +30a + 6d + 4$

$n = 210q +30a + 5e + 3$

$n = 210q +35b + 7f + 4$

$n = 210q +35b + 5g + 3$

$n = 210q +42c + 7h + 4$

$n = 210q +42c + 6i + 4$

With the restrictions: $0\le a < 7;0\le b < 6;0\le c < 5;0\le d< 5;0\le e< 6; 0\le f< 5; 0\le g < 7;0\le h< 6;0\le i< 7$.

So we have

$6d+1 = 5e$

$7f+1 = 5g$

$7h = 6i$

But given the restictions these each have only one solution $d=4;e=5; f=2;g=3;h=6;i=7$.

so we have

$30a +28 = 35b + 18 = 42c + 4$.

But $30a + 28 = 35b +18$ means $30a +10=35b$ or $6a+2=7b$

And $35b + 18 = 42 c + 4$ means $35b+14 = 42c$ or $5b+2=6c$.

And $30a + 28 = 42c+4$ means $30a+24=42c$ or $5a+4=7c$.

But given the restrictions these each have only one solution: $a=2;b=2$ and $b=2; c=2$ and $a=2;c=2$.

So $n = 210q + 60 + 28 = 210q + 70 + 18 = 210q + 84 + 4 = 210q + 88$.