If you're seeing this message, it means we're having trouble loading external resources on our website.

If you're behind a web filter, please make sure that the domains *.kastatic.org and *.kasandbox.org are unblocked.

Main content

The Euclidean Algorithm

Recall that the Greatest Common Divisor (GCD) of two integers A and B is the largest integer that divides both A and B.
The Euclidean Algorithm is a technique for quickly finding the GCD of two integers.

The Algorithm

The Euclidean Algorithm for finding GCD(A,B) is as follows:
  • If A = 0 then GCD(A,B)=B, since the GCD(0,B)=B, and we can stop.  
  • If B = 0 then GCD(A,B)=A, since the GCD(A,0)=A, and we can stop.  
  • Write A in quotient remainder form (A = B⋅Q + R)
  • Find GCD(B,R) using the Euclidean Algorithm since GCD(A,B) = GCD(B,R)

Example:

Find the GCD of 270 and 192
  • A=270, B=192
  • A ≠0
  • B ≠0
  • Use long division to find that 270/192 = 1 with a remainder of 78. We can write this as: 270 = 192 * 1 +78
  • Find GCD(192,78), since GCD(270,192)=GCD(192,78)
A=192, B=78
  • A ≠0
  • B ≠0
  • Use long division to find that 192/78 = 2 with a remainder of 36. We can write this as:
  • 192 = 78 * 2 + 36
  • Find GCD(78,36), since GCD(192,78)=GCD(78,36)
A=78, B=36
  • A ≠0
  • B ≠0
  • Use long division to find that 78/36 = 2 with a remainder of 6. We can write this as:
  • 78 = 36 * 2 + 6
  • Find GCD(36,6), since GCD(78,36)=GCD(36,6)
A=36, B=6
  • A ≠0
  • B ≠0
  • Use long division to find that 36/6 = 6 with a remainder of 0. We can write this as:
  • 36 = 6 * 6 + 0
  • Find GCD(6,0), since GCD(36,6)=GCD(6,0)
A=6, B=0
  • A ≠0
  • B =0, GCD(6,0)=6
So we have shown:
GCD(270,192) = GCD(192,78) = GCD(78,36) = GCD(36,6) = GCD(6,0) = 6
GCD(270,192) = 6

Understanding the Euclidean Algorithm

If we examine the Euclidean Algorithm we can see that it makes use of the following properties:
  • GCD(A,0) = A
  • GCD(0,B) = B
  • If A = B⋅Q + R and B≠0 then GCD(A,B) = GCD(B,R) where Q is an integer, R is an integer between 0 and B-1
The first two properties let us find the GCD if either number is 0. The third property lets us take a larger, more difficult to solve problem, and reduce it to a smaller, easier to solve problem.
The Euclidean Algorithm makes use of these properties by rapidly reducing the problem into easier and easier problems, using the third property,  until it is easily solved by using one of the first two properties.
We can understand why these properties work by proving them.
We can prove that GCD(A,0)=A is as follows:
  • The largest integer that can evenly divide A is A.
  • All integers evenly divide 0, since for any integer, C, we can write C ⋅ 0 = 0. So we can conclude that A must evenly divide 0.
  • The greatest number that divides both A and 0 is A.
The proof for GCD(0,B)=B is similar. (Same proof, but we replace A with B).
To prove that GCD(A,B)=GCD(B,R) we first need to show that GCD(A,B)=GCD(B,A-B).
Suppose we have three integers A,B and C such that A-B=C.
Proof that the GCD(A,B) evenly divides C
The GCD(A,B), by definition, evenly divides A. As a result, A must be some multiple of GCD(A,B). i.e. X⋅GCD(A,B)=A where X is some integer
The GCD(A,B), by definition, evenly divides B. As a result,  B must be some multiple of GCD(A,B). i.e. Y⋅GCD(A,B)=B where Y is some integer
A-B=C gives us:
  • X⋅GCD(A,B) - Y⋅GCD(A,B) = C
  • (X - Y)⋅GCD(A,B) = C
So we can see that GCD(A,B) evenly divides C.
An illustration of this proof  is shown in the left portion of the figure below:
Proof that the GCD(B,C) evenly divides A
The GCD(B,C), by definition, evenly divides B. As a result, B must be some multiple of GCD(B,C). i.e. M⋅GCD(B,C)=B where M is some integer
The GCD(B,C), by definition, evenly divides C. As a result,  C must be some multiple of GCD(B,C). i.e. N⋅GCD(B,C)=C where N is some integer
A-B=C gives us:
  • B+C=A
  • M⋅GCD(B,C) + N⋅GCD(B,C) = A
  • (M + N)⋅GCD(B,C) = A
So we can see that GCD(B,C) evenly divides A.
An illustration of this proof  is shown in the figure below
Proof that GCD(A,B)=GCD(A,A-B)
  • GCD(A,B) by definition, evenly divides B.
  • We proved that GCD(A,B) evenly divides C.
  • Since the GCD(A,B) divides both B and C evenly it is a common divisor of B and C.
GCD(A,B) must be less than or equal to, GCD(B,C), because GCD(B,C) is the “greatest” common divisor of B and C.
  • GCD(B,C) by definition, evenly divides B.
  • We proved that GCD(B,C) evenly divides A.
  • Since the GCD(B,C) divides both A and B evenly it is a common divisor of A and B.
GCD(B,C) must be less than or equal to, GCD(A,B), because GCD(A,B) is the “greatest” common divisor of A and B.
Given that GCD(A,B)≤GCD(B,C) and GCD(B,C)≤GCD(A,B) we can conclude that:
GCD(A,B)=GCD(B,C)
Which is equivalent to:
GCD(A,B)=GCD(B,A-B)
An illustration of this proof  is shown in the right portion of the figure below.
Proof that GCD(A,B) = GCD(B,R)
We proved that GCD(A,B)=GCD(B,A-B)
The order of the terms does not matter so we can say GCD(A,B)=GCD(A-B,B)
We can repeatedly apply GCD(A,B)=GCD(A-B,B) to obtain:
GCD(A,B)=GCD(A-B,B)=GCD(A-2B,B)=GCD(A-3B,B)=...=GCD(A-Q⋅B,B)
But A= B⋅Q + R so  A-Q⋅B=R
Thus GCD(A,B)=GCD(R,B)
The order of terms does not matter, thus:
GCD(A,B)=GCD(B,R)

Want to join the conversation?

  • blobby green style avatar for user evelyn mazariegos
    Can you guys show a video of this please maybe if someone speaks about it step by step and show the visual I can or others too might understand it better. thanks
    (114 votes)
    Default Khan Academy avatar avatar for user
  • blobby green style avatar for user JohnBltz
    I'm having a really hard time understating why "If A = B⋅Q + R and B≠0 then GCD(A,B) = GCD(B,R) where Q is an integer, R is an integer between 0 and B-1" is true...
    (15 votes)
    Default Khan Academy avatar avatar for user
    • blobby green style avatar for user Sherwood Botsford
      If the GCD divides both A and B, it will divide A-B.
      Suppose that D is the GCD of A and B.
      The D divides both and and B by definition.
      So A = kD and B= jD for k and j some integer.
      A-B = kD - jD
      factoring A-B = (k-j)D
      but k-j is just another integer.


      Example: Consider 72 and 48. GCD is 12.

      72 -48 = 36, also a multiple of 12.

      So GCD (A,B) = GCD of (A-B, B) then we can repeat this as many times as we wish. So lets subtract all the B's we can from A. Divide A by B with a quotient Q and remainder R.

      Turning that around A=QB +R.
      So GCD (A,B) = GCD (QB+R,B) substitution.
      But remember that B is divisible by D. So is QB.
      so GCD(QB+R,B) = GCD(R,B)

      This help any?
      (32 votes)
  • blobby green style avatar for user Kingsley Pinder
    what is the purpose of the Euclldan Algorithm?
    (13 votes)
    Default Khan Academy avatar avatar for user
    • blobby green style avatar for user David Mears
      it leverages multiplication and subtraction, which humans are fairly good at, to make fractions like 15996751/3870378 reducible. Also useful in scaling equations down to their simplest integer representation in one step, given with extra integers, GCD(C,GCD(A,B)) is equivalent to GCD(A,B,C). It's been around for over two thousand years and mathematicians have bent it to many purposes , but just the first bit should be justification.
      (19 votes)
  • hopper cool style avatar for user Rathony
    What are some practical applications the Euclidean Algorithm might be used in?
    I cannot imagine a situation where we might need to use it.
    (7 votes)
    Default Khan Academy avatar avatar for user
  • winston default style avatar for user Chris K
    I'm trying to wrap my head around:

    Find GCD(B,R) using the Euclidean Algorithm since GCD(A,B) = GCD(B,R)

    How is it that GCD(A,B) = GCD(B,R)?

    Maybe someone can help make this a little more intuitive for me?
    (2 votes)
    Default Khan Academy avatar avatar for user
    • male robot hal style avatar for user Cameron
      This may be an intuitive way to think about it.
      Keep in mind that this is hand-wavy, and not a proof.

      Suppose A and B are made up of chunks of size G
      If we subtract B from A the difference will also be some number of chunks of size G
      In fact, we can subtract several Bs from A and the difference will still be some number of chunks of size G
      If we subtract as many Bs as we can from A, then the remaining amount is the remainder when we divide A by B.
      (Remember from the quotient remainder theorem A - B * Q = R )
      And since it it just a difference of several Bs from A, that remainder is some number of chunks of size G.

      So:
      gcd(A,B) = G (A and B are made up of chunks of size G)
      gcd(B,A-B) = G (A-B is also made up of chunks of size G)
      gcd(B,R) = G (The remainder R which is just A-B*Q is also made up of chunks of size G)

      So:
      gcd(A,B) = gcd(B,R)
      (18 votes)
  • piceratops ultimate style avatar for user Saqib Rahman
    Can you please do a tutorial video/article on Bezout relation?
    (5 votes)
    Default Khan Academy avatar avatar for user
  • blobby green style avatar for user Prakash Wadhwani
    Where is the next article on extended Euclidean Alg?
    (5 votes)
    Default Khan Academy avatar avatar for user
  • blobby green style avatar for user mat.auburn
    When will this be continued! It's been months!
    (5 votes)
    Default Khan Academy avatar avatar for user
  • leafers sapling style avatar for user Delirious.Mintii
    a=bq+r If b and r are known, how would I solve to find a and q?
    I have two equations and I need to find the least possible value of a:
    a=3q+2 and a=5q+1
    (3 votes)
    Default Khan Academy avatar avatar for user
  • blobby green style avatar for user kishitanimker2385
    if d is HCF of 40 and 65, find the value of integers x and y which satisfy d=40x+65y
    (2 votes)
    Default Khan Academy avatar avatar for user