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

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.

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

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

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

• OP explicitly mentioned that use of CRT is disallowed. Commented Sep 6, 2021 at 2:06

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.