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

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

• If gcd(a,n)=1, then a^λ(n)≡1 (mod n) Corollary
• If n has a primitive root, gcd(a,n)=1, m≥1, and xᵐ≡ a (mod n) is solvable, then it has exactly gcd(φ(n),m) solution classes modulo n Corollary
• The discriminant counts roots of Ax²+Bx+C≡0 (mod p) for odd prime p∤ A Corollary
• The generators of a cyclic group of order m are the gᵃ with gcd(a,m)=1, so there are φ(m) of them Corollary
• φ(1)=1, and φ(p)=p-1 for every prime p Corollary
• Two quadratic nonresidues modulo 15 can have a nonresidue product Counterexample
• Quadratic residues and nonresidues modulo an integer Definition
• (ℤ/12)^×={[1],[5],[7],[11]} and φ(12)=4 Example
• (ℤ/8)^×={[1],[3],[5],[7]} is not cyclic because every element squares to [1] Example
• 2 is primitive modulo every power of 5 Example
• A modulus n>1 is composite exactly when two nonzero classes in ℤ/n have product [0]ₙ Example
• Aut(C₈)≅ C₂× C₂ Example
• Hol(C₈) is the group of affine maps x↦ ax+b with a∈{1,3,5,7} Example
• The unique Sylow p-subgroup of Aff(ℤ/p²) Example
• A cyclic group of order n has exactly φ(n) generators Lemma
• For an odd prime p and a primitive root g modulo p, at least one of g and g+p is primitive modulo p² Lemma
• For k≥3, the class of 5 has order 2ᵏ⁻² modulo 2ᵏ Lemma
• For odd prime p, p∤ u, and k≥1, the class of 1+pu has order pᵏ⁻¹ modulo pᵏ Lemma
• A unit square modulo an odd integer has Jacobi symbol one Proposition
• For fixed odd modulus, the Jacobi symbol is a homomorphism on the unit group Proposition
• Quadratic residuosity is representative-independent and the residues are the image of squaring Proposition
• Aut(Cₙ)≅(ℤ/nℤ)^× Theorem
• Euler's criterion: if n has a primitive root, gcd(a,n)=1, and m≥1, then xᵐ≡ a (mod n) is solvable if and only if a^φ(n)/gcd(φ(n),m)≡1 (mod n) Theorem
• 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)≡1 (mod 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
• For gcd(n,q)=1 the image of Gal(F_q(μₙ)/F_q) in (ℤ/n)^× is generated by [q] Theorem
• For k≥3, (ℤ/2ᵏℤ)^×≅ C₂× C_2ᵏ⁻², generated uniquely as (-1)^ε5ʲ Theorem
• Gauss's quadratic-residue lemma Theorem
• K(μₙ)/K is Galois and σ↦ a_σ embeds its Galois group into (ℤ/n)^× Theorem
• Over a commutative ℚ-algebra, CYC(A) has generating function ∑_k≥ 1φ(k)/k log1/1-A(xᵏ) Theorem
• The Legendre symbol is multiplicative for all integer numerators Theorem

Dependency tree · two levels

31 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

• 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)