0
$\begingroup$

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.

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

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

$\endgroup$
  • $\begingroup$ Thanks for the input. Why do you conclude that $1234 \equiv z \mod 5 \Rightarrow z \equiv 4 \mod 5$ ? $\endgroup$ – Fernando Gómez May 7 '18 at 7:03
  • $\begingroup$ $1234 = 5\times 246 + 4$ so $1234 \equiv 4 \bmod 5$ $\endgroup$ – Joffan May 7 '18 at 7:27
  • $\begingroup$ 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? $\endgroup$ – Fernando Gómez May 7 '18 at 17:15
  • $\begingroup$ It's not right. See update. $\endgroup$ – Joffan May 7 '18 at 17:50
  • $\begingroup$ 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. $\endgroup$ – Fernando Gómez May 7 '18 at 22:51

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.