4
$\begingroup$

The textbook that I'm using explicitly says to solve it without using the Chinese remainder theorem(or modular arithmetic for that case).

Any help/hint would be appreciated.

Edit: Upon reviewing the question, the book resolution does in fact use the CRT despite it imposing the restriction(The error has already been reported to the professor). Nevertheless user's u/Ilovemath answer still stands and is greatly appreciated.

$\endgroup$
1
  • 1
    $\begingroup$ Well, what technique does your book recommend then? I guess you could always just brute force it... $\endgroup$
    – Eric
    Commented Sep 6, 2021 at 2:03

3 Answers 3

5
$\begingroup$

The sequence of numbers leaving remainder $34$ when divided by $41$ is $$34, 75, 116.....$$ which is an arithmetic progression with common difference $41$.

Similarly, the sequence of numbers leaving remainder $20$ when divided by $23$ is $$20, 43, 66....$$ which is also an arithmetic progression with common difference 23.

We need to find the smallest number common to both sequences.

If that number is the $mth$ term of first sequence and $nth$ of the second, $$34+(m-1)41=20+(n-1)23$$ Hence, we have $41m=23n+4$. Or $46m=23n+5m+4$.

From here, we observe that $5m+4$ should be divisible by $23$.

Smallest such $m$ is $13$. Hence the answer is $34+(13-1)41=526$.

$\endgroup$
1
$\begingroup$

Check out the chinese remainder theorem, it tells you exactly when such systems of congruences have solutions (and gives a formula for the solution).

$\endgroup$
1
  • 2
    $\begingroup$ OP explicitly mentioned that use of CRT is disallowed. $\endgroup$ Commented Sep 6, 2021 at 2:06
0
$\begingroup$

No chinese remainder theorem: Your problem can be stated:

$\begin{align*} x &\equiv 20 \pmod{23} \\ x &\equiv 34 \pmod{41} \end{align*}$

This is $x = 23 a + 20 = 41 b + 34$ for some $a, b$. Consider this last equation modulo 41:

$\begin{align*} 23 a + 20 &\equiv 41 b + 34 \pmod{41} \\ &\equiv 34 \pmod{41} \\ 23 a &\equiv 14 \pmod{41} \\ a &\equiv 25 \cdot 14 \pmod{41} && \text{since $23 \cdot 25 = 575 \equiv 1 \pmod{41}$} \\ &\equiv 22 \end{align*}$

The value of $b$ is obtained similarly.

$\endgroup$

You must log in to answer this question.

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