← Back to catalogue
Research draft

greatest common divisor

vr.tr.greatest-common-divisor · XCT.QTY

Let an agent handle the greatest common divisor by definition, computation, properties and applications.

Thing Registry Cross-cutting context

Research draft, second pass

A second pass drafted this model: the structure a model of this thing needs, and what is known about it in the world. The line under this one says how the second half was obtained - researched against sources, or recalled without web access, in which case nothing here was read anywhere and every claim is a lead to verify. Unreviewed either way.

written by Claude from model knowledge without web access - no source was read, every claim is a lead to verify

Researched by: Claude

Purpose and description

Let an agent handle the greatest common divisor by definition, computation, properties and applications.

The largest positive integer that divides each of two or more integers without remainder, written gcd(a, b); computed efficiently by the Euclidean algorithm, and used to simplify fractions.

What it is for: Simplifying fractions, number theory and cryptography.

It can be compute gcd by the Euclidean algorithm; simplify fractions; find Bezout coefficients; relate gcd and lcm.

Distinguishing features

Largest shared divisor

Efficient algorithm

gcd(a, b) x lcm(a, b) = |a x b|

Basis of coprimality

What it looks like

A number resulting from computation.

How it is recognised

Notation gcd(a, b)

Also called highest common factor

Least common multiple is the related dual

Related models

is a kind of - category

common divisor

is computed by - method

Euclidean algorithm

is related to - dual

least common multiple

is related to - concept

divisor

In practice

Families and kinds

gcd of integers

gcd of polynomials

extended Euclidean algorithm

binary gcd algorithm

Standards and regulation

ISO 80000-2 notation

Failure modes and hazards

Arithmetic errors

Confusing gcd and lcm

Where this came from

wikidata · CC0 1.0

Source repository Registry entry point

Drafted structure

Bundle to layer to finding to question, as the second pass will find it: 4 bundles · 8 layers · 8 findings · 16 questions.

Compute Finding it.

Algorithms compute gcd.

Value

Result.

Value

GCD value.

  1. What is the gcd of these numbers? measurement
  2. Which algorithm was used? definition

Steps

Euclidean algorithm.

Steps

Algorithm steps.

  1. What are the steps of the Euclidean algorithm here? action
  2. How many steps are needed? measurement
Properties Theory.

Properties enable proofs.

Bezout

Coefficients.

Bezout

Bezout identity.

  1. What integers x and y satisfy ax + by = gcd(a, b)? measurement
  2. How are they found? action

Coprime

gcd equals 1.

Coprime

Coprimality.

  1. Are the numbers coprime? boundary
  2. Why does it matter? definition
Applications Uses.

gcd appears widely.

Fractions

Simplifying.

Fractions

Simplifying fractions.

  1. How does the gcd simplify this fraction? action
  2. Is the result in lowest terms? boundary

Cryptography

RSA.

Cryptography

Cryptography.

  1. How is the gcd used in cryptographic algorithms such as RSA key generation? definition
  2. Which step uses it? definition
Learning Teaching.

Clear terms help.

Terms

HCF and GCD.

Terms

Terminology.

  1. Is it called gcd or highest common factor in this curriculum? provenance
  2. Are they the same? definition

LCM

Relation.

LCM

Relation to lcm.

  1. How are gcd and lcm related? definition
  2. Can the relation be checked on an example? action

What the second pass must settle

  • Should the Euclidean algorithm be a separate entry?
  • How should polynomial gcd be linked?
  • How should terminology variants be recorded?
Draft as JSON