LemmaStatement: AI-adaptedProof: AI-generatedSession-authored (Fable 5 assisted)precheck 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\ge1$ , $d=\gcd(a,n)$ and $d\mid b$ , then $ax\equiv b\pmod n$ reduces to a congruence with coprime coefficient modulo $n/d$

Statement

Let $a,b\in\mathbb Z$ , let $n\ge1$ , and put $d:=\gcd(a,n)$ . If $d\mid b$ , write

$a=da',\qquad n=dn',\qquad b=db'.$

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

$ax\equiv b\pmod n\quad\Longleftrightarrow\quad a'x\equiv b'\pmod{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\pmod n$ when $n\mid(a-b)$ , including the moduli $0$ and $1$ ).

Facts & Assumptions

Given: Integers $a,b$ , a positive integer $n$ , $d:=\gcd(a,n)$ , and $d\mid 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)\ne0$ , 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\mid y$ means $y=cq$ for some integer $q$ , and divisibility is preserved by integer linear combinations (Divisibility in $\mathbb{Z}$ : $d \mid a$ when $a = dq$ for some integer $q$ , Divisibility is reflexive and transitive on $\mathbb{Z}$ , and is linear: if $d \mid a$ and $d \mid b$ then $d \mid ax + by$ for all integers $x, y$ ; also $d \mid a$ implies $d \mid ac$ , $-d \mid a$ and $d \mid -a$ ).

[L4]

$u\equiv v\pmod c$ means $c\mid(u-v)$ (Congruence modulo an integer: $a\equiv b\pmod n$ when $n\mid(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=da'$ , $n=dn'$ and $b=db'$ ; these quotients are unique by cancellation, $n'>0$ , and $a',n'$ are coprime by [L2].

L1L2L3

2.1

For any integer $x$ , the congruence $ax\equiv b\pmod n$ says $dn'\mid d(a'x-b')$ , so it holds exactly when there is an integer $q$ with $d(a'x-b')=dn'q$ ; since $d\ne0$ , cancellation makes this equivalent to $a'x-b'=n'q$ , namely $a'x\equiv b'\pmod{n'}$ .

step 1.1L3L4∎

Depends on

Used by

For n≥1, ax≡ bpmod n is solvable exactly when gcd(a,n)∣ b, and then has exactly gcd(a,n) solution classes modulo n Theorem

Dependency tree · next 3 levels

Direct dependencies and their dependencies through the next three levels: 43 results over 17 levels. An arrow runs from a result to what uses it, and this result sits at the bottom with a heavier outline. Click the chart to enlarge it.

Sources

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

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