2
$\begingroup$

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?

$\endgroup$
  • 1
    $\begingroup$ 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! $\endgroup$ – Ferra Nov 10 '15 at 22:56
  • $\begingroup$ 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. $\endgroup$ – Shailesh Nov 10 '15 at 23:04
  • $\begingroup$ 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$. $\endgroup$ – Lubin Nov 10 '15 at 23:09
  • $\begingroup$ 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. $\endgroup$ – Max Goodridge Nov 10 '15 at 23:21
  • $\begingroup$ What do you call a "real integer" ??? $\endgroup$ – Yves Daoust Nov 12 '15 at 9:39
2
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$
1
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ That should do the trick. Thanks! $\endgroup$ – Max Goodridge Nov 10 '15 at 23:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.