LemmaStatement: AI-adaptedProof: AI-adaptedSession-authored (Fable 5 assisted)precheck passjudge pass (z-ai/glm-5.2)audited 2026-07-28

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.

$a$ and $b$ are coprime if and only if $ax + by = 1$ for some integers $x, y$ ; and in that case the only common divisors of $a$ and $b$ are $1$ and $-1$

Statement

Let $a, b \in \mathbb{Z}$ . Then $a$ and $b$ are coprime (Coprime integers: $\gcd(a,b) = 1$ ) if and only if

$ax + by \;=\; 1 \qquad \text{for some } x, y \in \mathbb{Z} .$

When this holds, the set of common divisors of $a$ and $b$ is exactly $\{1, -1\}$ .

Facts & Assumptions

Given: Integers $a$ and $b$ .

[L1]

$a$ and $b$ are coprime when $\gcd(a,b) = 1$ (Coprime integers: $\gcd(a,b) = 1$ , Common divisor, and the greatest common divisor $\gcd(a,b)$ , with the convention $\gcd(0,0) := 0$ ).

[L2]

For $(a,b) \ne (0,0)$ there are $x_0, y_0$ with $a x_0 + b y_0 = \gcd(a,b)$ (Bézout's identity: for integers $a, b$ not both zero, $\gcd(a,b)$ is the least positive element of $\{\, ax + by : x, y \in \mathbb{Z} \,\}$ ; in particular $ax + by = \gcd(a,b)$ has an integer solution).

[L3]

$d = \gcd(a,b)$ exactly when $d \ge 0$ , $d \mid a$ , $d \mid b$ , and every common divisor of $a$ and $b$ divides $d$ (Every common divisor of $a$ and $b$ divides $\gcd(a,b)$ ; consequently $d = \gcd(a,b)$ exactly when $d \ge 0$ , $d \mid a$ , $d \mid b$ , and every common divisor of $a$ and $b$ divides $d$ — a characterisation that holds at $(a,b) = (0,0)$ as well).

[L4]

If $c \mid a$ and $c \mid b$ then $c \mid ax + by$ for all $x, y$ ; and $1 \mid a$ for every $a$ (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$ , Divisibility in $\mathbb{Z}$ : $d \mid a$ when $a = dq$ for some integer $q$ ).

[L5]

$c \mid 1$ exactly when $c = 1$ or $c = -1$ , and $1 \ne -1$ ( $(\mathbb{Z}, \cdot, 1)$ is a commutative monoid whose group of units is $\{1, -1\}$ ; equivalently $u \mid 1$ holds exactly for $u = 1$ and $u = -1$ ).

[L6]

$\mathbb{Z}$ is a commutative ring, with $x \cdot 0 = 0$ , $x + 0 = x$ , $-(-x) = x$ and $(-x)(-y) = xy$ (The integers form a commutative ring, Arithmetic on the integers); its order is total, antisymmetric and transitive and is compatible with addition, and positives are closed under multiplication (The integers form a totally ordered ring, Order on the integers).

[L7]

$\gcd(0,0) = 0$ by convention (Common divisor, and the greatest common divisor $\gcd(a,b)$ , with the convention $\gcd(0,0) := 0$ ).

Proof

technique · direct

1.1

$1 \ne 0$ and $0 \le 1$ . If $1 = 0$ then $-1 = -0 = 0 = 1$ , contradicting $1 \ne -1$ in [L5]. By totality either $0 \le 1$ or $1 \le 0$ ; in the second case adding $-1$ gives $0 \le -1$ , and $-1 \ne 0$ since otherwise $1 = 0$ , so $0 < -1$ and hence $0 < (-1)(-1) = 1$ , which with $1 \le 0$ contradicts antisymmetry.

L5L6

1.2

Conversely, suppose $ax + by = 1$ for some $x, y$ . Every common divisor $c$ of $a$ and $b$ divides $ax + by = 1$ by [L4], hence $c = 1$ or $c = -1$ by [L5].

L4L5

2.1

Suppose $a$ and $b$ are coprime, so $\gcd(a,b) = 1$ . Then $(a,b) \ne (0,0)$ , since $\gcd(0,0) = 0 \ne 1$ ; so [L2] supplies $x_0, y_0$ with $a x_0 + b y_0 = \gcd(a,b) = 1$ .

step 1.1L1L2L7

2.2

The integer $1$ then satisfies all four conditions of [L3]: $1 \ge 0$ by step 1.1, $1 \mid a$ and $1 \mid b$ by [L4], and every common divisor of $a$ and $b$ divides $1$ by step 1.2. Hence $\gcd(a,b) = 1$ , that is, $a$ and $b$ are coprime.

step 1.1step 1.2L1L3L4

3.1

So coprimality and the solvability of $ax + by = 1$ are equivalent, by step 2.1 and step 2.2.

step 2.1step 2.2

4.1

When they hold, step 1.2 shows every common divisor is $1$ or $-1$ ; conversely $1$ and $-1$ are common divisors of any pair, since $1 \mid a$ , $1 \mid b$ , $-1 \mid a$ and $-1 \mid b$ . So the set of common divisors is exactly $\{1,-1\}$ , and it has two elements since $1 \ne -1$ .

step 1.2L4L5∎

Remarks

The criterion is the practical form of coprimality. Verifying $\gcd(a,b) = 1$ from the definition means examining all common divisors; exhibiting one pair $(x,y)$ with $ax + by = 1$ settles it in a line, and the extended Euclidean algorithm produces such a pair (The extended Euclidean algorithm: the same descent produces integers $x, y$ with $ax + by = \gcd(a,b)$ , so Bézout coefficients are computed and not merely shown to exist).
The analogous statement with $1$ replaced by a general $c$ is false, and the correct version is that $ax + by = c$ is solvable exactly when $\gcd(a,b) \mid c$ ; that is worked out on the companion page ( $ax + by = c$ has an integer solution exactly when $\gcd(a,b) \mid c$ : $6x + 15y = 9$ is solvable and $6x + 15y = 7$ is not ↗).

Depends on

Used by

Dependency tree · next 3 levels

Direct dependencies and their dependencies through the next three levels: 66 results over 22 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

Coprime integers (Wikipedia) (standard reference, not scraped)

aaa and bbb are coprime if and only if ax+by=1ax + by = 1ax+by=1 for some integers x,yx, yx,y; and in that case the only common divisors of aaa and bbb are 111 and −1-1−1