# Find lesses positive integer that satisfies a congruence

I found this exercise in a book, but I don't even know how to start tackling it.

Find the lesser positive integer z such that:

$1234 \equiv z \mod 5$

$2^{240} \equiv z \mod 3$

Looking at their definitions, I can say that $1234 \equiv z \mod 5$ $\implies$ $5 | 1234-z$, which implies that $1234-z=5c$ for some integer $c$. Likewise, $2^{240} \equiv z \mod 3$ $\implies$ $3|2^{240}-z$, which implies that $2^{240}-z=3d~$ for some integer $d$.

I don't know where to go from here. I deduced $1234-5c=2^{240}-3d$, but I'm not sure how does that help me. I'm also unsure about the "lesser" condition.

Any hint will be really appreciated. Thanks in advance.

• Your second equation is $\bmod 3$ though? – Joffan May 7 '18 at 3:39
• @Joffan Yes, corrected it, sorry. – Fernando Gómez May 7 '18 at 7:05

$1234 \equiv z \mod 5$, so $z\equiv 4\bmod 5$

$2^{240} \equiv z \mod 3$, and $2^2 = 4\equiv 1 \bmod 3$, so $z\equiv (2^2)^{120} \equiv 1^{120} \equiv 1 \bmod 3$

So: given

\begin{align} z \equiv 4\bmod 5\\ z \equiv 1 \bmod 3\\ \end{align}

and we can certainly find a solution$\bmod 15$ through the Chinese remainder theorem. For these small numbers we can just use examination:

$z \equiv 4\bmod 5 \implies z\in\{4,9,14\} \bmod 15$
$z \equiv 1\bmod 3 \implies z\in\{1,4,7,10,13\} \bmod 15$

and we have $z\equiv 4 \bmod 15$ and $z=4$ as the smallest positive solution.

• Thanks for the input. Why do you conclude that $1234 \equiv z \mod 5 \Rightarrow z \equiv 4 \mod 5$ ? – Fernando Gómez May 7 '18 at 7:03
• $1234 = 5\times 246 + 4$ so $1234 \equiv 4 \bmod 5$ – Joffan May 7 '18 at 7:27
• thanks for the clarification. I wished I could see the apparent answer... What I worked out is, from the congruences you gave (which, I think, I followed well after your clarification), from the definitions: $$5|z-4 \Rightarrow 5k = z-4 \\ 3|z-1 \Rightarrow 3k = z-3 \\ \\ 3(z-4) = 5(z-3) \\ 3z-12=5z-15 \\ -12+15=5z-2z \\ 3=3z \\ z=1 \\$$ But it doesn't feel right... am I correct? – Fernando Gómez May 7 '18 at 17:15
• It's not right. See update. – Joffan May 7 '18 at 17:50
• Thanks @Joffan so what I see is that 4, 9 and 14 are the only numbers that fit $z \equiv 4 \mod 5$ and 1, 4, 7, 13 are the only numbers that fit $z \equiv 1 \mod 3$ and then you are taking the lesser, and only, number shared by both sets, which is 4. Is that right? I'm sorry, I haven't grasped the congruence/modulo concept fully, I know the definitions but conceptually still have to visualize it in my mind. I'll keep doing exercises. Thanks again. – Fernando Gómez May 7 '18 at 22:51