LemmaStatement: AI-adaptedProof: AI-generatedprecheck passaudited 2026-07-31

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.

If $n \geq 1$ , $d = \gcd (a, n)$ and $d ∣ b$ , then $a x \equiv b (m o d n)$ reduces to a congruence with coprime coefficient modulo $n / d$

Statement

Let $a, b \in Z$ , let $n \geq 1$ , and put $d : = \gcd (a, n)$ . If $d ∣ b$ , write

$a = d a^{'}, n = d n^{'}, b = d b^{'} .$

Then $d > 0$ , the integers $a^{'}, n^{'}$ are coprime, and for every $x \in Z$ ,

$a x \equiv b (m o d n) ⟺ a^{'} x \equiv b^{'} (m o d n^{'}) .$

Thus the reduced modulus is the positive integer $n^{'} = n / d$ and its coefficient is coprime to it (Congruence modulo an integer: $a \equiv b (m o d n)$ when $n ∣ (a - b)$ , including the moduli $0$ and $1$ ).

Facts & Assumptions

Given: Integers $a, b$ , a positive integer $n$ , $d : = \gcd (a, n)$ , and $d ∣ b$ .

[L1]

The gcd is a nonnegative common divisor, and it is positive when its two arguments are not both zero (Common divisor, and the greatest common divisor $\gcd (a, b)$ , with the convention $\gcd (0, 0) : = 0$ ).

[L2]

If $d = \gcd (u, v) \neq 0$ , then the uniquely determined quotients $u / d$ and $v / d$ are coprime (If $d = \gcd (a, b)$ is nonzero then $a / d$ and $b / d$ are coprime, The integers have no zero divisors; multiplicative cancellation).

[L3]

$c ∣ y$ means $y = c q$ for some integer $q$ , and divisibility is preserved by integer linear combinations (Divisibility in $Z$ : $d ∣ a$ when $a = d q$ for some integer $q$ , Divisibility is reflexive and transitive on $Z$ , and is linear: if $d ∣ a$ and $d ∣ b$ then $d ∣ a x + b y$ for all integers $x, y$ ; also $d ∣ a$ implies $d ∣ a c$ , $- d ∣ a$ and $d ∣ - a$ ).

[L4]

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

Proof

technique · direct

1.1

Since $n > 0$ , the pair $(a, n)$ is not $(0, 0)$ , so $d > 0$ by [L1]. Because $d$ divides $a, n, b$ , there are integers $a^{'}, n^{'}, b^{'}$ with $a = d a^{'}$ , $n = d n^{'}$ and $b = d b^{'}$ ; these quotients are unique by cancellation, $n^{'} > 0$ , and $a^{'}, n^{'}$ are coprime by [L2].

L1L2L3

2.1

For any integer $x$ , the congruence $a x \equiv b (m o d n)$ says $d n^{'} ∣ d (a^{'} x - b^{'})$ , so it holds exactly when there is an integer $q$ with $d (a^{'} x - b^{'}) = d n^{'} q$ ; since $d \neq 0$ , cancellation makes this equivalent to $a^{'} x - b^{'} = n^{'} q$ , namely $a^{'} x \equiv b^{'} (m o d n^{'})$ .

step 1.1L3L4∎

Depends on

Used by

Dependency tree · two levels

18 results within two dependency steps of this one, each drawn at its shortest distance from it. An arrow runs from a result to what uses it, so the chart reads left to right and ends at this result, which carries a heavier outline. Every node is a link to that result. Click elsewhere on the chart to enlarge it.

Sources

Mathematics LibreTexts, Linear Congruences (standard reference, not scraped)

If n≥1n≥1, d=gcd⁡(a,n)d=gcd(a,n) and d∣bd∣b, then ax≡b(modn)ax≡b(modn) reduces to a congruence with coprime coefficient modulo n/dn/d