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

elementary-number-theory

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.

Best Answer

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