TheoremStatement: Literature-sourcedProof: AI-adaptedprecheck 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.

For $n \geq 1$ , $[a]_{n}$ is a unit if and only if $\gcd (a, n) = 1$

Statement

Let $n \geq 1$ and $a \in Z$ . Then $[a]_{n}$ is a unit of $Z / n$ (The unit group $(Z / n)^{\times}$ and Euler's totient $φ (n) = ∣ (Z / n)^{\times} ∣$ for $n \geq 1$ ) if and only if

$\gcd (a, n) = 1,$

that is, if and only if $a$ and $n$ are coprime (Coprime integers: $\gcd (a, b) = 1$ ). Consequently the condition $\gcd (a, n) = 1$ depends only on the class $[a]_{n}$ .

Facts & Assumptions

Given: A positive integer $n$ and an integer $a$ .

[L1]

Integers $u, v$ are coprime exactly when $u x + v y = 1$ for some integers $x, y$ ( $a$ and $b$ are coprime if and only if $a x + b y = 1$ for some integers $x, y$ ; and in that case the only common divisors of $a$ and $b$ are $1$ and $- 1$ , Bézout's identity: for integers $a, b$ not both zero, $\gcd (a, b)$ is the least positive element of ${a x + b y : x, y \in Z}$ ; in particular $a x + b y = \gcd (a, b)$ has an integer solution, Common divisor, and the greatest common divisor $\gcd (a, b)$ , with the convention $\gcd (0, 0) : = 0$ , Coprime integers: $\gcd (a, b) = 1$ ).

[F1]

The class $[a]_{n}$ is a unit exactly when some $[b]_{n}$ satisfies $[a]_{n} [b]_{n} = [1]_{n}$ (The unit group $(Z / n)^{\times}$ and Euler's totient $φ (n) = ∣ (Z / n)^{\times} ∣$ for $n \geq 1$ ).

[L2]

If an integer divides two integers, it divides every integer linear combination of them (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$ ).

Proof

technique · direct

1.1L1F1choose

Suppose $\gcd (a, n) = 1$ . By [L1], choose integers $x, y$ with $a x + n y = 1$ . Reducing this equality modulo $n$ gives $[a]_{n} [x]_{n} = [1]_{n}$ , so $[a]_{n}$ is a unit.

1.2F1L1choose

Conversely, suppose $[a]_{n}$ is a unit. Choose $b$ with $[a]_{n} [b]_{n} = [1]_{n}$ . Then $a b \equiv 1 (m o d n)$ , so $a b - 1 = n q$ for some integer $q$ , and $a b + n (- q) = 1$ . By [L1], $\gcd (a, n) = 1$ .

1.3L1L2algebra

If $a \equiv a^{'} (m o d n)$ and $\gcd (a, n) = 1$ , write $a^{'} = a + n k$ . A Bézout identity $a x + n y = 1$ then becomes $a^{'} x + n (y - k x) = 1$ , so $\gcd (a^{'}, n) = 1$ by [L1]; symmetry gives the converse. Thus the criterion is representative independent.

2.1step 1.1step 1.2step 1.3∎

Steps 1.1 and 1.2 prove the equivalence, and step 1.3 proves its final representative-independence assertion.

For $n \geq 1$ , $[a]_{n}$ is a unit if and only if $\gcd (a, n) = 1$

Statement

Facts & Assumptions

Proof

Depends on

Dependency tree · 2 levels

Sources

For n≥1n≥1, [a]n[a]n​ is a unit if and only if gcd⁡(a,n)=1gcd(a,n)=1

Statement

Facts & Assumptions

Proof

Depends on

Dependency tree · 2 levels

Sources

For $n \geq 1$ , $[a]_{n}$ is a unit if and only if $\gcd (a, n) = 1$