How statement and proof provenance work

The first chip identifies the source of the statement or construction; the second identifies the source of its local proof or verification.

Literature-sourced: the exact statement appears in a cited source; only wording and notation differ.
AI-adapted: a semantically identical restatement of literature-sourced material, modulo indexing, notation, and boundary cases adopted by the library.
AI-generated: a genuinely novel statement formulated by AI, with no source for the claim itself.

These labels describe origin, not correctness: citations and verification chips remain separate evidence.

✓ 10 results · all verified · 1 also independently AI-judged

Every result on this page is machine-checked by a proof checker and read in full and owner-audited; the judge is an additional, independent cross-model AI review of the proofs. The 9 not AI-judged were verified by owner audit (typically over a confirmed judge false positive), not failures.

Congruences and Modular Arithmetic: Examples and Counterexamples

1 · Prerequisites

2 · Summary

3 · Logical flowchart

4 · Definitions, theorems and proofs

None yet.

5 · Examples, counterexamples and false statements

ExampleConstruction: Literature-sourcedVerification: AI-adaptedprecheck passaudited 2026-07-31Open item page →

The system $x \equiv 2 (m o d 3)$ , $x \equiv 3 (m o d 5)$ , $x \equiv 2 (m o d 7)$ has the unique solution $x \equiv 23 (m o d 105)$

Example

The system

$x \equiv 2 (m o d 3), x \equiv 3 (m o d 5), x \equiv 2 (m o d 7)$

has exactly the solutions $x \equiv 23 (m o d 105)$ .

Facts & Assumptions

Given: The three displayed congruences.

[L1]

For a finite pairwise-coprime list of positive moduli, prescribed residues determine one class modulo their product (Chinese remainder theorem for a finite pairwise-coprime list: simultaneous residues determine one class modulo the product, and the resulting bijection preserves addition and multiplication).

[L2]

The relation $u \equiv v (m o d n)$ means $n ∣ (u - v)$ (Congruence modulo an integer: $a \equiv b (m o d n)$ when $n ∣ (a - b)$ , including the moduli $0$ and $1$ ).

Verification

technique · constructive

1.1

The numbers $3, 5, 7$ are pairwise coprime and have product $105$ . The complementary products $35, 21, 15$ satisfy $2 \cdot 35 \equiv 1 (m o d 3)$ , $21 \equiv 1 (m o d 5)$ , and $15 \equiv 1 (m o d 7)$ , while each is divisible by the other two moduli.

2.1

Therefore $x : = 2 (2 \cdot 35) + 3 (21) + 2 (15) = 233$ has the prescribed three residues, and $233 = 23 + 2 \cdot 105$ gives $x \equiv 23 (m o d 105)$ .

constructstep 1.1L2

3.1

By [L1], all simultaneous solutions form one class modulo $3 \cdot 5 \cdot 7 = 105$ ; since step 2.1 exhibits $23$ in that class, it is exactly $[23]_{105}$ .

step 2.1L1discharge-construct∎

ExampleConstruction: Literature-sourcedVerification: AI-adaptedprecheck passaudited 2026-07-31Open item page →

The congruence $14 x \equiv 30 (m o d 100)$ has exactly the two solutions $x \equiv 45, 95 (m o d 100)$

Example

The congruence $14 x \equiv 30 (m o d 100)$ has exactly the solution classes

$[45]_{100} and [95]_{100} .$

Facts & Assumptions

Given: The congruence $14 x \equiv 30 (m o d 100)$ .

[L1]

A linear congruence $a x \equiv b (m o d n)$ is solvable exactly when $\gcd (a, n) ∣ b$ , and then has exactly $\gcd (a, n)$ solution classes modulo $n$ (For $n \geq 1$ , $a x \equiv b (m o d n)$ is solvable exactly when $\gcd (a, n) ∣ b$ , and then has exactly $\gcd (a, n)$ solution classes modulo $n$ ).

[L2]

The extended Euclidean algorithm produces gcds and Bézout coefficients (The extended Euclidean algorithm: the same descent produces integers $x, y$ with $a x + b y = \gcd (a, b)$ , so Bézout coefficients are computed and not merely shown to exist).

[L3]

Congruence modulo $n$ means divisibility of a difference by $n$ (Congruence modulo an integer: $a \equiv b (m o d n)$ when $n ∣ (a - b)$ , including the moduli $0$ and $1$ ).

Verification

technique · direct

1.1

The Euclidean algorithm gives $\gcd (14, 100) = 2$ , and $2 ∣ 30$ . Cancelling the common factor reduces the congruence to $7 x \equiv 15 (m o d 50)$ .

L1L2L3

1.2

Since $7 \cdot 43 = 301 \equiv 1 (m o d 50)$ , multiplication by $43$ gives $x \equiv 43 \cdot 15 = 645 \equiv 45 (m o d 50)$ .

1.3

The two lifts of this class modulo $100$ are $45$ and $45 + 50 = 95$ , and both verify the original congruence: $14 \cdot 45 - 30 = 600$ and $14 \cdot 95 - 30 = 1300$ are divisible by $100$ .

2.1

By [L1] there are exactly two solution classes modulo $100$ , so the two distinct classes in step 1.3 exhaust them.

step 1.1step 1.2step 1.3L1∎

ExampleConstruction: AI-adaptedVerification: AI-adaptedprecheck passaudited 2026-07-31Open item page →

$(Z / 12)^{\times} = {[1], [5], [7], [11]}$ and $φ (12) = 4$

Example

$(Z / 12)^{\times} = {[1]_{12}, [5]_{12}, [7]_{12}, [11]_{12}}, φ (12) = 4.$

Every displayed unit is its own inverse.

Facts & Assumptions

Given: The quotient $Z / 12$ and its unit group.

[L1]

The classes modulo $12$ have the unique standard representatives $0, \dots, 11$ (For $n \geq 1$ , every class in $Z / n$ has one representative $r$ with $0 \leq r < n$ , so $∣ Z / n ∣ = n$ ; while $Z / 0$ is in bijection with $Z$ ).

[L2]

The class $[a]_{12}$ is a unit exactly when $\gcd (a, 12) = 1$ , and $φ (12)$ counts these units (For $n \geq 1$ , $[a]_{n}$ is a unit if and only if $\gcd (a, n) = 1$ , The unit group $(Z / n)^{\times}$ and Euler's totient $φ (n) = ∣ (Z / n)^{\times} ∣$ for $n \geq 1$ ).

[L3]

Euler's finite prime-divisor product gives $φ (n) = \prod_{p^{k} ∥ n} (p^{k} - p^{k - 1})$ (Euler's product formula $φ (n) = n \prod_{p ∣ n} (1 - 1 / p) = \prod_{p^{k} ∥ n} (p^{k} - p^{k - 1})$ for $n \geq 1$ , stated through a finite injective list of its prime divisors).

[F1]

Equality of residue classes is congruence of representatives (The congruence class $[a]_{n}$ and the quotient set $Z / n$ ), and congruence means divisibility of their difference (Congruence modulo an integer: $a \equiv b (m o d n)$ when $n ∣ (a - b)$ , including the moduli $0$ and $1$ ).

[F2]

Products of residue classes are computed by multiplying representatives: $[a]_{12} [b]_{12} = [a b]_{12}$ (Addition and multiplication on $Z / n$ by $[a]_{n} + [b]_{n} = [a + b]_{n}$ and $[a]_{n} [b]_{n} = [a b]_{n}$ ).

Verification

technique · direct

1.1

Among $0, \dots, 11$ , exactly $1, 5, 7, 11$ have gcd $1$ with $12$ : every other representative is divisible by $2$ or $3$ . Thus [L1] and [L2] give the displayed unit group and $φ (12) = 4$ .

L1L2

1.2

The congruences $5^{2} = 25 \equiv 1$ , $7^{2} = 49 \equiv 1$ , and $11^{2} = 121 \equiv 1 (m o d 12)$ show that the three nonidentity units, as well as $[1]_{12}$ , are self-inverse.

L2F1F2

2.1

Since $12 = 2^{2} \cdot 3$ , [L3] independently gives $φ (12) = (2^{2} - 2) (3 - 1) = 2 \cdot 2 = 4$ , agreeing with the list.

step 1.1L3∎

ExampleConstruction: AI-adaptedVerification: AI-generatedprecheck passaudited 2026-07-31Open item page →

The Chinese remainder bijection $Z / 12 \to Z / 3 \times Z / 4$ computed on all standard representatives

Example

For standard representatives, the Chinese remainder map is

$a$	$([a]_{3}, [a]_{4})$	$a$	$([a]_{3}, [a]_{4})$
$0$	$([0]_{3}, [0]_{4})$	$6$	$([0]_{3}, [2]_{4})$
$1$	$([1]_{3}, [1]_{4})$	$7$	$([1]_{3}, [3]_{4})$
$2$	$([2]_{3}, [2]_{4})$	$8$	$([2]_{3}, [0]_{4})$
$3$	$([0]_{3}, [3]_{4})$	$9$	$([0]_{3}, [1]_{4})$
$4$	$([1]_{3}, [0]_{4})$	$10$	$([1]_{3}, [2]_{4})$
$5$	$([2]_{3}, [1]_{4})$	$11$	$([2]_{3}, [3]_{4})$

Facts & Assumptions

Given: The map $Φ ([a]_{12}) : = ([a]_{3}, [a]_{4})$ .

[L1]

Every class modulo a positive integer has one standard representative (For $n \geq 1$ , every class in $Z / n$ has one representative $r$ with $0 \leq r < n$ , so $∣ Z / n ∣ = n$ ; while $Z / 0$ is in bijection with $Z$ ).

[L2]

Since $3, 4$ are coprime, $Φ$ is a bijection and preserves addition and multiplication componentwise (Chinese remainder theorem for a finite pairwise-coprime list: simultaneous residues determine one class modulo the product, and the resulting bijection preserves addition and multiplication).

[L3]

Modular addition and multiplication are computed by adding and multiplying representatives (Addition and multiplication on $Z / n$ by $[a]_{n} + [b]_{n} = [a + b]_{n}$ and $[a]_{n} [b]_{n} = [a b]_{n}$ ).

Verification

technique · direct

1.1

Reducing each integer $0, \dots, 11$ modulo $3$ and modulo $4$ gives the displayed table. Its entries are all distinct, and [L1] shows that they exhaust the domain and codomain standard pairs, in agreement with [L2].

L1L2

1.2

For a nontrivial addition check, $[7]_{12} + [8]_{12} = [3]_{12}$ , and the table gives $([1]_{3}, [3]_{4}) + ([2]_{3}, [0]_{4}) = ([0]_{3}, [3]_{4})$ .

1.3

For a nontrivial multiplication check, $[5]_{12} [7]_{12} = [11]_{12}$ , and the table gives $([2]_{3}, [1]_{4}) ([1]_{3}, [3]_{4}) = ([2]_{3}, [3]_{4})$ .

2.1

The table computes the whole bijection, while steps 1.2 and 1.3 instantiate its componentwise arithmetic preservation.

step 1.1step 1.2step 1.3L2∎

ExampleConstruction: Literature-sourcedVerification: AI-adaptedprecheck passaudited 2026-07-31Open item page →

$(Z / 8)^{\times} = {[1], [3], [5], [7]}$ is not cyclic because every element squares to $[1]$

Example

$(Z / 8)^{\times} = {[1]_{8}, [3]_{8}, [5]_{8}, [7]_{8}}$

is not cyclic: every element has square $[1]_{8}$ .

Facts & Assumptions

Given: The unit group $(Z / 8)^{\times}$ .

[L1]

The standard representatives of units are exactly the integers $a$ with $0 \leq a < 8$ and $\gcd (a, 8) = 1$ (For $n \geq 1$ , every class in $Z / n$ has one representative $r$ with $0 \leq r < n$ , so $∣ Z / n ∣ = n$ ; while $Z / 0$ is in bijection with $Z$ , For $n \geq 1$ , $[a]_{n}$ is a unit if and only if $\gcd (a, n) = 1$ , The unit group $(Z / n)^{\times}$ and Euler's totient $φ (n) = ∣ (Z / n)^{\times} ∣$ for $n \geq 1$ ).

[L2]

A finite group is cyclic when one element generates it, and an element generates a finite group exactly when its order is the group cardinality (The subgroup $⟨ S ⟩$ generated by a subset, the cyclic subgroup $⟨ g ⟩$ , and cyclic groups, The order $∣ G ∣$ of a finite group and the order $ord (g)$ of an element, with $ord (g) = \infty$ when no positive power of $g$ is the identity, If $ord (g) = n$ then $g^{k} = e$ iff $k$ is an integer multiple of $n$ , the powers $g^{0}, \dots, g^{n - 1}$ are distinct, and $⟨ g ⟩$ has exactly $n$ elements; if $g$ has infinite order then $g^{j} = g^{k}$ only for $j = k$ ).

[L3]

Natural powers in a group satisfy $g^{0} = e$ and $g^{2} = g g$ (Powers $g^{n}$ : natural exponents in a monoid and integer exponents in a group, with $g^{0} = e$ ).

[F1]

Verification

technique · direct

1.1

The odd standard representatives $1, 3, 5, 7$ are precisely those coprime to $8$ , giving the displayed unit group by [L1].

1.2

Their squares are $1^{2} = 1$ , $3^{2} = 9 \equiv 1$ , $5^{2} = 25 \equiv 1$ , and $7^{2} = 49 \equiv 1 (m o d 8)$ . Hence every element has order at most $2$ .

L3F1

2.1

The group has cardinality $4$ by step 1.1, but no element has order $4$ by step 1.2. Therefore no element generates it, and [L2] shows that it is not cyclic.

step 1.1step 1.2L2∎

ExampleConstruction: AI-adaptedVerification: AI-generatedprecheck passjudge pass (deepseek-v4-pro + gpt-5.6-terra)verified 2026-08-04 (gpt-5.6-sol-codex-subscription)Open item page →

$φ (360) = 96$ by both inclusion-exclusion and the prime-power product formula

Example

Euler's totient at $360$ is $96$ , obtained either by excluding multiples of $2, 3, 5$ or by multiplying the prime-power contributions.

Facts & Assumptions

Given: The positive integer $360$ .

[L1]

Its canonical prime factorisation is $360 = 2^{3} \cdot 3^{2} \cdot 5$ (For $n \geq 1$ and any injective list $p : r \to Z$ of primes containing every prime divisor of $n$ , one has $n = \prod_{i < r} p_{i}^{v_{p_{i}} (n)}$ ; the exponents are determined by $n$ , and $v_{q} (n) = 0$ for every prime $q$ outside the list).

[L2]

Euler's formula gives $φ (n) = \prod_{i < r} (p_{i}^{k_{i}} - p_{i}^{k_{i} - 1})$ over the distinct prime divisors of $n$ and, after carrying the natural numbers into $Q$ , the equivalent form $φ (n) = n \prod_{i < r} (1 - \frac{1}{p_{i}})$ (Euler's product formula $φ (n) = n \prod_{p ∣ n} (1 - 1 / p) = \prod_{p^{k} ∥ n} (p^{k} - p^{k - 1})$ for $n \geq 1$ , stated through a finite injective list of its prime divisors). Multiplying out that second product over the subsets of ${p_{0}, \dots, p_{r - 1}}$ is the inclusion-exclusion display used below; the cited theorem states the two products, not that display.

Verification

technique · direct

1.1

Inclusion-exclusion over the multiples of $2, 3, 5$ gives $φ (360) = 360 - 180 - 120 - 72 + 60 + 36 + 24 - 12 = 96$ .

L1L2

1.2

The product form gives $φ (360) = (2^{3} - 2^{2}) (3^{2} - 3) (5 - 1) = 4 \cdot 6 \cdot 4 = 96$ .

L1L2

2.1

Both computations therefore give the same value, $φ (360) = 96$ .

step 1.1step 1.2∎

CounterexampleConstruction: AI-adaptedVerification: AI-generatedprecheck passaudited 2026-07-31Open item page →

The system $x \equiv 1 (m o d 2)$ , $x \equiv 2 (m o d 4)$ has no solution, so coprimality in the Chinese remainder theorem cannot be dropped

Statement refuted

Refuted claim: prescribed residue classes always determine a simultaneous class even when the positive moduli are not coprime.

The system $x \equiv 1 (m o d 2)$ , $x \equiv 2 (m o d 4)$ is a counterexample.

Facts & Assumptions

Given: The two displayed congruences with moduli $2$ and $4$ .

[L1]

Congruence $a \equiv b (m o d n)$ means $n ∣ (a - b)$ (Congruence modulo an integer: $a \equiv b (m o d n)$ when $n ∣ (a - b)$ , including the moduli $0$ and $1$ ).

[L2]

For positive moduli $m, n$ , simultaneous residues $a, b$ are compatible exactly when $\gcd (m, n) ∣ (a - b)$ ; pairwise coprimality makes this automatic (For coprime positive $m, n$ , every pair of residue classes modulo $m$ and $n$ has a unique simultaneous class modulo $m n$ , Chinese remainder theorem for a finite pairwise-coprime list: simultaneous residues determine one class modulo the product, and the resulting bijection preserves addition and multiplication).

Counterexample

technique · direct

1.1

If $x \equiv 1 (m o d 2)$ , then $x - 1$ is even and $x$ is odd. If $x \equiv 2 (m o d 4)$ , then $x - 2$ is divisible by $4$ and $x$ is even. No integer is both odd and even, so the system has no solution.

1.2

Equivalently, $\gcd (2, 4) = 2$ does not divide $1 - 2 = - 1$ , so the compatibility criterion in [L2] fails.

2.1

The claim without coprimality admits the unsolvable system in step 1.1 and is therefore false.

step 1.1step 1.2∎

ExampleConstruction: Literature-sourcedVerification: AI-adaptedprecheck passaudited 2026-07-31Open item page →

A modulus $n > 1$ is composite exactly when two nonzero classes in $Z / n$ have product $[0]_{n}$

Example

For every integer $n > 1$ , the following are equivalent:

$n$ is composite.
There are nonzero classes $u, v \in Z / n$ with $u v = [0]_{n}$ .

Facts & Assumptions

Given: An integer $n > 1$ .

[L1]

A positive integer greater than $1$ is composite exactly when it has a divisor $d$ with $1 < d < n$ ; otherwise it is prime (Prime and composite integers: $p$ is prime when $p > 1$ and its only positive divisors are $1$ and $p$ ).

[L2]

Products in $Z / n$ are computed on representatives, and the quotient has standard representatives $0, \dots, n - 1$ (Addition and multiplication on $Z / n$ by $[a]_{n} + [b]_{n} = [a + b]_{n}$ and $[a]_{n} [b]_{n} = [a b]_{n}$ , For $n \geq 1$ , every class in $Z / n$ has one representative $r$ with $0 \leq r < n$ , so $∣ Z / n ∣ = n$ ; while $Z / 0$ is in bijection with $Z$ ).

[L3]

A class $[a]_{n}$ is a unit exactly when $\gcd (a, n) = 1$ , and the gcd is a nonnegative common divisor that is positive when its arguments are not both zero (For $n \geq 1$ , $[a]_{n}$ is a unit if and only if $\gcd (a, n) = 1$ , Common divisor, and the greatest common divisor $\gcd (a, b)$ , with the convention $\gcd (0, 0) : = 0$ ).

Verification

technique · direct

1.1

If $n$ is composite, write $n = a b$ with $1 < a < n$ and $1 < b < n$ . Then $[a]_{n}$ and $[b]_{n}$ are nonzero standard classes, but $[a]_{n} [b]_{n} = [a b]_{n} = [n]_{n} = [0]_{n}$ .

L1L2

1.2

Conversely, suppose nonzero classes have product zero and choose their standard representatives $a, b$ , so $0 < a, b < n$ and $n ∣ a b$ . The class $[a]_{n}$ cannot be a unit, because multiplying an equation $[a]_{n} [b]_{n} = [0]_{n}$ by its inverse would give $[b]_{n} = [0]_{n}$ . Hence $d : = \gcd (a, n) > 1$ by [L3]. Since $d ∣ a$ and $0 < a < n$ , one also has $d < n$ , so $d$ is a nontrivial divisor of $n$ and $n$ is composite by [L1].

L1L2L3

2.1

Steps 1.1 and 1.2 prove the equivalence.

step 1.1step 1.2∎

False statementConstruction: AI-adaptedVerification: AI-generatedprecheck passaudited 2026-07-31Open item page →

False: $[a]_{n} [b]_{n} = [0]_{n}$ always implies $[a]_{n} = [0]_{n}$ or $[b]_{n} = [0]_{n}$

Statement

False claim: for every natural modulus $n$ ,

$[a]_{n} [b]_{n} = [0]_{n} ⟹ [a]_{n} = [0]_{n} or [b]_{n} = [0]_{n} .$

Facts & Assumptions

Given: The quotient $Z / 6$ and the classes $[2]_{6}, [3]_{6}$ .

[L1]

Products in $Z / n$ are computed by multiplying representatives (Addition and multiplication on $Z / n$ by $[a]_{n} + [b]_{n} = [a + b]_{n}$ and $[a]_{n} [b]_{n} = [a b]_{n}$ ).

[L2]

Composite moduli admit nonzero classes with zero product; moreover $[a]_{n} = [b]_{n}$ exactly when $a \equiv b (m o d n)$ , which means $n ∣ (a - b)$ (A modulus $n > 1$ is composite exactly when two nonzero classes in $Z / n$ have product $[0]_{n}$ , The congruence class $[a]_{n}$ and the quotient set $Z / n$ , Congruence modulo an integer: $a \equiv b (m o d n)$ when $n ∣ (a - b)$ , including the moduli $0$ and $1$ ).

Refutation

technique · direct

1.1

In $Z / 6$ , $[2]_{6} [3]_{6} = [6]_{6} = [0]_{6}$ by [L1].

1.2

Neither $6 ∣ 2$ nor $6 ∣ 3$ , so $[2]_{6} \neq [0]_{6}$ and $[3]_{6} \neq [0]_{6}$ .

2.1

Thus the antecedent of the claimed implication holds while both alternatives in its conclusion fail, so the claim is false.

step 1.1step 1.2∎

CounterexampleConstruction: Literature-sourcedVerification: AI-adaptedprecheck passaudited 2026-07-31Open item page →

$Z / 1$ has one element and satisfies $[0]_{1} = [1]_{1}$ , so it is not a field

Statement refuted

The modular operations do not make $Z / n$ a field for every positive modulus $n$ : the boundary modulus $n = 1$ is a counterexample.

Facts & Assumptions

Given: The quotient $Z / 1$ with its modular operations.

[L1]

The quotient $Z / 1$ has exactly one class (For $n \geq 1$ , every class in $Z / n$ has one representative $r$ with $0 \leq r < n$ , so $∣ Z / n ∣ = n$ ; while $Z / 0$ is in bijection with $Z$ ).

[L2]

Its modular operations satisfy the abelian-group, commutative-monoid and distributive identities, with additive identity $[0]_{1}$ and multiplicative identity $[1]_{1}$ (For every natural $n$ , $(Z / n, +)$ is an abelian group, multiplication is a commutative monoid operation, and both distributive laws hold).

[L3]

A field must have distinct additive and multiplicative identities (Field).

Counterexample

technique · direct

1.1

By [L1], all integers determine the same class modulo $1$ , so in particular $[0]_{1} = [1]_{1}$ .

2.1

Although the other algebraic identities hold by [L2], the equality in step 1.1 violates the distinct-identities clause [L3]. Hence $Z / 1$ is not a field.

step 1.1L2L3∎

Congruences and Modular Arithmetic: Examples and Counterexamples

1 · Prerequisites

2 · Summary

3 · Logical flowchart

4 · Definitions, theorems and proofs

5 · Examples, counterexamples and false statements

The system x≡2(mod3)x≡2(mod3), x≡3(mod5)x≡3(mod5), x≡2(mod7)x≡2(mod7) has the unique solution x≡23(mod105)x≡23(mod105)

Example

Facts & Assumptions

Verification

The congruence 14x≡30(mod100)14x≡30(mod100) has exactly the two solutions x≡45,95(mod100)x≡45,95(mod100)

Example

Facts & Assumptions

Verification

(Z/12)×={[1],[5],[7],[11]}(Z/12)×={[1],[5],[7],[11]} and φ(12)=4φ(12)=4

Example

Facts & Assumptions

Verification

The Chinese remainder bijection Z/12→Z/3×Z/4Z/12→Z/3×Z/4 computed on all standard representatives

Example

Facts & Assumptions

Verification

(Z/8)×={[1],[3],[5],[7]}(Z/8)×={[1],[3],[5],[7]} is not cyclic because every element squares to [1][1]

Example

Facts & Assumptions

Verification

φ(360)=96φ(360)=96 by both inclusion-exclusion and the prime-power product formula

Example

Facts & Assumptions

Verification

The system x≡1(mod2)x≡1(mod2), x≡2(mod4)x≡2(mod4) has no solution, so coprimality in the Chinese remainder theorem cannot be dropped

Statement refuted

Facts & Assumptions

Counterexample

A modulus n>1n>1 is composite exactly when two nonzero classes in Z/nZ/n have product [0]n[0]n​

Example

Facts & Assumptions

Verification

False: [a]n[b]n=[0]n[a]n​[b]n​=[0]n​ always implies [a]n=[0]n[a]n​=[0]n​ or [b]n=[0]n[b]n​=[0]n​

Statement

Facts & Assumptions

Refutation

Z/1Z/1 has one element and satisfies [0]1=[1]1[0]1​=[1]1​, so it is not a field

Statement refuted

Facts & Assumptions

Counterexample

Sources

The system $x \equiv 2 (m o d 3)$ , $x \equiv 3 (m o d 5)$ , $x \equiv 2 (m o d 7)$ has the unique solution $x \equiv 23 (m o d 105)$

The congruence $14 x \equiv 30 (m o d 100)$ has exactly the two solutions $x \equiv 45, 95 (m o d 100)$

$(Z / 12)^{\times} = {[1], [5], [7], [11]}$ and $φ (12) = 4$

The Chinese remainder bijection $Z / 12 \to Z / 3 \times Z / 4$ computed on all standard representatives

$(Z / 8)^{\times} = {[1], [3], [5], [7]}$ is not cyclic because every element squares to $[1]$

$φ (360) = 96$ by both inclusion-exclusion and the prime-power product formula

The system $x \equiv 1 (m o d 2)$ , $x \equiv 2 (m o d 4)$ has no solution, so coprimality in the Chinese remainder theorem cannot be dropped

A modulus $n > 1$ is composite exactly when two nonzero classes in $Z / n$ have product $[0]_{n}$

False: $[a]_{n} [b]_{n} = [0]_{n}$ always implies $[a]_{n} = [0]_{n}$ or $[b]_{n} = [0]_{n}$

$Z / 1$ has one element and satisfies $[0]_{1} = [1]_{1}$ , so it is not a field