Proof of the generalized Euclid's lemma
Proof
We use Bézout's identity.
- Let , and be integers with , and let and be coprime, so .
- By Bézout's identity, there are integers and with .
- Multiplying by gives .
- Since divides , there is an integer with . Then .
- So , and is an integer.
- Hence .
Idea
Coprimality gives . Multiplying by writes as a sum of two multiples of : one is visibly a multiple, and the other is a multiple of .
Reading path
To understand this page from the ground up, read these 23 pages in order. The foundations come first. The path takes the proofs Proof of Bézout's identity, Proof of the commutativity of addition by induction, Proof of strong induction from ordinary induction, Proof of the well-ordering principle from strong induction, Proof of the division algorithm.
Show the path as a graph
- no evidence level
- Definition by recursion concept
- Divisibility definition
- Mathematical induction concept
- Natural numbers object
- Peano axioms concept
- Greatest common divisor definition
- Successor function definition
- Coprime integers definition
- Addition of natural numbers definition
- The successor function is injective statement
- Zero is not a successor statement
- Proof of the commutativity of addition by induction proof
- Order on the natural numbers definition
- Commutativity of addition statement
- Proof of strong induction from ordinary induction proof
- Strong induction statement
- Proof of the well-ordering principle from strong induction proof
- Well-ordering principle statement
- Proof of the division algorithm proof
- Division algorithm statement
- Proof of Bézout's identity proof
- Bézout's identity statement
- Proof of the generalized Euclid's lemma proof
Where this leads
230 pages build on this one.
- −1 is a square modulo p if and only if p is not 3 modulo 4
- A finite group is nilpotent iff it is the product of its Sylow subgroups
- Uniqueness of finite fields of a given order
- Hensel's lemma
- Legendre's formula
- Eisenstein's criterion
- Fermat pseudoprime
- Gauss's lemma on quadratic residues
- Freshman's dream
- Generalized Euclid's lemma
- Wilson's theorem
- Subgroups of a finite cyclic group correspond to divisors of its order
- Fermat's theorem on sums of two squares
- Density of the irrationals
- Sum of two squares theorem
- Galois field
- Chinese remainder theorem for non-coprime moduli
- Existence of primitive roots modulo a prime
- Euclid's lemma
- Lucas–Lehmer test
- Converse of Wilson's theorem
- Classification of finite abelian groups
- Pépin's test
- Möbius inversion formula
- Rational root theorem
- Finite p-groups are nilpotent
- Fundamental theorem of arithmetic
- P-adic valuation of a product
- Law of quadratic reciprocity
- Fermat's right triangle theorem
- Product of cyclic groups is cyclic iff the orders are coprime
- Subfields of a finite field
- Fixed points of a p-group action
- Second Sylow theorem
- Groups of order p squared are abelian
- Cancellation in congruences
- The number of Sylow subgroups is the index of the normaliser
- The Möbius function is the inverse of the constant function 1
- Totient of a prime power
- Fermat's little theorem in the form a^p = a
- Euler product formula
- Finite subgroups of the multiplicative group of a field are cyclic
- Impossibility of doubling the cube
- Irrationality of the square root of 2
- Primitive root theorem
- Fermat's Last Theorem for n = 4
- The multiplicative group of a finite field is cyclic
- Existence of nontrivial solutions of Pell's equation
- Impossibility of trisecting the angle
- A subgroup whose index is the smallest prime divisor of the order is normal
- Chinese remainder theorem
- Multiplicativity of the totient function
- Automorphism group of a cyclic group
- Frobenius endomorphism
- Solutions of Pell's equation are powers of the fundamental solution
- Abelian simple groups have prime order
- Cauchy's theorem
- Lifting-the-exponent lemma
- Fundamental solution of Pell's equation
- Classification of Pythagorean triples
- Lagrange's four-square theorem
- Fermat's little theorem
- The number of Sylow subgroups divides the index
- Euler's criterion
- A finite abelian group is cyclic iff its exponent equals its order
- Irrationality of square roots of non-squares
- Multiplicativity of the Legendre symbol
- First supplement to quadratic reciprocity
- Dirichlet convolution of multiplicative functions is multiplicative
- Third Sylow theorem
- The group of units of Z/pZ is cyclic
- Frattini argument
- Fraction in lowest terms
- Gcd of Fibonacci numbers
- Structure theorem for finitely generated abelian groups
- Lucas's theorem
- A nontrivial finite p-group has nontrivial centre
- Irreducibility of the cyclotomic polynomials over the rationals
- Primitive element theorem
- Miller–Rabin primality test
- Fundamental theorem of Galois theory
- Existence of finite fields of every prime power order
- Carmichael number
- Frobenius coin problem
- First Sylow theorem
- Multiplicativity of the Möbius function
- Kummer's theorem
- If 2^n + 1 is prime then n is a power of 2
- Frobenius automorphism of a finite field
- Order of a power
- Euclid–Euler theorem
- A prime is a Gaussian prime if and only if it is 3 modulo 4
- Number of elements of each order in a cyclic group
- Eisenstein's lemma
- A root of an integer is an integer or irrational
- Gauss–Wantzel theorem
- The order modulo p divides p − 1
- Primitive element of a finite field
- Groups of order pq
- Irrationality of the square root of a prime
- Quadratic reciprocity for the Jacobi symbol
- Second supplement to quadratic reciprocity
- Proof of the description of the subfields of a finite field
- Proof of the impossibility of doubling the cube
- Proof of the primitive root theorem
- Proof that a root of an integer is an integer or irrational
- Proof that the number of Sylow subgroups is the index of the normaliser
- Primitive polynomial over a finite field
- Proof of the first Sylow theorem by induction with the class equation
- Proof of the gcd formula for Fibonacci numbers by the Euclidean algorithm
- Fourier analysis on the Boolean cube
- Proof of Gauss's lemma on quadratic residues
- Proof of Eisenstein's lemma
- Proof of the Chinese remainder theorem
- Proof of the irrationality of the square root of a prime
- Proof of the rational root theorem
- Galois group of a prime degree polynomial with two nonreal roots
- Proof that finite p-groups are nilpotent
- Proof of Fermat's little theorem by rearrangement
- Proof of the sum of two squares theorem
- Proof of the Euclid–Euler theorem
- Proof of Pépin's test
- Proof of the classification of Pythagorean triples
- Characters of a finite abelian group form a basis
- Proof that a nontrivial finite p-group has nontrivial centre by the class equation
- Proof of the second Sylow theorem
- Artin reciprocity law
- Proof of Fermat's theorem on sums of two squares by Thue's lemma
- Proof of the irrationality of the square root of 2 by lowest terms
- Proof of the Frobenius coin problem for two coins
- Proof of Fermat's right triangle theorem by infinite descent
- Weil conjectures
- Shor's algorithm
- Proof of the multiplicativity of the Möbius function
- Divisibility poset
- Proof of Euclid's lemma
- Hall's theorem on solvable groups
- Proof of Kummer's theorem from Legendre's formula
- Proof of the Lucas–Lehmer test
- Proof that finite subgroups of the multiplicative group of a field are cyclic
- Proof of the law of quadratic reciprocity by counting lattice points
- Proof of the uniqueness of finite fields of a given order
- Proof of Eisenstein's criterion
- Proof that the subgroups of a finite cyclic group correspond to the divisors of its order
- Prime-factor FFT algorithm
- Cyclotomic field
- Euler product for multiplicative functions
- Proof that a subgroup whose index is the smallest prime divisor of the order is normal
- Proof that the p-adic valuation of a product is the sum of the valuations
- Proof of the fundamental theorem of arithmetic
- Non-vanishing of the zeta function on the line Re s = 1
- Proof of the third Sylow theorem
- Standard conjectures on algebraic cycles
- Proof that −1 is a square modulo p if and only if p is not 3 modulo 4
- Hall subgroup
- Coxeter's integral octonions
- Proof that a product of two finite cyclic groups is cyclic iff their orders are coprime
- Beam propagation method
- Proof of the multiplicativity of the Legendre symbol from Euler's criterion
- Cubic reciprocity
- Proof that the solutions of Pell's equation are powers of the fundamental solution
- Proof of Fermat's little theorem in the form a^p = a
- Proof of Fermat's Last Theorem for n = 4
- Proof of the existence of nontrivial solutions of Pell's equation by Dirichlet approximation
- Proof of the Euler product formula
- Proof that a prime is a Gaussian prime if and only if it is 3 modulo 4
- Sylow theorems
- Frattini subgroup
- Lattice-ordered group
- Proof that the group of units of Z/pZ is cyclic by counting elements of each order
- Proof of Lagrange's four-square theorem by descent
- Proof that groups of order p squared are abelian
- Proof of the irreducibility of the cyclotomic polynomials by reduction modulo primes
- Proof of Euler's criterion by counting quadratic residues
- Hilbert class field
- A finite abelian group is isomorphic to its dual
- Proof of quadratic reciprocity for the Jacobi symbol
- Proof of the Frattini argument
- Proof of the primitive element theorem
- Proof of the multiplicativity of the totient function
- Proof of the density of the irrationals
- Proof of the existence and uniqueness of a fraction in lowest terms
- Proof of the second supplement to quadratic reciprocity from Gauss's lemma
- Number of characters of a finite abelian group
- Proof that if 2^n + 1 is prime then n is a power of 2
- Proof that a cyclic group of order n has phi(d) elements of order d
- Proof of the freshman's dream
- Galois group of a finite field extension
- Proof that the number of Sylow subgroups divides the index
- Congruent number problem
- Perfect field
- Proof that a finite group is nilpotent iff it is the product of its Sylow subgroups
- Proof that the order modulo p divides p − 1
- Proof that a finite abelian group is cyclic iff its exponent equals its order
- Proof of the existence of finite fields of every prime power order
- Proof of Hensel's lemma by Newton steps
- Proof of the formula for the order of a power
- Proof of the existence of primitive roots modulo a prime by counting elements of each order
- Proof of the impossibility of trisecting the angle
- Structure theorem for compactly generated LCA groups
- Hurwitz quaternions
- Left-orderable group
- Proof of the lifting-the-exponent lemma for odd primes
- Proof of Wilson's theorem by pairing inverses
- Quintic equation
- Orthogonality of characters
- Fast Fourier transform
- Proof of the Möbius inversion formula
- Proof of the first supplement to quadratic reciprocity from Euler's criterion
- 24-cell
- Pseudo-spectral method
- Proof that the Möbius function is the inverse of the constant function 1
- Proof of the fundamental theorem of Galois theory
- Proof of the Gauss–Wantzel theorem
- Perfect closure
- Proof of the formula for the totient of a prime power
- Torsion-free group
- Proof of the fixed point congruence for p-group actions
- Quartic reciprocity
- Impossibility of the classical construction problems
- Proof of Legendre's formula by counting multiples of prime powers
- Proof of the irrationality of square roots of non-squares
- Proof that the Dirichlet convolution of multiplicative functions is multiplicative
- Artin's theorem on fixed fields
- AKS primality test
- Proof that the multiplicative group of a finite field is cyclic
- Proof of cancellation in congruences
- Integer factorization
- Proof of Lucas's theorem by generating functions
- Orderable group
Further reading
About this page
| Tag | 3JF4PFZFYZ |
|---|---|
| URI | m2://3JF4PFZFYZ |
| Kind | proof |
| Writing | W0 stub |
| MSC | 11A05 |
| Proves | Generalized Euclid's lemma |
| Uses | Coprime integers, Bézout's identity, Divisibility |
| Changed | 4 November 2026 |
Markdown · JSON · Edit on GitHub
What this page needs for W1
- an inventory row: the row of the inventory that the node accounts for (0 of 1)
The writing levels say how complete the text of a page is. They do not measure its truth.
What links here
No page links to this page yet.