# How to solve this modular equation?

Find the smallest possible $n$ such that $n \equiv 1 \mod 5$ and $n \equiv 3 \mod 7$.

The only method that I can think of to solve this is write out the two sequences defined by the $k$th terms $5k+1$ and $7k+3$, where $k$ is any positive real integer, and the smallest value in both sequences would be the solution.

Is there a better method that would work for larger values?

• not really, because you can have $n=5k+1$ and $n=7l+3$ for some integers $k\neq l$. Other than that, you are on the right track! – Ferra Nov 10 '15 at 22:56
• which comes to solving for integers an equation of the type $ax + by = c$, In this case $(a, b) = 1$ and you will have infinitely many solutions. You can pick whatever solution suits your needs. There are well known ways like the Euclidean Algorithm which aid in solving these. – Shailesh Nov 10 '15 at 23:04
• Your method is exactly the method I use when the two moduli ($5$ and $7$ in this case) are not too big. As far as I’m concerned, just the numbers $\equiv3\pmod7$ in order will do the trick: you can see at a glance the first one whose decimal representation ends in $1$ or $6$. – Lubin Nov 10 '15 at 23:09
• Thank you for the clarification that this is the correct approach for smaller integer values. That is a good observation. @Shailesh Yes, it is clear that there are infinitely many solutions for $n$, hence in this question I am trying to find the smallest. – Max Goodridge Nov 10 '15 at 23:21
• What do you call a "real integer" ??? – Yves Daoust Nov 12 '15 at 9:39

We have the obvious *Bézout's identity: $\;3\cdot 5-2\cdot 7 =1$. The solution of the system of congruences $$\begin{cases}n\equiv \color{cyan}1\mod5\\n\equiv \color{red}3\mod 7\end{cases}\quad \text{is}\enspace n\equiv \color{red}3\cdot3\cdot 5-\color{cyan}1\cdot2\cdot 7\equiv 31\mod 35$$
In brief, "a better method" uses the Chinese Remainder Theorem with $5,7$ as the primes. It is not necessarily more simple...
You should find an integer $a \leftrightarrow (1,0)$ (i.e. $a \equiv 1 \bmod 5$, $a \equiv 0 \bmod 7$) and $b \leftrightarrow (0,1)$. Then your $n = 1\cdot a + 3\cdot b$, maybe also $\bmod (5\cdot7)$ - I don't remember exactly.
How to find $a$?
$a = 7k \equiv 1 \bmod 5$ - solve for $k$ using the Extended Euclidian algorithm.