# Simplifying two simultaneous modular arithmetic equations

For example, say I have two equations for $n$:

$n\equiv 1 \mod 2$ and $n\equiv 1 \mod 3$

I can show that $n \equiv 1 \mod 6$ by saying that:

$n \equiv 1, 3, 5 \mod 6$ and $n \equiv 1, 4 \mod 6$ using the previous two equations, and then seeing that $1$ is the only remainder both equations share.

However, I would like to know if there is a simpler way to perform simplify these simultaneous equations (ideally one that could be executed quickly by code).

Please note that I am interested in a method for solving the generalised form of the equations (ie. $n\equiv 1 \mod a$ and $n\equiv 1 \mod b$)

• what's wrong with $n\equiv 1 \pmod {12}$? (or more simply, just note that the full solution is given by $n\equiv 1 \pmod 6$).
– lulu
Commented May 6, 2017 at 11:21
• You might want to read about the Chinese Remainder Theorem and methods to solve it in practice.
– lulu
Commented May 6, 2017 at 11:22
• @lulu Thank you I have fixed the question Commented May 6, 2017 at 11:24
• To solve the general case, note that $k=0\bmod a$ and $k=0\bmod b$ is equivalent to $k=0\bmod c$ where $c$ is the lowest common multiple of $a$ and $b$. Hence $n=1\bmod a$ and $n=1\bmod b$ is equivalent to $n=1\bmod c$.
– Did
Commented May 6, 2017 at 13:29

$n\equiv 1$ (mod $a$) and $n\equiv 1$ (mod $b$) if and only if $n-1$ is divisible by both $a$ and $b$, i.e. $n-1$ is divisible by the L.C.M. of $a$ and $b$.
Let $l$ be the L.C.M. of $a$ and $b$. The solution is
$$n\equiv 1 \mod l$$
from the two equations we have $$n=1+2k$$ and $$n=1+3p$$ thus we get $$k=\frac{3}{2}p$$ and $p$ must be evan, setting $$p=2a$$ and the solution is $$n=1+6a$$ with an integer number $a$ sorry for my mistake.