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.1

$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.2

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

assume-case divL2L4

2.1

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

step 1.1L7L9

2.2

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

step 1.1L1L3L7

3.1

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

step 1.1step 2.1L1L7

3.2

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

step 2.2L1L2

4.1

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.

assume-case divstep 3.1step 3.2L5

4.2

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.

assume-case nodivstep 3.2L2L6

5.1

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.

step 4.1step 4.2cases-exhaustive∎

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$ .

Depends on

Used by

Dependency tree · two levels

49 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

Euclid's lemma (Wikipedia) (standard reference, not scraped)
Coprime integers (Wikipedia) (standard reference, not scraped)
Inquiry into Advanced Algebra: Division, primes, and factorisation (standard reference, not scraped)

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