0
$\begingroup$

Find the smallest positive $N$ such that \begin{align*} N &\equiv 3 \pmod{4}, \\ N &\equiv 2 \pmod{5}, \\ N &\equiv 6 \pmod{7}. \end{align*}

I got 69 as the answer but with a check, it's not correct. Am I at least close? Could someone provide a solution? Thanks!

$\endgroup$
2
$\begingroup$

$$N = 4p + 3$$

$$N \equiv 2 \pmod{5}$$

$$4p + 3 \equiv 2 \pmod{5}$$

$$4p \equiv 4 \pmod{5}$$

$$p \equiv 1 \pmod{5}$$

We find this by finding the inverse of 4 mod 5 (the 4 chosen is the coefficient of p on the left).

$$N = 4(1)+3 \pmod{4 * 5}$$

$$N \equiv 7 \pmod{20}$$

$$N = 20q + 7$$

$$N \equiv 6 \pmod{7}$$

$$20q + 7 \equiv 6 \pmod{7}$$

$$20q \equiv 6 \pmod{7}$$

$$6q \equiv 6 \pmod{7}$$

$$q \equiv 1 \pmod{7}$$

$$N \equiv 20(1)+7 \pmod{20*7}$$

$$N \equiv 27 \pmod{140}$$

$$N = 27$$

$\endgroup$
1
$\begingroup$

Hint $N+1$ needs to be divisible by $4$ and $7$ thus $28$, and $$N+1 \equiv 3 \pmod{5}$$

Look now for the smallest multiple of $28$ which has a remainder of $3$ when divided by $5$ and subtract 1.

Hint 2: $28=5\cdot 5+3$

$\endgroup$
0
$\begingroup$

$N+1$ has to be a multiple of $4\cdot 7= 28$ that is $\equiv 3\pmod{5}$.
Since $28$ is actually $\equiv 3\pmod{5}$, the smallest positive solution is given by $N=\color{red}{27}$.

$\endgroup$
0
$\begingroup$

You first solve $\;\begin{cases}n\equiv3\mod 4,\\n\equiv2\mod 5.\end{cases}$.

For this you need a Bézout's relation between $4$ and $5$. We have one at hand: $\; 5-4=1$. Hence the solutions are: $$n\equiv 3\cdot5-2\cdot 4=7\mod 4\cdot 5=20.$$ Then you solve $\;\begin{cases}N\equiv7\mod 20,\\N\equiv6\mod 7.\end{cases}$ A Bézout's relation between $20$ and $7$ is $\;3\cdot 7-20=1$. Hence the solutions are $$N\equiv 7\cdot 3\cdot 7-6\cdot 20=27\pmod{140}.$$ The smallest positive integer in this congruence is $20$.

$\endgroup$
0
$\begingroup$

last digit of N due to first condition should be either 1,3,5,7. due to second condition last digit should be either 7,2. so to satisfy both conditions it should end with 7. the smallest number ending with 7 satisfying third condition is 27.

$\endgroup$

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.