LemmaStatement: AI-adaptedProof: AI-generatedprecheck 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.

For a prime $p$ and any integer $a$ , $\gcd (p, a)$ is $p$ when $p ∣ a$ and $1$ otherwise; so $p ∤ a$ makes $p$ and $a$ coprime

Statement

Let $p$ be a prime (Prime and composite integers: $p$ is prime when $p > 1$ and its only positive divisors are $1$ and $p$ ) and let $a \in Z$ . Then

$\gcd (p, a) = {\begin{cases} p & if p ∣ a, \\ 1 & if p ∤ a, \end{cases}$

with $\gcd$ as in Common divisor, and the greatest common divisor $\gcd (a, b)$ , with the convention $\gcd (0, 0) : = 0$ and divisibility as in Divisibility in $Z$ : $d ∣ a$ when $a = d q$ for some integer $q$ . In particular, if $p ∤ a$ then $p$ and $a$ are coprime (Coprime integers: $\gcd (a, b) = 1$ ).

Facts & Assumptions

Given: A prime $p$ , an integer $a$ , and $g : = \gcd (p, a)$ (Common divisor, and the greatest common divisor $\gcd (a, b)$ , with the convention $\gcd (0, 0) : = 0$ ).

[L1]

$p > 1$ , and every positive divisor $d$ of $p$ satisfies $d = 1$ or $d = p$ (Prime and composite integers: $p$ is prime when $p > 1$ and its only positive divisors are $1$ and $p$ ).

[L2]

$g \geq 0$ , $g ∣ p$ , $g ∣ a$ , and every common divisor of $p$ and $a$ divides $g$ (Every common divisor of $a$ and $b$ divides $\gcd (a, b)$ ; consequently $d = \gcd (a, b)$ exactly when $d \geq 0$ , $d ∣ a$ , $d ∣ b$ , and every common divisor of $a$ and $b$ divides $d$ — a characterisation that holds at $(a, b) = (0, 0)$ as well, Common divisor, and the greatest common divisor $\gcd (a, b)$ , with the convention $\gcd (0, 0) : = 0$ ).

[L3]

$\gcd (u, v) \geq 1$ unless $u = v = 0$ , in which case $\gcd (u, v) = 0$ ( $\gcd$ is symmetric and unchanged by signs: $\gcd (a, b) = \gcd (b, a) = \gcd (∣ a ∣, ∣ b ∣)$ ; moreover $\gcd (a, 0) = ∣ a ∣$ , $\gcd (a, 1) = 1$ , $\gcd (a, a) = ∣ a ∣$ , and $\gcd (a, b) \geq 1$ unless $a = b = 0$ ).

[L4]

Divisibility is reflexive and transitive: $u ∣ u$ for every $u$ , and $d ∣ u$ with $u ∣ v$ gives $d ∣ v$ (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$ , Divisibility in $Z$ : $d ∣ a$ when $a = d q$ for some integer $q$ ).

[L5]

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

[L6]

$u$ and $v$ are coprime exactly when $\gcd (u, v) = 1$ (Coprime integers: $\gcd (a, b) = 1$ ).

[L7]

The order on $Z$ is total, antisymmetric and transitive and is compatible with addition; $x < y$ means $x \leq y$ together with $x \neq y$ (The integers form a totally ordered ring, Order on the integers).

[L8]

The embedding $ι : N \to Z$ is injective, preserves the order, and has as image exactly the nonnegative integers, with $ι (0) = 0$ and $ι (1) = 1$ ; and $0 \neq 1$ in $N$ (The naturals embed in the integers, The natural numbers $N$ (von Neumann), The integers as equivalence classes of pairs of naturals).

[L9]

$Z$ is a commutative ring: addition is associative and commutative, $x + 0 = x$ , and every $x$ has an additive inverse $- x$ , with $- (- x) = x$ ; we write $u - v$ for $u + (- v)$ (The integers form a commutative ring, Arithmetic on the integers).

Proof

technique · cases

1.1L8

$0 < 1$ in $Z$ : $1 = ι (1)$ lies in the image of $ι$ , hence $1 \geq 0$ , and $1 \neq 0$ because $ι$ is injective and $0 \neq 1$ in $N$ .

1.2assume-case divL2L4

Suppose $p ∣ a$ . Then $p$ is a common divisor of $p$ and $a$ , since $p ∣ p$ , so $p ∣ g$ .

2.1step 1.1L7L9

$- 1 < 0$ : adding $- 1$ to both sides of $0 < 1$ preserves the order, giving $- 1 < 0$ .

2.2step 1.1L1L3L7

$p > 0$ and $p \neq 0$ , so $(p, a) \neq (0, 0)$ ; consequently $g \geq 1$ , and in particular $g > 0$ .

3.1step 1.1step 2.1L1L7

$p \neq 1$ and $p \neq - 1$ : the first because $p > 1$ , the second because $- 1 < 0 < 1 < p$ and the order is transitive.

3.2step 2.2L1L2

$g$ is a positive divisor of $p$ , so $g = 1$ or $g = p$ .

4.1assume-case divstep 3.1step 3.2L5

In that case $g \neq 1$ : otherwise $p ∣ 1$ , forcing $p = 1$ or $p = - 1$ and contradicting step 3.1. So $g = p$ by step 3.2.

4.2assume-case nodivstep 3.2L2L6

Suppose instead $p ∤ a$ . Then $g \neq p$ , since $g ∣ a$ and $g = p$ would give $p ∣ a$ . So $g = 1$ by step 3.2, that is, $p$ and $a$ are coprime.

5.1step 4.1step 4.2cases-exhaustive∎

Either $p ∣ a$ or $p ∤ a$ , and no third possibility exists, so the two cases above are exhaustive and give the stated value of $g$ in each.

Remarks

This is the only place on this page where primality becomes coprimality. Every later appeal to Bézout's identity — Euclid's lemma (Euclid's lemma: if $p$ is prime and $p ∣ a b$ then $p ∣ a$ or $p ∣ b$ ) first among them — runs through this lemma rather than through the definition of a prime, because the published If $\gcd (a, b) = 1$ and $a ∣ b c$ then $a ∣ c$ ; and if $a ∣ c$ , $b ∣ c$ and $\gcd (a, b) = 1$ then $a b ∣ c$ is stated for coprime integers and uses no primality at all.
The hypothesis that $p$ is prime is used twice, and both uses are essential: once for $p > 1$ , which puts $(p, a)$ outside the pair $(0, 0)$ where the $\gcd$ convention lives and excludes $p$ from being a unit, and once for the divisor condition, which is what leaves only the two candidate values $1$ and $p$ . For a composite $p$ the conclusion fails: $\gcd (4, 6) = 2$ , which is neither $4$ nor $1$ , while $4 ∤ 6$ .

For a prime $p$ and any integer $a$ , $\gcd (p, a)$ is $p$ when $p ∣ a$ and $1$ otherwise; so $p ∤ a$ makes $p$ and $a$ coprime

Statement

Facts & Assumptions

Proof

Remarks

Depends on

Dependency tree · 2 levels

Sources

For a prime pp and any integer aa, gcd⁡(p,a)gcd(p,a) is pp when p∣ap∣a and 11 otherwise; so p∤ap∤a makes pp and aa coprime

Statement

Facts & Assumptions

Proof

Remarks

Depends on

Dependency tree · 2 levels

Sources

For a prime $p$ and any integer $a$ , $\gcd (p, a)$ is $p$ when $p ∣ a$ and $1$ otherwise; so $p ∤ a$ makes $p$ and $a$ coprime