0

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

Ronikos
  • 596
  • 1
  • 4
  • 14
  • 4
    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 May 06 '17 at 11:21
  • 5
    You might want to read about the Chinese Remainder Theorem and methods to solve it in practice. – lulu May 06 '17 at 11:22
  • @lulu Thank you I have fixed the question – Ronikos May 06 '17 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 May 06 '17 at 13:29

2 Answers2

1

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

CY Aries
  • 23,393
0

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.

Dr. Sonnhard Graubner
  • 95,283