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 , is a unit if and only if
Statement
Let and . Then is a unit of (The unit group and Euler's totient for ) if and only if
that is, if and only if and are coprime (Coprime integers: ). Consequently the condition depends only on the class .
Facts & Assumptions
Given: A positive integer and an integer .
Integers are coprime exactly when for some integers ( and are coprime if and only if for some integers ; and in that case the only common divisors of and are and , Bézout's identity: for integers not both zero, is the least positive element of ; in particular has an integer solution, Common divisor, and the greatest common divisor , with the convention , Coprime integers: ).
The class is a unit exactly when some satisfies (The unit group and Euler's totient for ).
If an integer divides two integers, it divides every integer linear combination of them (Divisibility is reflexive and transitive on , and is linear: if and then for all integers ; also implies , and ).
Proof
Suppose . By [L1], choose integers with . Reducing this equality modulo gives , so is a unit.
Conversely, suppose is a unit. Choose with . Then , so for some integer , and . By [L1], .
If and , write . A Bézout identity then becomes , so by [L1]; symmetry gives the converse. Thus the criterion is representative independent.
Steps 1.1 and 1.2 prove the equivalence, and step 1.3 proves its final representative-independence assertion.
Depends on
- The unit group $(\mathbb{Z}/n)^\times$ and Euler's totient $\varphi(n)=\lvert(\mathbb{Z}/n)^\times\rvert$ for $n\ge1$
- 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
- Common divisor, and the greatest common divisor $\gcd(a,b)$, with the convention $\gcd(0,0) := 0$
- Coprime integers: $\gcd(a,b) = 1$
- $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$
- 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$
Used by
- φ(1)=1, and φ(p)=p-1 for every prime p Corollary
- (ℤ/12)^×={[1],[5],[7],[11]} and φ(12)=4 Example
- (ℤ/8)^×={[1],[3],[5],[7]} is not cyclic because every element squares to [1] Example
- A modulus n>1 is composite exactly when two nonzero classes in ℤ/n have product [0]ₙ Example
- Euler's product formula φ(n)=n∏_p∣ n(1-1/p)=∏_pᵏ∥ n(pᵏ-pᵏ⁻¹) for n≥1, stated through a finite injective list of its prime divisors Theorem
- Euler's theorem: if n≥1 and gcd(a,n)=1, then a^φ(n)≡1pmod n Theorem
- For a prime p and k≥1, φ(pᵏ)=pᵏ-pᵏ⁻¹ Theorem
- For every positive integer n, ∑_d∣ n, d>0φ(d)=n Theorem
- For every prime p, the two operations on ℤ/p make it a field Theorem
Dependency tree · next 3 levels
Direct dependencies and their dependencies through the next three levels: 70 results over 18 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
- K. Conrad, Modular Arithmetic (standard reference, not scraped)
- Mathematics LibreTexts, Euler's phi Function (standard reference, not scraped)
- UW Oshkosh, Number Theory Notes 3 (standard reference, not scraped)