<-- Prev

Modular Arithmetic

Next -->
  • Chinese Remainder Theorem
    40 pts · 7876 Solves · 47 Solutions
    The Chinese Remainder Theorem gives a unique solution to a set of linear congruences if their moduli are coprime.

    This means, that given a set of arbitrary integers $a^{i}$, and pairwise coprime integers $n^{i}$, such that the following linear congruences hold:

    Note "pairwise coprime integers" means that if we have a set of integers $\{n^{1}, n^{2}, ..., n^{i}\}$, all pairs of integers selected from the set are coprime: $\gcd(n^{i}, n^{j}) = 1$.

    $x \equiv a^{1} \mod n^{1}$
    $x \equiv a^{2} \mod n^{2}$
    $\ldots$
    $x \equiv a^{n} \mod n^{n}$


    There is a unique solution $x \equiv a \mod N$ where $N = n^{1} \cdot n^{2} \cdot ... \cdot n^{n}$.

    In cryptography, we commonly use the Chinese Remainder Theorem to help us reduce a problem of very large integers into a set of several, easier problems.

    Given the following set of linear congruences:

    $x \equiv 2 \mod 5$
    $x \equiv 3 \mod 11$
    $x \equiv 5 \mod 17$


    Find the integer $a$ such that $x \equiv a \mod 935$

    Starting with the congruence with the largest modulus, use that for $x \equiv a \mod p$ we can write $x = a + k \cdot p$ for arbitrary integer $k$.

    You must be logged in to submit your flag.


Level Up

level up icon

You are now level Current level