0

Say I have a number of equations, all with different modulos, but two numbers that are congruent under all of them, that all contain a variable I want to solve for, like for instance:

$1 = n\ (\text{mod } 2)\\ 1 = n\ (\text{mod } 3)\\ 1 = n\ (\text{mod } 5)\\ 0 = n\ (\text{mod } 7)$

Now I know

$2 |(n-1)\\ 3 | (n-1)\\ 5 | (n-1)\\ 7 | n$

Ok so I can write $n \equiv_2 1 \equiv_3 n \equiv_5 1$... not particularly useful... I also know

$\frac{n}{2}=x_1 +1\\ \frac{n}{3}=x_2 +1\\ \frac{n}{5}=x_3 +1$

But that does not get me anywhere either, as that is not solvable (I think).

So, how does one actually go about solving for $n$?

user3578468
  • 1,371

1 Answers1

1

This is an example of the Chinese Remainder Theorem. Many of the references that describe the theorem will also explain how to solve problems of this kind.

This example is relatively simple because three of the four divisors all give the same remainder. You therefore have one number, $n-1$, which is divisible by all three of the primes $2$, $3$, and $5$. What happens when you divide $n-1$ by the product of those three primes?

The fourth divisor has to be handled in a separate step, but by that point it's reasonable to finish this example by trial and error.

David K
  • 98,388