0
$\begingroup$

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

$\endgroup$
4
  • 4
    $\begingroup$ 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$). $\endgroup$
    – lulu
    Commented May 6, 2017 at 11:21
  • 5
    $\begingroup$ You might want to read about the Chinese Remainder Theorem and methods to solve it in practice. $\endgroup$
    – lulu
    Commented May 6, 2017 at 11:22
  • $\begingroup$ @lulu Thank you I have fixed the question $\endgroup$
    – Ronikos
    Commented May 6, 2017 at 11:24
  • $\begingroup$ 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$. $\endgroup$
    – Did
    Commented May 6, 2017 at 13:29

2 Answers 2

1
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ Did you read the last paragraph of the question? How are you addressing it? $\endgroup$
    – Did
    Commented May 6, 2017 at 13:28

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .