Smallest positive integer that when divided by 23 has 20 as remainder and 34 remainder when divided by 41.

Question

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.

Answer 1

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

Answer 2

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

Answer 3

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.