avewright/proofwiki-math huggingface dataset:
Theorem: Divisor Count of Square-Free Integer is Power of 2

Let $n$ be a square-free integer.
Let $\sigma_0: \Z \to \Z$ be the divisor count Function.
Then $\map {\sigma_0} n = 2^r$ for some $r \ge 1$.
The converse is not true in general.
That is, if $\map {\sigma_0} n = 2^r$ for some $r \ge 1$, it is not necessarily the case that $n$ is square-free.

Proof:
Let $n$ be an integer such that $n \ge 2$.
Let the prime decomposition of $n$ be:
:$n = p_1^{k_1} p_2^{k_2} \dotsm p_r^{k_r}$
Then from Divisor Count Function from Prime Decomposition we have that:
:$\ds \map {\sigma_0} n = \prod_{i \mathop = 1}^r \paren {k_i + 1}$
Let $n$ be square-free.
Then by definition:
:$\forall i: 1 \le i \le r: k_i = 1$
So:
:$\ds \map {\sigma_0} n = \prod_{i \mathop = 1}^r \paren {1 + 1} = 2^r$
The statement about the converse is proved by counterexample:
Let $n = p^3$ where $p$ is prime.
Then $n$ is not square-free as $p^2 \divides n$.
However:
:$\map {\sigma_0} n = 3 + 1 = 2^2$
{{qed}}
Category:Divisor Count Function
Category:Square-Free Integers
2pu6ljen7a8b684ullbnyqv40kmzyhm
Theorem: Divisor Count Function is Odd Iff Argument is Square

Let $\sigma_0: \Z \to \Z$ denote the divisor count function.
Then $\map {\sigma_0} n$ is odd {{iff}} $n$ is square.

Proof:
Let $n$ be an integer such that $n \ge 2$.
Let the prime decomposition of $n$ be:
:$n = p_1^{k_1} p_2^{k_2} \dotsm p_r^{k_r}$
Then from Divisor Count Function from Prime Decomposition we have that:
:$\ds \map {\sigma_0} n = \prod_{i \mathop = 1}^r \paren {k_i + 1}$
Theorem: Divisor Sum is Odd iff Argument is Square or Twice Square

Let $\sigma_1: \Z \to \Z$ be the divisor sum function.
Then $\map {\sigma_1} n$ is odd {{iff}} $n$ is either square or twice a square.

Proof:
Let $n$ be an integer such that $n \ge 2$.
Let the prime decomposition of $n$ be:
:$n = p_1^{k_1} p_2^{k_2} \ldots p_r^{k_r}$
Then:
{{begin-eqn}}
{{eqn | l = \map {\sigma_1} n
      | r = \prod_{i \mathop = 1}^r \frac {p_i^{k_i + 1} - 1} {p_i - 1}
      | c = Divisor Sum of Integer
}}
{{eqn | r = \prod_{i \mathop = 1}^r \paren {1 + p_i + p_i^2 + \ldots + p_i^{k_i} }
      | c = Sum of Geometric Sequence
}}
{{end-eqn}}
Let $\map {\sigma_1} n$ be odd.
Then all factors of $\ds \prod_{i \mathop = 1}^r \paren {1 + p_i + p_i^2 + \ldots + p_i^{k_i} }$ are odd (and of course $\ge 3$).
For $1 + p_i + p_i^2 + \ldots + p_i^{k_i}$ to be odd, one of two conditions must hold:
:$p_i$ is even (so that all terms of $1 + p_i + p_i^2 + \ldots + p_i^{k_i}$ are even except the $1$);
:$k_i$ is even (so that $1 + p_i + p_i^2 + \ldots + p_i^{k_i}$ has an odd number of odd terms).
In the first case, that means $p_i^{k_i}$ is a power of $2$.
In the second case, that means $p_i^{k_i}$ is a square.
The result follows.
The argument reverses.
{{qed}}
Category:Square Numbers
Category:Divisor Sum Function
Category:Odd Integers
kynkqvfcic11rqm91tfxbfvvlp1rmif
Theorem: Number of Quadratic Residues of Prime

Let $p$ be an odd prime.
Then $p$ has $\dfrac {p - 1} 2$ quadratic residues and $\dfrac {p - 1} 2$ quadratic non-residues.
The quadratic residues are congruent modulo $p$ to the integers $1^2, 2^2, \ldots, \paren {\dfrac {p - 1} 2}$.

Proof:
The quadratic residues of $p$ are the integers which result from the evaluation of the squares:
:$1^2, 2^2, \ldots, \paren {p - 1}^2$ modulo $p$
But:
:$r^2 = \paren {-r}^2$
and so these $p - 1$ integers fall into congruent pairs modulo $p$, namely:
{{begin-eqn}}
{{eqn | l = 1^2
      | o = \equiv
      | r = \paren {p - 1}^2
      | rr= \pmod p
}}
{{eqn | l = 2^2
      | o = \equiv
      | r = \paren {p - 2}^2
      | rr= \pmod p
}}
{{eqn | o = \ldots
}}
{{eqn | l = \paren {\frac {p - 1} 2}^2
      | o = \equiv
      | r = \paren {\frac {p + 1} 2}^2
      | rr= \pmod p
      | c = Note that we require $p$ to be odd here.
}}
{{end-eqn}}
Therefore each quadratic residue of $p$ is congruent modulo $p$ to one of the $\dfrac {p - 1} 2$ integers $1^2, 2^2, \ldots, \paren {\dfrac {p - 1} 2}^2$.
Note that as $r^2 \not \equiv 0 \pmod p$ for $1 \le r < p$, the integer $0$ is not among these.
All we need to do now is show that no two of these integers are congruent modulo $p$.
So, suppose that $r^2 \equiv s^2 \pmod p$ for some $1 \le r \le s \le \dfrac {p - 1} 2$.
What we are going to do is prove that $r = s$.
Now $r^2 \equiv s^2 \pmod p$ means that $p$ is a divisor of $r^2 - s^2 = \paren {r + s} \paren {r - s}$.
From Euclid's Lemma either:
:$p \divides \paren {r + s}$
or:
:$p \divides \paren {r - s}$
$p \divides \paren {r + s}$ is impossible as $2 \le r + s \le p - 1$.
Take $p \divides \paren {r - s}$.
As $0 \le r - s < \dfrac {p - 1} 2$, that can happen only when:
:$r - s = 0$
or:
:$r = s$
So there must be exactly $\dfrac {p - 1} 2$ quadratic residues.
That means there must also be exactly $\dfrac {p - 1} 2$ quadratic non-residues.
{{qed}}
Category:Prime Numbers
Category:Quadratic Residues
04d8e6nlo19361e9x2as2pc5p1ovuox
Theorem: Cancellability of Congruences

Let $a, b, c, n \in \Z$ be integers.
Then:
:$c a \equiv c b \pmod n \iff a \equiv b \pmod {n / d}$
where $d = \gcd \set {c, n}$.

Proof:
Let $c a \equiv c b \pmod n$.
Then we have that $c a - c b = k n$ for some $k \in \Z$ by definition of congruence.
Now $d = \gcd \set {c, n}$, so from Integers Divided by GCD are Coprime we have:
:$\exists r, s \in Z: r \perp s: c = d r, n = d s$
So we substitute for $c$ and $n$ in $c a - c b = k n$:
:$d r a - d r b = k d s$
which leads us to:
:$r \paren {a - b} = k s$
So $s \divides \paren {a - b}$ and as $r \perp s$, from Euclid's Lemma $s \divides \paren {a - b}$.
So $a \equiv b \pmod s$ where $s = \dfrac n d$.
Now suppose $a \equiv b \pmod {n / d}$ where $d = \gcd \set {c, n}$.
Then:
:$\exists k \in \Z: a - b = k \dfrac n d$
Hence:
:$c a - c b = \dfrac {k c} d n$
As $d = \gcd \set {c, n}$ we have $d \divides c$ and so $\dfrac c d \in \Z$.
So:
:$c a \equiv c b \pmod n$
{{qed}}
Category:Modulo Multiplication
Category:Modulo Arithmetic
Category:Cancellability of Congruences
pky8rvdw5ydnippe4xss52lr97tegog
Theorem: Cancellability of Congruences

Let $a, b, c, n \in \Z$ be integers.
Then:
:$c a \equiv c b \pmod n \iff a \equiv b \pmod {n / d}$
where $d = \gcd \set {c, n}$.

Proof:
Recall that $c \perp n$ means $\gcd \set {c, n} = 1$.
The result follows directly from Cancellability of Congruences.
{{qed}}
Theorem: Cancellability of Congruences

Let $a, b, c, n \in \Z$ be integers.
Then:
:$c a \equiv c b \pmod n \iff a \equiv b \pmod {n / d}$
where $d = \gcd \set {c, n}$.

Proof:
We are given that $c$ and $n$ are coprime.
So:
{{begin-eqn}}
{{eqn | q = \exists x, y \in \Z
      | l = c x + n y
      | r = 1
      | c = Integer Combination of Coprime Integers
}}
{{eqn | ll= \leadsto
      | l = 1 - cx
      | r = y n
}}
{{eqn | n = 1
      | l = c x
      | o = \equiv
      | r = 1
      | rr= \pmod n
      | c = {{Defof|Congruence (Number Theory)|subdef = Integer Multiple|Congruence}}
}}
{{end-eqn}}
Then:
{{begin-eqn}}
{{eqn | l = a
      | o = \equiv
      | r = a
      | rr= \pmod n
      | c = Equal Numbers are Congruent
}}
{{eqn | n = 2
      | ll= \leadsto
      | l = a c x
      | o = \equiv
      | r = a
      | rr= \pmod n
      | c = Modulo Multiplication is Well-Defined and from $(1)$
}}
{{eqn | l = b
      | o = \equiv
      | r = b
      | rr= \pmod n
      | c = Equal Numbers are Congruent
}}
{{eqn | n = 3
      | ll= \leadsto
      | l = b c x
      | o = \equiv
      | r = b
      | rr= \pmod n
      | c = Modulo Multiplication is Well-Defined and from $(1)$
}}
{{eqn | n = 4
      | l = x c a
      | o = \equiv
      | r = x c b
      | rr= \pmod n
      | c = Modulo Multiplication is Well-Defined and from $c a \equiv c b \pmod n$
}}
{{end-eqn}}
Thus:
{{begin-eqn}}
{{eqn | l = a
      | o = \equiv
      | r = a c x
      | rr= \pmod n
      | c = from $(2)$ above
}}
{{eqn | o = \equiv
      | r = b c x
      | rr= \pmod n
      | c = from $(4)$ above
}}
{{eqn | o = \equiv
      | r = b
      | rr= \pmod n
      | c = from $(3)$ above
}}
{{end-eqn}}
{{qed}}
Theorem: Cancellability of Congruences

Let $a, b, c, n \in \Z$ be integers.
Then:
:$c a \equiv c b \pmod n \iff a \equiv b \pmod {n / d}$
where $d = \gcd \set {c, n}$.

Proof:
Let:
:$c a \equiv c b \pmod n$
Then by definition of congruence:
:$n \divides k \paren {x - y}$
We have that:
:$c \perp n$
Thus by Euclid's Lemma:
:$n \divides \paren {x - y}$
So by definition of congruence:
:$a \equiv b \pmod n$
{{qed}}
Theorem: Solution of Linear Diophantine Equation

The linear Diophantine equation:
:$a x + b y  = c$
has solutions {{iff}}:
:$\gcd \set {a, b} \divides c$
where $\divides$ denotes divisibility.
If this condition holds with $\gcd \set {a, b} > 1$ then division by $\gcd \set {a, b}$ reduces the equation to:
:$a' x + b' y = c'$
where $\gcd \set {a', b'} = 1$.
If $x_0, y_0$ is one solution of the latter equation, then the general solution is:
:$\forall k \in \Z: x = x_0 + b' k, y = y_0 - a' k$
or:
:$\forall k \in \Z: x = x_0 + \dfrac b d k, y = y_0 - \dfrac a d k$
where $d = \gcd \set {a, b}$.

Proof:
We assume that both $a$ and $b$ are non-zero, otherwise the solution is trivial.
The first part of the problem is a direct restatement of Set of Integer Combinations equals Set of Multiples of GCD:
The set of all integer combinations of $a$ and $b$ is precisely the set of integer multiples of the GCD of $a$ and $b$:
:$\gcd \set {a, b} \divides c \iff \exists x, y \in \Z: c = x a + y b$
Now, suppose that $x', y'$ is any solution of the equation.
Then we have:
:$a' x_0 + b' y_0 = c'$ and $a' x' + b' y' = c'$
Substituting for $c'$ and rearranging:
:$a' \paren {x' - x_0} = b' \paren {y_0 - y'}$
So:
:$a' \divides b' \paren {y_0 - y'}$
Since $\gcd \set {a', b'} = 1$, from Euclid's Lemma we have:
:$a' \divides \paren {y_0 - y'}$.
So $y_0 - y' = a' k$ for some $k \in \Z$.
Substituting into the above gives $x' - x_0 = b' k$ and so:
:$x' = x_0 + b' k, y' = y_0 - a'k$ for some $k \in \Z$
which is what we claimed.
Substitution again gives that the integers:
:$x_0 + b' k, y_0 - a' k$
constitute a solution of $a' x + b' y = c'$ for any $k \in \Z$.
{{qed}}
Theorem: GCD with Prime

Let $p$ be a prime number.
Then:
$\quad \forall n \in \Z: \gcd \set {n, p} = \begin {cases}
p & : p \divides n \\
1 & : p \nmid n
\end {cases}$

Proof:
The only divisors of $p$ are $1$ and $p$ itself by definition.
$\gcd \set {n, p} = p$ {{iff}} $p$ divides $n$.
Hence the result.
{{qed}}
Category:Greatest Common Divisor
Category:Prime Numbers
cp93gzbif27auasul35s4r3x96ixnrr
Theorem: Prime Divides Power

Let $p$ be a prime number.
Let $a, n \in \Z$ be integers.
Then $p$ divides $a^n$ {{iff}} $p^n$ divides $a^n$.

Proof:
=== Sufficient Condition ===
Let $p^n \divides a^n$.
We have $p \divides p^n$ as $p^n = p \paren {p^{n - 1} }$.
From the fact that Divisor Relation is Transitive, we have that $p \divides a^n$.
{{qed|lemma}}
Theorem: Congruence by Divisor of Modulus

Let $z \in \R$ be a real number.
Let $a, b \in \R$ such that $a$ is congruent modulo $z$ to $b$, that is:
:$a \equiv b \pmod z$
Let $m \in \R$ such that $z$ is an integer multiple of $m$:
:$\exists k \in \Z: z = k m$
Then:
: $a \equiv b \pmod m$

Proof:
We are given that $\exists k \in \Z: z = k m$.
Thus:
{{begin-eqn}}
{{eqn | l = a
      | o = \equiv
      | r = b
      | rr= \pmod z
      | c = 
}}
{{eqn | ll= \leadsto
      | q = \exists k' \in \Z
      | l = a
      | r = b + k' z
      | c = {{Defof|Congruence (Number Theory)|Congruence}}
}}
{{eqn | ll= \leadsto
      | l = a
      | r = b + k' k m
      | c = 
}}
{{eqn | l = a
      | o = \equiv
      | r = b
      | rr= \pmod m
      | c = {{Defof|Congruence (Number Theory)|Congruence}}: $k' k$ is an integer
}}
{{end-eqn}}
{{qed}}
Theorem: Congruence of Sum with Constant

Let $a, b, z \in \R$.
Let $a$ be congruent to $b$ modulo $z$:
: $a \equiv b \pmod z$
Then:
:$\forall c \in \R: a + c \equiv b + c \pmod z$

Proof:
Follows directly from the definition of Modulo Addition:
{{begin-eqn}}
{{eqn | l = a
      | o = \equiv
      | r = b
      | rr= \pmod z
      | c = given
}}
{{eqn | l = c
      | o = \equiv
      | r = c
      | rr= \pmod z
      | c = Congruence Modulo Real Number is Equivalence Relation
}}
{{eqn | ll= \leadsto
      | l = a + c
      | o = \equiv
      | r = b + c
      | rr= \pmod z
      | c = {{Defof|Modulo Addition}}
}}
{{end-eqn}}
{{qed}}
Category:Modulo Addition
mcnjhhb8e1wychegup4ic439u6s1c55
Theorem: Congruence of Quotient

Let $a, b \in \Z$ and $n \in \N$.
Let $a$ be congruent to $b$ modulo $n$, that is $a \equiv b \pmod n$.
Let $d \in \Z: d > 0$ such that $d$ is a common divisor of $a, b$ and $n$.
Then:
:$\dfrac a d \equiv \dfrac b d \pmod {n / d}$

Proof:
By definition of congruence modulo $n$:
:$a = b + k n$
Dividing through by $d$ (which you can do because $d$ divides all three terms), we get:
:$\dfrac a d = \dfrac b d + k \dfrac n d$
from which the result follows directly.
{{qed}}
Theorem: Congruence of Quotient

Let $a, b \in \Z$ and $n \in \N$.
Let $a$ be congruent to $b$ modulo $n$, that is $a \equiv b \pmod n$.
Let $d \in \Z: d > 0$ such that $d$ is a common divisor of $a, b$ and $n$.
Then:
:$\dfrac a d \equiv \dfrac b d \pmod {n / d}$

Proof:
From Congruence by Product of Moduli, we have that:
:$\dfrac a d \equiv \dfrac b d \pmod {n / d} \iff d \dfrac a d \equiv d \dfrac b d \pmod {n / d} \iff a \equiv b \pmod n$
{{qed}}
Theorem: Divisibility by 11

Let $N \in \N$ be expressed as:
:$N = a_0 + a_1 10 + a_2 10^2 + \cdots + a_n 10^n$
Then $N$ is divisible by $11$ {{iff}} $\ds \sum_{r \mathop = 0}^n \paren {-1}^r a_r$ is  divisible by $11$.
That is, a divisibility test for $11$ is achieved by alternately adding and subtracting the digits and taking the result modulo $11$.

Proof:
As:
:$10 \equiv -1 \pmod {11}$
we have:
:$10^r \equiv \paren {-1}^r \pmod {11}$
from Congruence of Powers.
Thus:
:$N \equiv a_0 + \paren {-1} a_1 + \paren {-1}^2 a_2 + \cdots + \paren {-1}^n a_n \pmod {11}$
from the definition of Modulo Addition.
The result follows.
{{qed}}
Theorem: Solutions of Polynomial Congruence

Let $\map P x$ be an integral polynomial.
Let $a \equiv b \pmod n$.
Then:
:$\map P a \equiv \map P b \pmod n$
In particular, $a$ is a solution to the polynomial congruence $\map P x \equiv 0 \pmod n$ {{iff}} $b$ is also.

Proof:
Let $\map P x = c_m x^m + c_{m - 1} x^{m - 1} + \cdots + c_1 x + c_0$.
Since $a \equiv b \pmod n$, from Congruence of Product and Congruence of Powers, we have:
:$\forall r \in \Z_{>0}: c_r a^r \equiv c_r b^r \pmod n$
From Modulo Addition we then have:
{{begin-eqn}}
{{eqn | l = \map P a
      | r = c_m a^m + c_{m - 1} a^{m - 1} + \cdots + c_1 a + c_0
      | c = 
}}
{{eqn | o = \equiv
      | r = c_m b^m + c_{m - 1} b^{m - 1} + \cdots + c_1 b + c_0
      | rr= \pmod n
      | c = 
}}
{{eqn | o = \equiv
      | r = \map P b
      | rr= \pmod n
      | c = 
}}
{{end-eqn}}
In particular:
:$\map P a \equiv 0 \iff \map P b \equiv 0 \pmod n$
That is, $a$ is a solution to the polynomial congruence $\map P x \equiv 0 \pmod n$ {{iff}} $b$ is also.
{{qed}}
Category:Polynomial Congruences
o24hsggjadvnecwk7gc8lv6yl4gnkd0
Theorem: Chinese Remainder Theorem

Let $b_1, b_2, \ldots, b_r \in \Z$.
Let $n_1, n_2, \ldots, n_r$ be pairwise coprime positive integers.
Let $\ds N = \prod_{i \mathop = 1}^r n_i$.
Then the system of linear congruences:
{{begin-eqn}}
{{eqn | l = x
      | o = \equiv
      | r = b_1
      | rr= \pmod {n_1}
}}
{{eqn | l = x
      | o = \equiv
      | r = b_2
      | rr= \pmod {n_2}
}}
{{eqn | o = \vdots
}}
{{eqn | l = x
      | o = \equiv
      | r = b_r
      | rr= \pmod {n_r}
}}
{{end-eqn}}
has a solution which is unique modulo $N$:
:$\exists ! a \in \Z_{>0}: x \equiv a \pmod N$

Proof:
=== Existence ===
Let $N_k = \dfrac N {n_k}$ for $k = 1, 2, \ldots, r$.
From Integer Coprime to all Factors is Coprime to Whole:
:$\forall k \in \set {1, 2, \ldots, r}: \gcd \set {N_k, n_k} = \gcd \set {n_1 n_2 \cdots n_{k - 1} n_{k + 1} \cdots n_r, n_k} = 1$
From Solution of Linear Congruence, the linear congruence:
:$N_k x \equiv b_k \pmod {n_k}$
has a unique solution modulo $n_k$.
Let this solution be $x_k$.
That is:
:$(1): \quad N_k x_k \equiv b_k \pmod {n_k}$
for $k = 1, 2, \ldots, r$.
Let $\ds x_0 = \sum_{i \mathop = 1}^r N_i x_i$.
For each $k, i \in \set {1, 2, 3, \ldots, r}$ such that $i \ne k$:
{{begin-eqn}}
{{eqn | l = n_k
      | o = \divides
      | r = N
}}
{{eqn | ll= \leadsto
      | l = n_k
      | o = \divides
      | r = n_i N_i
}}
{{eqn | ll= \leadsto
      | l = n_k
      | o = \divides
      | r = N_i
      | c = Euclid's Lemma
}}
{{eqn | ll= \leadsto
      | l = n_k
      | o = \divides
      | r = N_i x_i
      | c = Divisor Divides Multiple
}}
{{eqn | n = 2
      | ll= \leadsto
      | l = N_i x_i
      | o = \equiv
      | r = 0
      | rr= \pmod {n_k}
      | c = Congruent to Zero iff Modulo is Divisor
}}
{{end-eqn}}
Then for each $k = 1, 2, 3, \ldots, r$:
{{begin-eqn}}
{{eqn | l = x_0
      | o = \equiv
      | r = \sum_{i \mathop = 1}^r N_i x_i
}}
{{eqn | o = \equiv
      | r = N_k x_k
      | c = from $(2)$
}}
{{eqn | o = \equiv
      | r = b_k
      | rr= \pmod {n_k}
      | c = from $(1)$
}}
{{end-eqn}}
Thus $x_0$ is a simultaneous solution.
{{qed|lemma}}
Theorem: Chinese Remainder Theorem

Let $b_1, b_2, \ldots, b_r \in \Z$.
Let $n_1, n_2, \ldots, n_r$ be pairwise coprime positive integers.
Let $\ds N = \prod_{i \mathop = 1}^r n_i$.
Then the system of linear congruences:
{{begin-eqn}}
{{eqn | l = x
      | o = \equiv
      | r = b_1
      | rr= \pmod {n_1}
}}
{{eqn | l = x
      | o = \equiv
      | r = b_2
      | rr= \pmod {n_2}
}}
{{eqn | o = \vdots
}}
{{eqn | l = x
      | o = \equiv
      | r = b_r
      | rr= \pmod {n_r}
}}
{{end-eqn}}
has a solution which is unique modulo $N$:
:$\exists ! a \in \Z_{>0}: x \equiv a \pmod N$

Proof:
Consider $\pi$ only as a homomorphism of groups.
Then Chinese Remainder Theorem (Groups) is applicable as Subgroup of Abelian Group is Normal. 
It remains to demonstrate that the condition $I_i + I_j = R$ for all $i \ne j$ assumed here is equivalent to:
:$\ds \forall k \le n - 1: I_{k + 1} + \bigcap_{i \mathop = 1}^k I_i = R$
The implication from the latter condition is immediate.
For the converse, let $i$ be arbitrary.
The result follows from:
{{begin-eqn}}
{{eqn | l = R
      | r = \prod_{j \mathop \ne i} \paren {I_i + I_j}
      | c = $R$ has a unit and $I_i + I_j = R$ for $j \ne i$
}}
{{eqn | o = \subseteq
      | r = I_i + \prod_{j \mathop \ne i} I_j
      | c = {{Ring-axiom|D}}, {{Defof|Ideal of Ring}}
}}
{{eqn | o = \subseteq
      | r = I_i + \bigcap_{j \mathop \ne i}^n I_j
      | c = Intersection of Ideals of Ring contains Product
}}
{{end-eqn}}
{{qed}}
Theorem: Solution to Simultaneous Linear Congruences

Let:
{{begin-eqn}}
{{eqn | l = a_1 x
      | o = \equiv
      | r = b_1
      | rr= \pmod {n_1}
      | c = 
}}
{{eqn | l = a_2 x
      | o = \equiv
      | r = b_2
      | rr= \pmod {n_2}
      | c = 
}}
{{eqn | o = \vdots
      | c = 
}}
{{eqn | l = a_r x
      | o = \equiv
      | r = b_r
      | rr= \pmod {n_r}
      | c = 
}}
{{end-eqn}}
be a system of simultaneous linear congruences.
This system has a simultaneous solution {{iff}}:
:$\forall i, j: 1 \le i, j \le r: \gcd \set {n_i, n_j}$ divides $b_j - b_i$.
If a solution exists then it is unique modulo $\lcm \set {n_1, n_2, \ldots, n_r}$.

Proof:
We take the case where $r = 2$.
Suppose $x \in \Z$ satisfies both:
{{begin-eqn}}
{{eqn | l = a_1 x
      | o = \equiv
      | r = b_1
      | rr= \pmod {n_1}
      | c = 
}}
{{eqn | l = a_2 x
      | o = \equiv
      | r = b_2
      | rr= \pmod {n_2}
      | c = 
}}
{{end-eqn}}
That is, $\exists r, s \in \Z$ such that:
{{begin-eqn}}
{{eqn | l = x - b_1
      | r = n_1 r
      | c = 
}}
{{eqn | l = x - b_2
      | r = n_2 r
      | c = 
}}
{{end-eqn}}
Eliminating $x$, we get:
:$b_2 - b_1 = n_1 r - n_2 s$
The {{RHS}} is an integer combination of $n_1$ and $n_2$ and so is a multiple of $\gcd \left\{{n_1, n_2}\right\}$.
Thus $\gcd \set {n_1, n_2}$ divides $b_2 - b_1$, so this is a necessary condition for the system to have a solution.
To show sufficiency, we reverse the argument.
Suppose $\exists k \in \Z: b_2 - b_1 = k \gcd \set {n_1, n_2}$.
We know that $\exists u, v \in \Z: \gcd \set {n_1, n_2} = u n_1 + v n_2$ from Bézout's Identity.
Eliminating $\gcd \set {n_1, n_2}$, we have:
:$b_1 + k u n_1 = b_2 - k v n_2$.
Then:
:$b_1 + k u n_1 = b_1 + \paren {k u} n_1 \equiv b_1 \pmod {n_1}$
:$b_1 + k u n_1 = b_2 + \paren {k v} n_2 \equiv b_2 \pmod {n_2}$
So $b_1 + k u n_1$ satisfies both congruences and so simultaneous solutions do exist.
Now to show uniqueness.
Suppose $x_1$ and $x_2$ are both solutions.
That is:
:$x_1 \equiv x_2 \equiv b_1 \pmod {n_1}$
:$x_1 \equiv x_2 \equiv b_2 \pmod {n_2}$
Then from Intersection of Congruence Classes the result follows.
{{qed}}
The result for $r > 2$ follows by a tedious induction proof.
{{finish}}
Category:Modulo Arithmetic
b01ooyv4rzbggsxx6rkuch4wcjpwl16
Theorem: Second Supplement to Law of Quadratic Reciprocity

$\quad \paren {\dfrac 2 p} = \paren {-1}^{\paren {p^2 - 1} / 8} = \begin {cases}
+1 & : p \equiv \pm 1 \pmod 8 \\
-1 & : p \equiv \pm 3 \pmod 8
\end {cases}$

Proof:
Consider the numbers in the set $S = \set {2 \times 1, 2 \times 2, 2 \times 3, \dots, 2 \times \dfrac {p - 1} 2} = \set {2, 4, 6, \dots, p - 1}$.
From Gauss's Lemma:
:$\paren {\dfrac 2 p} = \paren {-1}^n$
where $n$ is the number of elements in $S$ whose least positive residue modulo $p$ is greater than $\dfrac p 2$.
As they are, the elements of $S$ are already least positive residues of $p$ (as they are all less than $p$).
What we need to do is count how many are greater than $\dfrac p 2$.
We see that:
:$2 k > \dfrac p 2 \iff k > \dfrac p 4$
So the first $\floor {\dfrac p 4}$ elements of $S$ are not greater than $\dfrac p 2$, where $\floor {\dfrac p 4} $ is the floor function of $\dfrac p 4$.
The rest of the elements of $S$ ''are'' greater than $\dfrac p 2$.
So we have:
:$n = \dfrac {p - 1} 2 - \floor {\dfrac p 4}$
Consider the four possible residue classes modulo $8$ of the odd prime $p$.
$p = 8 k + 1$:
{{begin-eqn}}
{{eqn | l = p
      | r = 8 k + 1
      | c = 
}}
{{eqn | ll= \leadsto
      | l = n
      | r = 4 k - \floor {2 k + \frac 1 4}
      | c = 
}}
{{eqn | r = 4 k - 2 k
      | c = 
}}
{{eqn | r = 2k
      | c = 
}}
{{end-eqn}}
$p = 8 k + 3$:
{{begin-eqn}}
{{eqn | l = p
      | r = 8 k + 3
      | c = 
}}
{{eqn | ll= \leadsto
      | l = n
      | r = 4 k + 1 - \floor {2 k + \frac 3 4}
      | c = 
}}
{{eqn | r = 4 k + 1 - 2 k
      | c = 
}}
{{eqn | r = 2 k + 1
      | c = 
}}
{{end-eqn}}
$p = 8 k + 5$:
{{begin-eqn}}
{{eqn | l = p
      | r = 8 k + 5
      | c = 
}}
{{eqn | ll= \leadsto
      | l = n
      | r = 4 k + 2 - \floor {2 k + \frac 5 4}
      | c = 
}}
{{eqn | r = 4 k + 2 - \paren {2 k + 1}
      | c = 
}}
{{eqn | r = 2 k + 1
      | c = 
}}
{{end-eqn}}
$p = 8 k + 7$:
{{begin-eqn}}
{{eqn | l = p
      | r = 8 k + 7
      | c = 
}}
{{eqn | ll= \leadsto
      | l = n
      | r = 4 k + 3 - \floor {2 k + \frac 7 4}
      | c = 
}}
{{eqn | r = 4 k + 3 - \paren {2 k + 1}
      | c = 
}}
{{eqn | r = 2 k + 2
      | c = 
}}
{{end-eqn}}
We see that $n$ is even when $p = 8 k + 1$ or $p = 8 k + 7$ and odd in the other two cases.
So from Gauss's Lemma, we have:
{{begin-eqn}}
{{eqn | l = \paren {\dfrac 2 p}
      | r = \paren {-1}^n = 1
      | c = when $p = 8 k + 1$ or $p = 8 k + 7$
}}
{{eqn | l = \paren {\dfrac 2 p}
      | r = \paren {-1}^n = -1
      | c = when $p = 8 k + 3$ or $p = 8 k + 5$
}}
{{end-eqn}}
As $7 \equiv -1 \pmod 8$ and $5 \equiv -3 \pmod 8$ the result follows.
{{qed}}
Theorem: First Supplement to Law of Quadratic Reciprocity

$\quad \paren {\dfrac {-1} p} = \paren {-1}^{\paren {p - 1} / 2} = \begin {cases}
+1 & : p \equiv 1 \pmod 4 \\
-1 & : p \equiv 3 \pmod 4
\end {cases}$

Proof:
From Euler's Criterion for Quadratic Residue, and the definition of the Legendre symbol, we have that:
:$\paren {\dfrac a p} \equiv a^{\paren {p - 1} / 2} \pmod p$
The result follows by putting $a = -1$.
{{qed}}