GCD calculator
The greatest common divisor of 1071 and 462 is 21, found in three steps of Euclid's method without factoring either number. Enter two integers, negative or zero included, and use the result to reduce a fraction such as 462/1071 to 22/51. Free in your browser.
- Free
- Runs in your browser
- No sign-up
- Your data stays on your device
Run — free
Worked example
- A
- 1,071
- B
- 462
- Gcd
- 21
Signs are ignored, a single zero input is handled by the rule gcd(n, 0) = |n|, and the only rejected case is the mathematically undefined gcd(0, 0).
What the greatest common divisor actually is
The greatest common divisor of two integers is the largest positive whole number that divides both of them exactly. For 1071 and 462 it is 21, because 1071 = 21 × 51 and 462 = 21 × 22, and no larger integer divides both. When the result is 1 the two numbers are called coprime: they share no factor at all.
The concept is ancient — it sits at the heart of Euclid's Elements — and it is still the fastest way to answer very practical questions: reducing a fraction to its lowest terms, checking whether two periodic processes will ever align, or simplifying a ratio before you display it.
How the Euclidean algorithm computes it
The implementation is Euclid's subtraction-free version: repeatedly replace the larger number by the remainder of dividing the larger by the smaller, until the remainder is zero; the last non-zero remainder is the answer. For 1071 and 462 that is 1071 mod 462 = 147, then 462 mod 147 = 21, then 147 mod 21 = 0, so the result is 21.
The loop runs in O(log min(a, b)) iterations, which means even numbers near the safe-integer limit finish in a handful of steps, with no factorization and no floating point involved. Signs are removed first because divisibility does not depend on them, so gcd(-12, 18) is 6.
Where it fits in real work
Fraction reduction is the canonical use: divide numerator and denominator by their gcd and a fraction is in lowest terms, which is what billing engines, recipe scalers and ratio displays all need before presenting a number. It also underpins coprimality checks — a gcd of 1 is the test — and the Chinese remainder and modular-inverse machinery used in cryptography, where the gcd is the first step of the extended Euclidean algorithm.
The capability runs on our edge with nothing stored: the two integers arrive, the divisor leaves, and no record of your numbers is kept.
What you can do with it
Reduce fractions to lowest terms
Divide numerator and denominator by their gcd before storing or displaying a ratio, so 462/1071 becomes 22/51.
Check whether two numbers are coprime
A result of 1 means the pair shares no factor, the precondition for many scheduling, hashing and cryptographic constructions.
Align periodic processes
Combined with the lcm, the gcd tells you when two cycles of different lengths coincide and how to split work into equal batches.
FAQ
Can the inputs be negative?
Yes. Signs are ignored because divisibility does not depend on them: gcd(-12, 18) returns 6, always as a positive integer.
What happens with zero?
gcd(n, 0) returns |n| for any non-zero n.
How large can the integers be?
Any safe integer in JavaScript terms, up to 2^53 − 1 in magnitude. Values outside that range are rejected rather than computed imprecisely.
Which algorithm is used?
The Euclidean algorithm: repeated remainder steps until the remainder is zero. It runs in O(log min(a, b)) iterations with no factorization and no floating point.
What does it mean when the GCD is 1?
It means the two numbers are coprime: they share no factor other than 1. A fraction made of such numbers is already in lowest terms, and many scheduling and encryption methods require exactly this property.
Related tools
For developers — API access
Everything on this page is available programmatically. This section is for teams who want to wire it into their own systems; everyone else can just use the tool above.
API endpoint
Prefer to automate it? One authenticated POST creates the task; the result comes back by webhook or a signed link. The same capability also runs here on the web, by email and from Telegram — and soon from our app too.
Call it from your stack
curl -X POST https://api.kit.forhosting.com/math/gcd \
-H "Authorization: Bearer $KIT_KEY" \
-H "Content-Type: application/json" \
-d '{"a":1071,"b":462}'const res = await fetch("https://api.kit.forhosting.com/math/gcd", {
method: "POST",
headers: {
"Authorization": `Bearer ${process.env.KIT_KEY}`,
"Content-Type": "application/json"
},
body: JSON.stringify({
"a": 1071,
"b": 462
})
});
const { task_id } = await res.json();import os, requests
res = requests.post(
"https://api.kit.forhosting.com/math/gcd",
headers={"Authorization": f"Bearer {os.environ['KIT_KEY']}"},
json={
"a": 1071,
"b": 462
},
)
task_id = res.json()["task_id"]<?php
$res = file_get_contents("https://api.kit.forhosting.com/math/gcd", false, stream_context_create([
"http" => [
"method" => "POST",
"header" => "Authorization: Bearer " . getenv("KIT_KEY") . "\r\nContent-Type: application/json",
"content" => '{"a":1071,"b":462}',
],
]));
$task = json_decode($res, true);body := bytes.NewBufferString(`{"a":1071,"b":462}`)
req, _ := http.NewRequest("POST", "https://api.kit.forhosting.com/math/gcd", body)
req.Header.Set("Authorization", "Bearer "+os.Getenv("KIT_KEY"))
req.Header.Set("Content-Type", "application/json")
res, _ := http.DefaultClient.Do(req)Example request
{
"a": 1071,
"b": 462
}Example response
{
"task_id": "tsk_a1b2c3d4e5f6a1b2c3d4e5f6",
"type": "math.gcd",
"status": "queued",
"_links": {
"result": "/tasks/tsk_…/result"
}
}The API is asynchronous: the call returns a task_id immediately and the result arrives by webhook. Polling is capped at 1 req/s per task.
Pricing
Published price — no tokens, no invented credits. A failed task is never charged.
Errors
| HTTP | Code | Meaning |
|---|---|---|
401 | unauthorized | Missing or invalid API key. |
402 | insufficient_balance | Your balance doesn't cover the task price. |
404 | unknown_type | That task type doesn't exist. |
429 | rate_limited | Too many requests. Use the webhook instead of polling. |
Technical notes
The greatest common divisor API takes two integers and returns the largest positive integer that divides both of them without a remainder, computed with the classic Euclidean algorithm. It is a small, exact tool: the same deterministic code runs free in your browser and behind the paid endpoint, so the number you see while testing is the number your pipeline will get in production.
What the greatest common divisor actually is
This endpoint takes the two integers as fields a and b, accepts either sign, and returns one object with the positive divisor. It never approximates and never rounds: integer in, exact integer out.
How the Euclidean algorithm computes it
The edge cases follow the standard convention: gcd(n, 0) = |n| for any non-zero n, while gcd(0, 0) is undefined and is rejected with an invalid_input error instead of a silent, wrong zero.
Where it fits in real work
You can try it free on this page with the same code that serves the API, and you only pay the $0.002 per request when you call it from your own systems, which makes it cheap enough to put inline in a data-cleaning step that processes millions of pairs.
Technical questions
What does it cost?
$0.002 per request. It is also free to run in your browser on this page with exactly the same code.