{"id":65476,"date":"2026-08-19T10:37:10","date_gmt":"2026-08-19T09:37:10","guid":{"rendered":"https:\/\/blog-admin.thethinkacademy.com\/?p=65476"},"modified":"2026-08-19T10:37:12","modified_gmt":"2026-08-19T09:37:12","slug":"euclidean-algorithm-guide","status":"publish","type":"post","link":"https:\/\/blog-admin.thethinkacademy.com\/blog\/2026\/08\/19\/euclidean-algorithm-guide\/","title":{"rendered":"Euclidean Algorithm Explained: Definition, Steps and Applications"},"content":{"rendered":"\n

The Euclidean algorithm is one of the oldest algorithms in mathematics \u2014 described by Euclid around 300 BCE \u2014 and one of the most useful. It finds the greatest common divisor (GCD) of two integers efficiently, using nothing more than repeated division with remainder. It is the foundation of a significant portion of computational number theory, appears in every major mathematics competition, and underlies the RSA cryptography system that secures most internet communication today.<\/p>\n\n\n\n

This guide explains the Euclidean algorithm step by step, proves why it works, extends it to find integer solutions to linear equations, and shows where it appears in the curriculum and in competition mathematics.<\/p>\n\n\n\n

\n\n\n\n

What Is the Euclidean Algorithm?<\/h2>\n\n\n\n

The Euclidean algorithm<\/strong> is a method for finding the greatest common divisor (GCD)<\/strong> of two positive integers \u2014 the largest integer that divides both without remainder.<\/p>\n\n\n\n

The key insight:<\/strong> gcd<\/mi>\u2061<\/mo>(<\/mo>a<\/mi>,<\/mo>b<\/mi>)<\/mo>=<\/mo>gcd<\/mi>\u2061<\/mo>(<\/mo>b<\/mi>,<\/mo>r<\/mi>)<\/mo><\/mrow>\\gcd(a, b) = \\gcd(b, r)<\/annotation><\/semantics><\/math>gcd(a,b)=gcd(b,r) where r<\/mi><\/mrow>r<\/annotation><\/semantics><\/math>r is the remainder when a<\/mi><\/mrow>a<\/annotation><\/semantics><\/math>a is divided by b<\/mi><\/mrow>b<\/annotation><\/semantics><\/math>b.<\/p>\n\n\n\n

This means you can replace the larger number with the smaller, and the smaller number with the remainder, repeating until the remainder is 0. The last non-zero remainder is the GCD.<\/p>\n\n\n\n

\n\n\n\n

The Euclidean Algorithm: Step by Step<\/h2>\n\n\n\n

Algorithm:<\/strong><\/p>\n\n\n\n

Given two positive integers a<\/mi>><\/mo>b<\/mi><\/mrow>a > b<\/annotation><\/semantics><\/math>a>b:<\/p>\n\n\n\n
    \n
  1. Divide a<\/mi><\/mrow>a<\/annotation><\/semantics><\/math>a by b<\/mi><\/mrow>b<\/annotation><\/semantics><\/math>b: write a<\/mi>=<\/mo>q<\/mi>\u22c5<\/mo>b<\/mi>+<\/mo>r<\/mi><\/mrow>a = q \\cdot b + r<\/annotation><\/semantics><\/math>a=q\u22c5b+r where 0<\/mn>\u2264<\/mo>r<\/mi><<\/mo>b<\/mi><\/mrow>0 \\leq r < b<\/annotation><\/semantics><\/math>0\u2264r<b<\/li>\n\n\n\n
  2. If r<\/mi>=<\/mo>0<\/mn><\/mrow>r = 0<\/annotation><\/semantics><\/math>r=0: the GCD is b<\/mi><\/mrow>b<\/annotation><\/semantics><\/math>b. Stop.<\/li>\n\n\n\n
  3. If r<\/mi>\u2260<\/mo>0<\/mn><\/mrow>r \\neq 0<\/annotation><\/semantics><\/math>r\ue020=0: replace (<\/mo>a<\/mi>,<\/mo>b<\/mi>)<\/mo><\/mrow>(a, b)<\/annotation><\/semantics><\/math>(a,b) with (<\/mo>b<\/mi>,<\/mo>r<\/mi>)<\/mo><\/mrow>(b, r)<\/annotation><\/semantics><\/math>(b,r) and go to Step 1.<\/li>\n<\/ol>\n\n\n\n

    Why it terminates:<\/strong> The remainders form a strictly decreasing sequence of non-negative integers \u2014 so the algorithm must reach 0 in a finite number of steps.<\/p>\n\n\n\n

    \"\"<\/a><\/figure>\n\n\n\n
    \n\n\n\n

    Worked Examples<\/h2>\n\n\n\n

    Example 1 \u2014 Finding gcd(252, 105)<\/h3>\n\n\n\n

    252<\/mn>=<\/mo>2<\/mn>\u00d7<\/mo>105<\/mn>+<\/mo>42<\/mn><\/mrow>252 = 2 \\times 105 + 42<\/annotation><\/semantics><\/math>252=2\u00d7105+42 105<\/mn>=<\/mo>2<\/mn>\u00d7<\/mo>42<\/mn>+<\/mo>21<\/mn><\/mrow>105 = 2 \\times 42 + 21<\/annotation><\/semantics><\/math>105=2\u00d742+21 42<\/mn>=<\/mo>2<\/mn>\u00d7<\/mo>21<\/mn>+<\/mo>0<\/mn><\/mrow>42 = 2 \\times 21 + 0<\/annotation><\/semantics><\/math>42=2\u00d721+0<\/p>\n\n\n\n

    Remainder is 0. Last non-zero remainder: 21<\/strong>.gcd<\/mi>\u2061<\/mo>(<\/mo>252<\/mn>,<\/mo>105<\/mn>)<\/mo>=<\/mo>21<\/mn><\/mrow>\\gcd(252, 105) = 21<\/annotation><\/semantics><\/math>gcd(252,105)=21<\/p>\n\n\n\n

    Check:<\/strong> 252<\/mn>=<\/mo>21<\/mn>\u00d7<\/mo>12<\/mn><\/mrow>252 = 21 \\times 12<\/annotation><\/semantics><\/math>252=21\u00d712 \u2713 and 105<\/mn>=<\/mo>21<\/mn>\u00d7<\/mo>5<\/mn><\/mrow>105 = 21 \\times 5<\/annotation><\/semantics><\/math>105=21\u00d75 \u2713<\/p>\n\n\n\n
    \n\n\n\n

    Example 2 \u2014 Finding gcd(1071, 462)<\/h3>\n\n\n\n

    1071<\/mn>=<\/mo>2<\/mn>\u00d7<\/mo>462<\/mn>+<\/mo>147<\/mn><\/mrow>1071 = 2 \\times 462 + 147<\/annotation><\/semantics><\/math>1071=2\u00d7462+147 462<\/mn>=<\/mo>3<\/mn>\u00d7<\/mo>147<\/mn>+<\/mo>21<\/mn><\/mrow>462 = 3 \\times 147 + 21<\/annotation><\/semantics><\/math>462=3\u00d7147+21 147<\/mn>=<\/mo>7<\/mn>\u00d7<\/mo>21<\/mn>+<\/mo>0<\/mn><\/mrow>147 = 7 \\times 21 + 0<\/annotation><\/semantics><\/math>147=7\u00d721+0 gcd<\/mi>\u2061<\/mo>(<\/mo>1071<\/mn>,<\/mo>462<\/mn>)<\/mo>=<\/mo>21<\/mn><\/mrow>\\gcd(1071, 462) = 21<\/annotation><\/semantics><\/math>gcd(1071,462)=21<\/p>\n\n\n\n
    \n\n\n\n

    Example 3 \u2014 Finding gcd(17, 13) (Consecutive-ish primes)<\/h3>\n\n\n\n

    17<\/mn>=<\/mo>1<\/mn>\u00d7<\/mo>13<\/mn>+<\/mo>4<\/mn><\/mrow>17 = 1 \\times 13 + 4<\/annotation><\/semantics><\/math>17=1\u00d713+4 13<\/mn>=<\/mo>3<\/mn>\u00d7<\/mo>4<\/mn>+<\/mo>1<\/mn><\/mrow>13 = 3 \\times 4 + 1<\/annotation><\/semantics><\/math>13=3\u00d74+1 4<\/mn>=<\/mo>4<\/mn>\u00d7<\/mo>1<\/mn>+<\/mo>0<\/mn><\/mrow>4 = 4 \\times 1 + 0<\/annotation><\/semantics><\/math>4=4\u00d71+0 gcd<\/mi>\u2061<\/mo>(<\/mo>17<\/mn>,<\/mo>13<\/mn>)<\/mo>=<\/mo>1<\/mn><\/mrow>\\gcd(17, 13) = 1<\/annotation><\/semantics><\/math>gcd(17,13)=1<\/p>\n\n\n\n

    When the GCD is 1, the two numbers are coprime<\/strong> (share no common factor other than 1). This is significant in number theory and cryptography.<\/p>\n\n\n\n

    \n\n\n\n

    Example 4 \u2014 Finding gcd(144, 89) (Fibonacci numbers!)<\/h3>\n\n\n\n

    144<\/mn>=<\/mo>1<\/mn>\u00d7<\/mo>89<\/mn>+<\/mo>55<\/mn><\/mrow>144 = 1 \\times 89 + 55<\/annotation><\/semantics><\/math>144=1\u00d789+55 89<\/mn>=<\/mo>1<\/mn>\u00d7<\/mo>55<\/mn>+<\/mo>34<\/mn><\/mrow>89 = 1 \\times 55 + 34<\/annotation><\/semantics><\/math>89=1\u00d755+34 55<\/mn>=<\/mo>1<\/mn>\u00d7<\/mo>34<\/mn>+<\/mo>21<\/mn><\/mrow>55 = 1 \\times 34 + 21<\/annotation><\/semantics><\/math>55=1\u00d734+21 34<\/mn>=<\/mo>1<\/mn>\u00d7<\/mo>21<\/mn>+<\/mo>13<\/mn><\/mrow>34 = 1 \\times 21 + 13<\/annotation><\/semantics><\/math>34=1\u00d721+13 21<\/mn>=<\/mo>1<\/mn>\u00d7<\/mo>13<\/mn>+<\/mo>8<\/mn><\/mrow>21 = 1 \\times 13 + 8<\/annotation><\/semantics><\/math>21=1\u00d713+8 13<\/mn>=<\/mo>1<\/mn>\u00d7<\/mo>8<\/mn>+<\/mo>5<\/mn><\/mrow>13 = 1 \\times 8 + 5<\/annotation><\/semantics><\/math>13=1\u00d78+5 8<\/mn>=<\/mo>1<\/mn>\u00d7<\/mo>5<\/mn>+<\/mo>3<\/mn><\/mrow>8 = 1 \\times 5 + 3<\/annotation><\/semantics><\/math>8=1\u00d75+3 5<\/mn>=<\/mo>1<\/mn>\u00d7<\/mo>3<\/mn>+<\/mo>2<\/mn><\/mrow>5 = 1 \\times 3 + 2<\/annotation><\/semantics><\/math>5=1\u00d73+2 3<\/mn>=<\/mo>1<\/mn>\u00d7<\/mo>2<\/mn>+<\/mo>1<\/mn><\/mrow>3 = 1 \\times 2 + 1<\/annotation><\/semantics><\/math>3=1\u00d72+1 2<\/mn>=<\/mo>2<\/mn>\u00d7<\/mo>1<\/mn>+<\/mo>0<\/mn><\/mrow>2 = 2 \\times 1 + 0<\/annotation><\/semantics><\/math>2=2\u00d71+0 gcd<\/mi>\u2061<\/mo>(<\/mo>144<\/mn>,<\/mo>89<\/mn>)<\/mo>=<\/mo>1<\/mn><\/mrow>\\gcd(144, 89) = 1<\/annotation><\/semantics><\/math>gcd(144,89)=1<\/p>\n\n\n\n

    This is not a coincidence.<\/strong> 144 and 89 are consecutive Fibonacci numbers, and consecutive Fibonacci numbers are always coprime. The Euclidean algorithm applied to consecutive Fibonacci numbers produces the maximum possible number of steps \u2014 making Fibonacci pairs the “worst case” for the algorithm. This is a classical result in algorithm analysis.<\/p>\n\n\n\n

    \n\n\n\n

    Why the Euclidean Algorithm Works: The Proof<\/h2>\n\n\n\n

    Claim:<\/strong> gcd<\/mi>\u2061<\/mo>(<\/mo>a<\/mi>,<\/mo>b<\/mi>)<\/mo>=<\/mo>gcd<\/mi>\u2061<\/mo>(<\/mo>b<\/mi>,<\/mo>r<\/mi>)<\/mo><\/mrow>\\gcd(a, b) = \\gcd(b, r)<\/annotation><\/semantics><\/math>gcd(a,b)=gcd(b,r) where a<\/mi>=<\/mo>q<\/mi>b<\/mi>+<\/mo>r<\/mi><\/mrow>a = qb + r<\/annotation><\/semantics><\/math>a=qb+r.<\/p>\n\n\n\n

    Proof:<\/strong><\/p>\n\n\n\n

    Let d<\/mi>=<\/mo>gcd<\/mi>\u2061<\/mo>(<\/mo>a<\/mi>,<\/mo>b<\/mi>)<\/mo><\/mrow>d = \\gcd(a, b)<\/annotation><\/semantics><\/math>d=gcd(a,b). We show d<\/mi>=<\/mo>gcd<\/mi>\u2061<\/mo>(<\/mo>b<\/mi>,<\/mo>r<\/mi>)<\/mo><\/mrow>d = \\gcd(b, r)<\/annotation><\/semantics><\/math>d=gcd(b,r).<\/p>\n\n\n\n

    Since d<\/mi>\u2223<\/mo>a<\/mi><\/mrow>d \\mid a<\/annotation><\/semantics><\/math>d\u2223a and d<\/mi>\u2223<\/mo>b<\/mi><\/mrow>d \\mid b<\/annotation><\/semantics><\/math>d\u2223b: d<\/mi>\u2223<\/mo>(<\/mo>a<\/mi>\u2212<\/mo>q<\/mi>b<\/mi>)<\/mo>=<\/mo>r<\/mi><\/mrow>d \\mid (a – qb) = r<\/annotation><\/semantics><\/math>d\u2223(a\u2212qb)=r. So d<\/mi><\/mrow>d<\/annotation><\/semantics><\/math>d is a common divisor of b<\/mi><\/mrow>b<\/annotation><\/semantics><\/math>b and r<\/mi><\/mrow>r<\/annotation><\/semantics><\/math>r.<\/p>\n\n\n\n

    Now let e<\/mi><\/mrow>e<\/annotation><\/semantics><\/math>e be any common divisor of b<\/mi><\/mrow>b<\/annotation><\/semantics><\/math>b and r<\/mi><\/mrow>r<\/annotation><\/semantics><\/math>r. Then e<\/mi>\u2223<\/mo>q<\/mi>b<\/mi><\/mrow>e \\mid qb<\/annotation><\/semantics><\/math>e\u2223qb and e<\/mi>\u2223<\/mo>r<\/mi><\/mrow>e \\mid r<\/annotation><\/semantics><\/math>e\u2223r, so e<\/mi>\u2223<\/mo>(<\/mo>q<\/mi>b<\/mi>+<\/mo>r<\/mi>)<\/mo>=<\/mo>a<\/mi><\/mrow>e \\mid (qb + r) = a<\/annotation><\/semantics><\/math>e\u2223(qb+r)=a. Thus e<\/mi><\/mrow>e<\/annotation><\/semantics><\/math>e is a common divisor of a<\/mi><\/mrow>a<\/annotation><\/semantics><\/math>a and b<\/mi><\/mrow>b<\/annotation><\/semantics><\/math>b, so e<\/mi>\u2264<\/mo>d<\/mi><\/mrow>e \\leq d<\/annotation><\/semantics><\/math>e\u2264d.<\/p>\n\n\n\n

    Therefore d<\/mi><\/mrow>d<\/annotation><\/semantics><\/math>d is the greatest common divisor of b<\/mi><\/mrow>b<\/annotation><\/semantics><\/math>b and r<\/mi><\/mrow>r<\/annotation><\/semantics><\/math>r: gcd<\/mi>\u2061<\/mo>(<\/mo>b<\/mi>,<\/mo>r<\/mi>)<\/mo>=<\/mo>d<\/mi>=<\/mo>gcd<\/mi>\u2061<\/mo>(<\/mo>a<\/mi>,<\/mo>b<\/mi>)<\/mo><\/mrow>\\gcd(b, r) = d = \\gcd(a, b)<\/annotation><\/semantics><\/math>gcd(b,r)=d=gcd(a,b). \u25a1<\/p>\n\n\n\n

    This proof is short, elegant, and uses only the definition of divisibility \u2014 a model of mathematical reasoning that competition students should know.<\/p>\n\n\n\n

    \n\n\n\n

    The Euclidean Algorithm and the LCM<\/h2>\n\n\n\n

    The GCD and LCM (least common multiple) are related by:lcm<\/mtext>(<\/mo>a<\/mi>,<\/mo>b<\/mi>)<\/mo>=<\/mo>a<\/mi>\u22c5<\/mo>b<\/mi><\/mrow>gcd<\/mi>\u2061<\/mo>(<\/mo>a<\/mi>,<\/mo>b<\/mi>)<\/mo><\/mrow><\/mfrac><\/mrow>\\text{lcm}(a, b) = \\frac{a \\cdot b}{\\gcd(a, b)}<\/annotation><\/semantics><\/math>lcm(a,b)=gcd(a,b)a\u22c5b\u200b<\/p>\n\n\n\n

    So once the GCD is found using the Euclidean algorithm, the LCM follows immediately.<\/p>\n\n\n\n

    Example:<\/strong> lcm<\/mtext>(<\/mo>252<\/mn>,<\/mo>105<\/mn>)<\/mo>=<\/mo>252<\/mn>\u00d7<\/mo>105<\/mn><\/mrow>21<\/mn><\/mfrac>=<\/mo>26460<\/mn>21<\/mn><\/mfrac>=<\/mo>1260<\/mn><\/mrow>\\text{lcm}(252, 105) = \\frac{252 \\times 105}{21} = \\frac{26460}{21} = 1260<\/annotation><\/semantics><\/math>lcm(252,105)=21252\u00d7105\u200b=2126460\u200b=1260.<\/p>\n\n\n\n
    \n\n\n\n

    The Extended Euclidean Algorithm<\/h2>\n\n\n\n

    The extended Euclidean algorithm<\/strong> not only finds gcd<\/mi>\u2061<\/mo>(<\/mo>a<\/mi>,<\/mo>b<\/mi>)<\/mo><\/mrow>\\gcd(a, b)<\/annotation><\/semantics><\/math>gcd(a,b) but also finds integers x<\/mi><\/mrow>x<\/annotation><\/semantics><\/math>x and y<\/mi><\/mrow>y<\/annotation><\/semantics><\/math>y such that:a<\/mi>x<\/mi>+<\/mo>b<\/mi>y<\/mi>=<\/mo>gcd<\/mi>\u2061<\/mo>(<\/mo>a<\/mi>,<\/mo>b<\/mi>)<\/mo><\/mrow>ax + by = \\gcd(a, b)<\/annotation><\/semantics><\/math>ax+by=gcd(a,b)<\/p>\n\n\n\n

    This is called a B\u00e9zout identity<\/strong> (or B\u00e9zout’s lemma<\/strong>), and it states that the GCD of two integers can always be expressed as an integer linear combination of those integers.<\/p>\n\n\n\n

    Method: Back-substitution<\/strong><\/p>\n\n\n\n

    Working backwards through the Euclidean algorithm steps, express each remainder as a linear combination of a<\/mi><\/mrow>a<\/annotation><\/semantics><\/math>a and b<\/mi><\/mrow>b<\/annotation><\/semantics><\/math>b.<\/p>\n\n\n\n

    Example:<\/strong> Find x<\/mi><\/mrow>x<\/annotation><\/semantics><\/math>x, y<\/mi><\/mrow>y<\/annotation><\/semantics><\/math>y such that 252<\/mn>x<\/mi>+<\/mo>105<\/mn>y<\/mi>=<\/mo>21<\/mn>=<\/mo>gcd<\/mi>\u2061<\/mo>(<\/mo>252<\/mn>,<\/mo>105<\/mn>)<\/mo><\/mrow>252x + 105y = 21 = \\gcd(252, 105)<\/annotation><\/semantics><\/math>252x+105y=21=gcd(252,105).<\/p>\n\n\n\n

    From the Euclidean algorithm steps:42<\/mn>=<\/mo>252<\/mn>\u2212<\/mo>2<\/mn>\u00d7<\/mo>105<\/mn><\/mspace>\u22ef<\/mo>(<\/mo>1<\/mn>)<\/mo><\/mrow>42 = 252 – 2 \\times 105 \\quad \\cdots (1)<\/annotation><\/semantics><\/math>42=252\u22122\u00d7105\u22ef(1) 21<\/mn>=<\/mo>105<\/mn>\u2212<\/mo>2<\/mn>\u00d7<\/mo>42<\/mn><\/mspace>\u22ef<\/mo>(<\/mo>2<\/mn>)<\/mo><\/mrow>21 = 105 – 2 \\times 42 \\quad \\cdots (2)<\/annotation><\/semantics><\/math>21=105\u22122\u00d742\u22ef(2)<\/p>\n\n\n\n

    Substitute (1) into (2):21<\/mn>=<\/mo>105<\/mn>\u2212<\/mo>2<\/mn>(<\/mo>252<\/mn>\u2212<\/mo>2<\/mn>\u00d7<\/mo>105<\/mn>)<\/mo>=<\/mo>105<\/mn>\u2212<\/mo>2<\/mn>\u00d7<\/mo>252<\/mn>+<\/mo>4<\/mn>\u00d7<\/mo>105<\/mn>=<\/mo>5<\/mn>\u00d7<\/mo>105<\/mn>\u2212<\/mo>2<\/mn>\u00d7<\/mo>252<\/mn><\/mrow>21 = 105 – 2(252 – 2 \\times 105) = 105 – 2 \\times 252 + 4 \\times 105 = 5 \\times 105 – 2 \\times 252<\/annotation><\/semantics><\/math>21=105\u22122(252\u22122\u00d7105)=105\u22122\u00d7252+4\u00d7105=5\u00d7105\u22122\u00d7252<\/p>\n\n\n\n

    So: 252<\/mn>\u00d7<\/mo>(<\/mo>\u2212<\/mo>2<\/mn>)<\/mo>+<\/mo>105<\/mn>\u00d7<\/mo>5<\/mn>=<\/mo>21<\/mn><\/mrow>252 \\times (-2) + 105 \\times 5 = 21<\/annotation><\/semantics><\/math>252\u00d7(\u22122)+105\u00d75=21.<\/p>\n\n\n\n

    x=\u22122x = -2 x=\u22122, y=5y = 5 y=5.<\/strong><\/p>\n\n\n\n

    Check:<\/strong> 252<\/mn>\u00d7<\/mo>(<\/mo>\u2212<\/mo>2<\/mn>)<\/mo>+<\/mo>105<\/mn>\u00d7<\/mo>5<\/mn>=<\/mo>\u2212<\/mo>504<\/mn>+<\/mo>525<\/mn>=<\/mo>21<\/mn><\/mrow>252 \\times (-2) + 105 \\times 5 = -504 + 525 = 21<\/annotation><\/semantics><\/math>252\u00d7(\u22122)+105\u00d75=\u2212504+525=21 \u2713<\/p>\n\n\n\n
    \n\n\n\n

    Applications of the Extended Euclidean Algorithm<\/h2>\n\n\n\n

    1. Solving Linear Diophantine Equations<\/h3>\n\n\n\n

    A linear Diophantine equation<\/strong> is an equation of the form a<\/mi>x<\/mi>+<\/mo>b<\/mi>y<\/mi>=<\/mo>c<\/mi><\/mrow>ax + by = c<\/annotation><\/semantics><\/math>ax+by=c where a<\/mi><\/mrow>a<\/annotation><\/semantics><\/math>a, b<\/mi><\/mrow>b<\/annotation><\/semantics><\/math>b, c<\/mi><\/mrow>c<\/annotation><\/semantics><\/math>c are integers and we seek integer solutions x<\/mi><\/mrow>x<\/annotation><\/semantics><\/math>x, y<\/mi><\/mrow>y<\/annotation><\/semantics><\/math>y.<\/p>\n\n\n\n

    Theorem (B\u00e9zout):<\/strong> a<\/mi>x<\/mi>+<\/mo>b<\/mi>y<\/mi>=<\/mo>c<\/mi><\/mrow>ax + by = c<\/annotation><\/semantics><\/math>ax+by=c has integer solutions if and only if gcd<\/mi>\u2061<\/mo>(<\/mo>a<\/mi>,<\/mo>b<\/mi>)<\/mo>\u2223<\/mo>c<\/mi><\/mrow>\\gcd(a, b) \\mid c<\/annotation><\/semantics><\/math>gcd(a,b)\u2223c.<\/p>\n\n\n\n

    Method:<\/strong><\/p>\n\n\n\n

      \n
    1. Find gcd<\/mi>\u2061<\/mo>(<\/mo>a<\/mi>,<\/mo>b<\/mi>)<\/mo><\/mrow>\\gcd(a, b)<\/annotation><\/semantics><\/math>gcd(a,b) using the Euclidean algorithm.<\/li>\n\n\n\n
    2. Check if gcd<\/mi>\u2061<\/mo>(<\/mo>a<\/mi>,<\/mo>b<\/mi>)<\/mo>\u2223<\/mo>c<\/mi><\/mrow>\\gcd(a, b) \\mid c<\/annotation><\/semantics><\/math>gcd(a,b)\u2223c. If not: no solution.<\/li>\n\n\n\n
    3. Use back-substitution to find a particular solution (<\/mo>x<\/mi>0<\/mn><\/msub>,<\/mo>y<\/mi>0<\/mn><\/msub>)<\/mo><\/mrow>(x_0, y_0)<\/annotation><\/semantics><\/math>(x0\u200b,y0\u200b) to a<\/mi>x<\/mi>+<\/mo>b<\/mi>y<\/mi>=<\/mo>gcd<\/mi>\u2061<\/mo>(<\/mo>a<\/mi>,<\/mo>b<\/mi>)<\/mo><\/mrow>ax + by = \\gcd(a,b)<\/annotation><\/semantics><\/math>ax+by=gcd(a,b).<\/li>\n\n\n\n
    4. Scale: multiply by c<\/mi>\/<\/mi>gcd<\/mi>\u2061<\/mo>(<\/mo>a<\/mi>,<\/mo>b<\/mi>)<\/mo><\/mrow>c \/ \\gcd(a,b)<\/annotation><\/semantics><\/math>c\/gcd(a,b) to get a solution to a<\/mi>x<\/mi>+<\/mo>b<\/mi>y<\/mi>=<\/mo>c<\/mi><\/mrow>ax + by = c<\/annotation><\/semantics><\/math>ax+by=c.<\/li>\n\n\n\n
    5. The general solution is: x<\/mi>=<\/mo>x<\/mi>0<\/mn><\/msub>\u22c5<\/mo>c<\/mi>d<\/mi><\/mfrac>+<\/mo>b<\/mi>d<\/mi><\/mfrac>t<\/mi><\/mrow>x = x_0 \\cdot \\frac{c}{d} + \\frac{b}{d}t<\/annotation><\/semantics><\/math>x=x0\u200b\u22c5dc\u200b+db\u200bt, y<\/mi>=<\/mo>y<\/mi>0<\/mn><\/msub>\u22c5<\/mo>c<\/mi>d<\/mi><\/mfrac>\u2212<\/mo>a<\/mi>d<\/mi><\/mfrac>t<\/mi><\/mrow>y = y_0 \\cdot \\frac{c}{d} – \\frac{a}{d}t<\/annotation><\/semantics><\/math>y=y0\u200b\u22c5dc\u200b\u2212da\u200bt for any integer t<\/mi><\/mrow>t<\/annotation><\/semantics><\/math>t, where d<\/mi>=<\/mo>gcd<\/mi>\u2061<\/mo>(<\/mo>a<\/mi>,<\/mo>b<\/mi>)<\/mo><\/mrow>d = \\gcd(a,b)<\/annotation><\/semantics><\/math>d=gcd(a,b).<\/li>\n<\/ol>\n\n\n\n

      Example:<\/strong> Solve 252<\/mn>x<\/mi>+<\/mo>105<\/mn>y<\/mi>=<\/mo>63<\/mn><\/mrow>252x + 105y = 63<\/annotation><\/semantics><\/math>252x+105y=63.<\/p>\n\n\n\n

      gcd<\/mi>\u2061<\/mo>(<\/mo>252<\/mn>,<\/mo>105<\/mn>)<\/mo>=<\/mo>21<\/mn><\/mrow>\\gcd(252, 105) = 21<\/annotation><\/semantics><\/math>gcd(252,105)=21 and 21<\/mn>\u2223<\/mo>63<\/mn><\/mrow>21 \\mid 63<\/annotation><\/semantics><\/math>21\u222363 \u2713.<\/p>\n\n\n\n

      From above: 252<\/mn>(<\/mo>\u2212<\/mo>2<\/mn>)<\/mo>+<\/mo>105<\/mn>(<\/mo>5<\/mn>)<\/mo>=<\/mo>21<\/mn><\/mrow>252(-2) + 105(5) = 21<\/annotation><\/semantics><\/math>252(\u22122)+105(5)=21. Multiply by 63<\/mn>\/<\/mi>21<\/mn>=<\/mo>3<\/mn><\/mrow>63\/21 = 3<\/annotation><\/semantics><\/math>63\/21=3:<\/p>\n\n\n\n

      252<\/mn>(<\/mo>\u2212<\/mo>6<\/mn>)<\/mo>+<\/mo>105<\/mn>(<\/mo>15<\/mn>)<\/mo>=<\/mo>63<\/mn><\/mrow>252(-6) + 105(15) = 63<\/annotation><\/semantics><\/math>252(\u22126)+105(15)=63.<\/p>\n\n\n\n

      Particular solution: (<\/mo>x<\/mi>0<\/mn><\/msub>,<\/mo>y<\/mi>0<\/mn><\/msub>)<\/mo>=<\/mo>(<\/mo>\u2212<\/mo>6<\/mn>,<\/mo>15<\/mn>)<\/mo><\/mrow>(x_0, y_0) = (-6, 15)<\/annotation><\/semantics><\/math>(x0\u200b,y0\u200b)=(\u22126,15).<\/p>\n\n\n\n

      General solution: x<\/mi>=<\/mo>\u2212<\/mo>6<\/mn>+<\/mo>5<\/mn>t<\/mi><\/mrow>x = -6 + 5t<\/annotation><\/semantics><\/math>x=\u22126+5t, y<\/mi>=<\/mo>15<\/mn>\u2212<\/mo>12<\/mn>t<\/mi><\/mrow>y = 15 – 12t<\/annotation><\/semantics><\/math>y=15\u221212t for any integer t<\/mi><\/mrow>t<\/annotation><\/semantics><\/math>t.<\/p>\n\n\n\n

      Check with t=1t=1 t=1:<\/strong> 252<\/mn>(<\/mo>\u2212<\/mo>1<\/mn>)<\/mo>+<\/mo>105<\/mn>(<\/mo>3<\/mn>)<\/mo>=<\/mo>\u2212<\/mo>252<\/mn>+<\/mo>315<\/mn>=<\/mo>63<\/mn><\/mrow>252(-1) + 105(3) = -252 + 315 = 63<\/annotation><\/semantics><\/math>252(\u22121)+105(3)=\u2212252+315=63 \u2713<\/p>\n\n\n\n

      2. Modular Inverses<\/h3>\n\n\n\n

      If gcd<\/mi>\u2061<\/mo>(<\/mo>a<\/mi>,<\/mo>m<\/mi>)<\/mo>=<\/mo>1<\/mn><\/mrow>\\gcd(a, m) = 1<\/annotation><\/semantics><\/math>gcd(a,m)=1, the extended Euclidean algorithm finds the modular inverse<\/strong> of a<\/mi><\/mrow>a<\/annotation><\/semantics><\/math>a modulo m<\/mi><\/mrow>m<\/annotation><\/semantics><\/math>m \u2014 the integer x<\/mi><\/mrow>x<\/annotation><\/semantics><\/math>x such that a<\/mi>x<\/mi>\u2261<\/mo>1<\/mn><\/mspace><\/mspace>(<\/mo>m<\/mi>o<\/mi>d<\/mi><\/mrow><\/mspace>m<\/mi>)<\/mo><\/mrow>ax \\equiv 1 \\pmod{m}<\/annotation><\/semantics><\/math>ax\u22611(modm).<\/p>\n\n\n\n

      From a<\/mi>x<\/mi>+<\/mo>m<\/mi>y<\/mi>=<\/mo>1<\/mn><\/mrow>ax + my = 1<\/annotation><\/semantics><\/math>ax+my=1 (B\u00e9zout, since gcd<\/mi>\u2061<\/mo>(<\/mo>a<\/mi>,<\/mo>m<\/mi>)<\/mo>=<\/mo>1<\/mn><\/mrow>\\gcd(a,m) = 1<\/annotation><\/semantics><\/math>gcd(a,m)=1): a<\/mi>x<\/mi>\u2261<\/mo>1<\/mn><\/mspace><\/mspace>(<\/mo>m<\/mi>o<\/mi>d<\/mi><\/mrow><\/mspace>m<\/mi>)<\/mo><\/mrow>ax \\equiv 1 \\pmod{m}<\/annotation><\/semantics><\/math>ax\u22611(modm).<\/p>\n\n\n\n

      This is foundational to RSA cryptography and appears in competition number theory problems.<\/p>\n\n\n\n

      Example:<\/strong> Find the inverse of 7 modulo 11.<\/p>\n\n\n\n

      gcd<\/mi>\u2061<\/mo>(<\/mo>7<\/mn>,<\/mo>11<\/mn>)<\/mo>=<\/mo>1<\/mn><\/mrow>\\gcd(7, 11) = 1<\/annotation><\/semantics><\/math>gcd(7,11)=1. Apply extended Euclidean algorithm:<\/p>\n\n\n\n

      11<\/mn>=<\/mo>1<\/mn>\u00d7<\/mo>7<\/mn>+<\/mo>4<\/mn><\/mrow>11 = 1 \\times 7 + 4<\/annotation><\/semantics><\/math>11=1\u00d77+4 7<\/mn>=<\/mo>1<\/mn>\u00d7<\/mo>4<\/mn>+<\/mo>3<\/mn><\/mrow>7 = 1 \\times 4 + 3<\/annotation><\/semantics><\/math>7=1\u00d74+3 4<\/mn>=<\/mo>1<\/mn>\u00d7<\/mo>3<\/mn>+<\/mo>1<\/mn><\/mrow>4 = 1 \\times 3 + 1<\/annotation><\/semantics><\/math>4=1\u00d73+1 3<\/mn>=<\/mo>3<\/mn>\u00d7<\/mo>1<\/mn>+<\/mo>0<\/mn><\/mrow>3 = 3 \\times 1 + 0<\/annotation><\/semantics><\/math>3=3\u00d71+0<\/p>\n\n\n\n

      Back-substitution: 1<\/mn>=<\/mo>4<\/mn>\u2212<\/mo>1<\/mn>\u00d7<\/mo>3<\/mn>=<\/mo>4<\/mn>\u2212<\/mo>(<\/mo>7<\/mn>\u2212<\/mo>4<\/mn>)<\/mo>=<\/mo>2<\/mn>\u00d7<\/mo>4<\/mn>\u2212<\/mo>7<\/mn>=<\/mo>2<\/mn>(<\/mo>11<\/mn>\u2212<\/mo>7<\/mn>)<\/mo>\u2212<\/mo>7<\/mn>=<\/mo>2<\/mn>\u00d7<\/mo>11<\/mn>\u2212<\/mo>3<\/mn>\u00d7<\/mo>7<\/mn><\/mrow>1 = 4 – 1 \\times 3 = 4 – (7 – 4) = 2 \\times 4 – 7 = 2(11 – 7) – 7 = 2 \\times 11 – 3 \\times 7<\/annotation><\/semantics><\/math>1=4\u22121\u00d73=4\u2212(7\u22124)=2\u00d74\u22127=2(11\u22127)\u22127=2\u00d711\u22123\u00d77<\/p>\n\n\n\n

      So 7<\/mn>\u00d7<\/mo>(<\/mo>\u2212<\/mo>3<\/mn>)<\/mo>+<\/mo>11<\/mn>\u00d7<\/mo>2<\/mn>=<\/mo>1<\/mn><\/mrow>7 \\times (-3) + 11 \\times 2 = 1<\/annotation><\/semantics><\/math>7\u00d7(\u22123)+11\u00d72=1, meaning 7<\/mn>\u00d7<\/mo>(<\/mo>\u2212<\/mo>3<\/mn>)<\/mo>\u2261<\/mo>1<\/mn><\/mspace><\/mspace>(<\/mo>m<\/mi>o<\/mi>d<\/mi><\/mrow><\/mspace>11<\/mn>)<\/mo><\/mrow>7 \\times (-3) \\equiv 1 \\pmod{11}<\/annotation><\/semantics><\/math>7\u00d7(\u22123)\u22611(mod11).<\/p>\n\n\n\n

      \u2212<\/mo>3<\/mn>\u2261<\/mo>8<\/mn><\/mspace><\/mspace>(<\/mo>m<\/mi>o<\/mi>d<\/mi><\/mrow><\/mspace>11<\/mn>)<\/mo><\/mrow>-3 \\equiv 8 \\pmod{11}<\/annotation><\/semantics><\/math>\u22123\u22618(mod11).<\/p>\n\n\n\n

      Modular inverse of 7 mod 11 is 8.<\/strong> Check: 7<\/mn>\u00d7<\/mo>8<\/mn>=<\/mo>56<\/mn>=<\/mo>5<\/mn>\u00d7<\/mo>11<\/mn>+<\/mo>1<\/mn>\u2261<\/mo>1<\/mn><\/mspace><\/mspace>(<\/mo>m<\/mi>o<\/mi>d<\/mi><\/mrow><\/mspace>11<\/mn>)<\/mo><\/mrow>7 \\times 8 = 56 = 5 \\times 11 + 1 \\equiv 1 \\pmod{11}<\/annotation><\/semantics><\/math>7\u00d78=56=5\u00d711+1\u22611(mod11) \u2713<\/p>\n\n\n\n
      \n\n\n\n

      The Euclidean Algorithm in the Ontario Curriculum<\/h2>\n\n\n\n

      The Euclidean algorithm is not part of the standard Ontario K\u201312 curriculum, but GCD and LCM are:<\/p>\n\n\n\n

      Grade 8 (Ontario):<\/strong> Students find the GCD and LCM of pairs of numbers using factor lists or prime factorisation. The Euclidean algorithm provides a faster method for large numbers and is worth knowing as a supplement to the curriculum approach. See our Grade 8 math curriculum Ontario guide<\/a>.<\/p>\n\n\n\n

      Grade 9 MTH1W (Ontario):<\/strong> Number theory concepts including GCD appear in the curriculum. See our Ontario Grade 9 math curriculum guide<\/a>.<\/p>\n\n\n\n

      Math 30-1 (Alberta):<\/strong> Divisibility and integer properties underpin the polynomial content. See our Math 30-1 complete guide<\/a>.<\/p>\n\n\n\n

      \n\n\n\n

      Where the Euclidean Algorithm Appears in Competitions<\/h2>\n\n\n\n

      AMC 8 and Gauss Contest (Grades 7\u20138)<\/h3>\n\n\n\n

      GCD and LCM problems appear regularly in both contests \u2014 typically using factor lists or prime factorisation rather than the Euclidean algorithm directly. Knowing the algorithm gives a faster method for large numbers. See our AMC 8 guide<\/a> and Gauss math contest guide<\/a>.<\/p>\n\n\n\n

      AMC 10 and Cayley\/Fermat Contests (Grades 9\u201311)<\/h3>\n\n\n\n

      Number theory problems at this level include GCD and coprimality. The extended Euclidean algorithm enables solving linear Diophantine equations that appear as multi-step problems. Recognising when a problem reduces to a<\/mi>x<\/mi>+<\/mo>b<\/mi>y<\/mi>=<\/mo>c<\/mi><\/mrow>ax + by = c<\/annotation><\/semantics><\/math>ax+by=c and applying B\u00e9zout’s lemma is a standard technique.<\/p>\n\n\n\n

      Euclid Contest (CEMC, Grade 12)<\/h3>\n\n\n\n

      The Euclidean algorithm and its extensions appear in Euclid Part B and Part C number theory problems. Modular inverses (found via the extended algorithm) underpin certain problems involving fractions modulo a prime. See our Euclid math contest guide<\/a>.<\/p>\n\n\n\n

      COMC and CMO<\/h3>\n\n\n\n

      Linear Diophantine equations, B\u00e9zout’s identity, and modular inverses \u2014 all rooted in the extended Euclidean algorithm \u2014 are standard tools in COMC Part C and CMO number theory. See our COMC math contest guide<\/a> and Canadian Mathematical Olympiad guide<\/a>.<\/p>\n\n\n\n

      \n\n\n\n
      \"\"<\/a><\/figure>\n\n\n\n
      \n\n\n\n

      Common Mistakes with the Euclidean Algorithm<\/h2>\n\n\n\n

      Mistake 1: Using the wrong pair after each step.<\/strong>After computing a<\/mi>=<\/mo>q<\/mi>b<\/mi>+<\/mo>r<\/mi><\/mrow>a = qb + r<\/annotation><\/semantics><\/math>a=qb+r, the next step uses (<\/mo>b<\/mi>,<\/mo>r<\/mi>)<\/mo><\/mrow>(b, r)<\/annotation><\/semantics><\/math>(b,r) \u2014 not (<\/mo>a<\/mi>,<\/mo>r<\/mi>)<\/mo><\/mrow>(a, r)<\/annotation><\/semantics><\/math>(a,r) or (<\/mo>q<\/mi>,<\/mo>r<\/mi>)<\/mo><\/mrow>(q, r)<\/annotation><\/semantics><\/math>(q,r). The larger number is replaced by the smaller, and the smaller by the remainder.<\/p>\n\n\n\n

      Mistake 2: Stopping too early.<\/strong> The algorithm stops when the remainder is 0, and the GCD is the previous (non-zero) remainder \u2014 not the quotient of the final step.<\/p>\n\n\n\n

      Mistake 3: Back-substitution direction errors in the extended algorithm.<\/strong> In back-substitution, it is easy to substitute in the wrong direction or to make a sign error. Write each remainder explicitly as a linear combination at every step, checking the arithmetic before proceeding.<\/p>\n\n\n\n

      Mistake 4: Assuming ax+by=cax + by = c ax+by=c always has solutions.<\/strong>It has solutions if and only if gcd<\/mi>\u2061<\/mo>(<\/mo>a<\/mi>,<\/mo>b<\/mi>)<\/mo>\u2223<\/mo>c<\/mi><\/mrow>\\gcd(a, b) \\mid c<\/annotation><\/semantics><\/math>gcd(a,b)\u2223c. If gcd<\/mi>\u2061<\/mo>(<\/mo>a<\/mi>,<\/mo>b<\/mi>)<\/mo>\u2224<\/mo>c<\/mi><\/mrow>\\gcd(a, b) \\nmid c<\/annotation><\/semantics><\/math>gcd(a,b)\u2224c, no integer solution exists. Check divisibility before attempting to solve.<\/p>\n\n\n\n

      Mistake 5: Giving only one solution to a Diophantine equation.<\/strong>Linear Diophantine equations with solutions have infinitely many. The general solution involves a parameter t<\/mi><\/mrow>t<\/annotation><\/semantics><\/math>t. Competition problems sometimes ask for specific solution types (positive integers, smallest positive solution) \u2014 find the general solution first, then filter.<\/p>\n\n\n\n
      \n\n\n\n

      Practice Problems<\/h2>\n\n\n\n

      Set A \u2014 Euclidean algorithm<\/strong><\/p>\n\n\n\n

      Find each GCD using the Euclidean algorithm (show all steps):<\/p>\n\n\n\n

        \n
      1. gcd<\/mi>\u2061<\/mo>(<\/mo>48<\/mn>,<\/mo>18<\/mn>)<\/mo><\/mrow>\\gcd(48, 18)<\/annotation><\/semantics><\/math>gcd(48,18)<\/li>\n\n\n\n
      2. gcd<\/mi>\u2061<\/mo>(<\/mo>210<\/mn>,<\/mo>45<\/mn>)<\/mo><\/mrow>\\gcd(210, 45)<\/annotation><\/semantics><\/math>gcd(210,45)<\/li>\n\n\n\n
      3. gcd<\/mi>\u2061<\/mo>(<\/mo>1000<\/mn>,<\/mo>256<\/mn>)<\/mo><\/mrow>\\gcd(1000, 256)<\/annotation><\/semantics><\/math>gcd(1000,256)<\/li>\n\n\n\n
      4. gcd<\/mi>\u2061<\/mo>(<\/mo>144<\/mn>,<\/mo>55<\/mn>)<\/mo><\/mrow>\\gcd(144, 55)<\/annotation><\/semantics><\/math>gcd(144,55)<\/li>\n\n\n\n
      5. gcd<\/mi>\u2061<\/mo>(<\/mo>999<\/mn>,<\/mo>111<\/mn>)<\/mo><\/mrow>\\gcd(999, 111)<\/annotation><\/semantics><\/math>gcd(999,111)<\/li>\n<\/ol>\n\n\n\n

        Set B \u2014 LCM<\/strong><\/p>\n\n\n\n

          \n
        1. Find lcm<\/mtext>(<\/mo>48<\/mn>,<\/mo>18<\/mn>)<\/mo><\/mrow>\\text{lcm}(48, 18)<\/annotation><\/semantics><\/math>lcm(48,18)<\/li>\n\n\n\n
        2. Find lcm<\/mtext>(<\/mo>210<\/mn>,<\/mo>45<\/mn>)<\/mo><\/mrow>\\text{lcm}(210, 45)<\/annotation><\/semantics><\/math>lcm(210,45)<\/li>\n\n\n\n
        3. The GCD of two numbers is 12 and their LCM is 360. One number is 36. Find the other.<\/li>\n<\/ol>\n\n\n\n

          Set C \u2014 Extended algorithm and Diophantine equations<\/strong><\/p>\n\n\n\n

            \n
          1. Find integers x<\/mi><\/mrow>x<\/annotation><\/semantics><\/math>x, y<\/mi><\/mrow>y<\/annotation><\/semantics><\/math>y such that 48<\/mn>x<\/mi>+<\/mo>18<\/mn>y<\/mi>=<\/mo>gcd<\/mi>\u2061<\/mo>(<\/mo>48<\/mn>,<\/mo>18<\/mn>)<\/mo><\/mrow>48x + 18y = \\gcd(48, 18)<\/annotation><\/semantics><\/math>48x+18y=gcd(48,18).<\/li>\n\n\n\n
          2. Does 210<\/mn>x<\/mi>+<\/mo>45<\/mn>y<\/mi>=<\/mo>15<\/mn><\/mrow>210x + 45y = 15<\/annotation><\/semantics><\/math>210x+45y=15 have integer solutions? If so, find the general solution.<\/li>\n\n\n\n
          3. Find the modular inverse of 5 modulo 13.<\/li>\n\n\n\n
          4. Find all positive integer solutions to 17<\/mn>x<\/mi>+<\/mo>11<\/mn>y<\/mi>=<\/mo>100<\/mn><\/mrow>17x + 11y = 100<\/annotation><\/semantics><\/math>17x+11y=100.<\/li>\n<\/ol>\n\n\n\n
            \n\n\n\n

            Answers:<\/strong><\/p>\n\n\n\n

            Set A:<\/p>\n\n\n\n

              \n
            1. 48<\/mn>=<\/mo>2<\/mn>\u00d7<\/mo>18<\/mn>+<\/mo>12<\/mn><\/mrow>48 = 2\\times18+12<\/annotation><\/semantics><\/math>48=2\u00d718+12; 18<\/mn>=<\/mo>1<\/mn>\u00d7<\/mo>12<\/mn>+<\/mo>6<\/mn><\/mrow>18=1\\times12+6<\/annotation><\/semantics><\/math>18=1\u00d712+6; 12<\/mn>=<\/mo>2<\/mn>\u00d7<\/mo>6<\/mn>+<\/mo>0<\/mn><\/mrow>12=2\\times6+0<\/annotation><\/semantics><\/math>12=2\u00d76+0. gcd\u2061(48,18)=6\\gcd(48,18) = 6 gcd(48,18)=6<\/strong><\/li>\n\n\n\n
            2. 210<\/mn>=<\/mo>4<\/mn>\u00d7<\/mo>45<\/mn>+<\/mo>30<\/mn><\/mrow>210=4\\times45+30<\/annotation><\/semantics><\/math>210=4\u00d745+30; 45<\/mn>=<\/mo>1<\/mn>\u00d7<\/mo>30<\/mn>+<\/mo>15<\/mn><\/mrow>45=1\\times30+15<\/annotation><\/semantics><\/math>45=1\u00d730+15; 30<\/mn>=<\/mo>2<\/mn>\u00d7<\/mo>15<\/mn>+<\/mo>0<\/mn><\/mrow>30=2\\times15+0<\/annotation><\/semantics><\/math>30=2\u00d715+0. gcd\u2061(210,45)=15\\gcd(210,45) = 15 gcd(210,45)=15<\/strong><\/li>\n\n\n\n
            3. 1000<\/mn>=<\/mo>3<\/mn>\u00d7<\/mo>256<\/mn>+<\/mo>232<\/mn><\/mrow>1000=3\\times256+232<\/annotation><\/semantics><\/math>1000=3\u00d7256+232; 256<\/mn>=<\/mo>1<\/mn>\u00d7<\/mo>232<\/mn>+<\/mo>24<\/mn><\/mrow>256=1\\times232+24<\/annotation><\/semantics><\/math>256=1\u00d7232+24; 232<\/mn>=<\/mo>9<\/mn>\u00d7<\/mo>24<\/mn>+<\/mo>16<\/mn><\/mrow>232=9\\times24+16<\/annotation><\/semantics><\/math>232=9\u00d724+16; 24<\/mn>=<\/mo>1<\/mn>\u00d7<\/mo>16<\/mn>+<\/mo>8<\/mn><\/mrow>24=1\\times16+8<\/annotation><\/semantics><\/math>24=1\u00d716+8; 16<\/mn>=<\/mo>2<\/mn>\u00d7<\/mo>8<\/mn>+<\/mo>0<\/mn><\/mrow>16=2\\times8+0<\/annotation><\/semantics><\/math>16=2\u00d78+0. gcd\u2061(1000,256)=8\\gcd(1000,256) = 8 gcd(1000,256)=8<\/strong><\/li>\n\n\n\n
            4. 144<\/mn>=<\/mo>2<\/mn>\u00d7<\/mo>55<\/mn>+<\/mo>34<\/mn><\/mrow>144=2\\times55+34<\/annotation><\/semantics><\/math>144=2\u00d755+34; 55<\/mn>=<\/mo>1<\/mn>\u00d7<\/mo>34<\/mn>+<\/mo>21<\/mn><\/mrow>55=1\\times34+21<\/annotation><\/semantics><\/math>55=1\u00d734+21; 34<\/mn>=<\/mo>1<\/mn>\u00d7<\/mo>21<\/mn>+<\/mo>13<\/mn><\/mrow>34=1\\times21+13<\/annotation><\/semantics><\/math>34=1\u00d721+13; 21<\/mn>=<\/mo>1<\/mn>\u00d7<\/mo>13<\/mn>+<\/mo>8<\/mn><\/mrow>21=1\\times13+8<\/annotation><\/semantics><\/math>21=1\u00d713+8; 13<\/mn>=<\/mo>1<\/mn>\u00d7<\/mo>8<\/mn>+<\/mo>5<\/mn><\/mrow>13=1\\times8+5<\/annotation><\/semantics><\/math>13=1\u00d78+5; 8<\/mn>=<\/mo>1<\/mn>\u00d7<\/mo>5<\/mn>+<\/mo>3<\/mn><\/mrow>8=1\\times5+3<\/annotation><\/semantics><\/math>8=1\u00d75+3; 5<\/mn>=<\/mo>1<\/mn>\u00d7<\/mo>3<\/mn>+<\/mo>2<\/mn><\/mrow>5=1\\times3+2<\/annotation><\/semantics><\/math>5=1\u00d73+2; 3<\/mn>=<\/mo>1<\/mn>\u00d7<\/mo>2<\/mn>+<\/mo>1<\/mn><\/mrow>3=1\\times2+1<\/annotation><\/semantics><\/math>3=1\u00d72+1; 2<\/mn>=<\/mo>2<\/mn>\u00d7<\/mo>1<\/mn>+<\/mo>0<\/mn><\/mrow>2=2\\times1+0<\/annotation><\/semantics><\/math>2=2\u00d71+0. gcd\u2061(144,55)=1\\gcd(144,55) = 1 gcd(144,55)=1<\/strong> (consecutive Fibonacci-adjacent numbers)<\/li>\n\n\n\n
            5. 999<\/mn>=<\/mo>9<\/mn>\u00d7<\/mo>111<\/mn>+<\/mo>0<\/mn><\/mrow>999=9\\times111+0<\/annotation><\/semantics><\/math>999=9\u00d7111+0. gcd\u2061(999,111)=111\\gcd(999,111) = 111 gcd(999,111)=111<\/strong><\/li>\n<\/ol>\n\n\n\n

              Set B: 6. $\\text{lcm}(48,18) = 48\\times18\/6 = 864\/6 = $ 144<\/strong> 7. $\\text{lcm}(210,45) = 210\\times45\/15 = 9450\/15 = $ 630<\/strong>8. a<\/mi>\u00d7<\/mo>b<\/mi>=<\/mo>gcd<\/mi>\u2061<\/mo>\u00d7<\/mo>lcm<\/mtext><\/mrow>a \\times b = \\gcd \\times \\text{lcm}<\/annotation><\/semantics><\/math>a\u00d7b=gcd\u00d7lcm: 36<\/mn>\u00d7<\/mo>b<\/mi>=<\/mo>12<\/mn>\u00d7<\/mo>360<\/mn>=<\/mo>4320<\/mn><\/mrow>36 \\times b = 12 \\times 360 = 4320<\/annotation><\/semantics><\/math>36\u00d7b=12\u00d7360=4320; $b = $ 120<\/strong><\/p>\n\n\n\n

              Set C: 9. From steps: 6<\/mn>=<\/mo>18<\/mn>\u2212<\/mo>1<\/mn>\u00d7<\/mo>12<\/mn>=<\/mo>18<\/mn>\u2212<\/mo>(<\/mo>48<\/mn>\u2212<\/mo>2<\/mn>\u00d7<\/mo>18<\/mn>)<\/mo>=<\/mo>3<\/mn>\u00d7<\/mo>18<\/mn>\u2212<\/mo>1<\/mn>\u00d7<\/mo>48<\/mn><\/mrow>6 = 18-1\\times12 = 18-(48-2\\times18) = 3\\times18-1\\times48<\/annotation><\/semantics><\/math>6=18\u22121\u00d712=18\u2212(48\u22122\u00d718)=3\u00d718\u22121\u00d748. So 48<\/mn>\u00d7<\/mo>(<\/mo>\u2212<\/mo>1<\/mn>)<\/mo>+<\/mo>18<\/mn>\u00d7<\/mo>3<\/mn>=<\/mo>6<\/mn><\/mrow>48\\times(-1)+18\\times3=6<\/annotation><\/semantics><\/math>48\u00d7(\u22121)+18\u00d73=6. x=\u22121,y=3x=-1, y=3 x=\u22121,y=3<\/strong>10. gcd<\/mi>\u2061<\/mo>(<\/mo>210<\/mn>,<\/mo>45<\/mn>)<\/mo>=<\/mo>15<\/mn><\/mrow>\\gcd(210,45)=15<\/annotation><\/semantics><\/math>gcd(210,45)=15 and 15<\/mn>\u2223<\/mo>15<\/mn><\/mrow>15\\mid15<\/annotation><\/semantics><\/math>15\u222315 \u2713. From above: 210<\/mn>\u00d7<\/mo>(<\/mo>\u2212<\/mo>1<\/mn>)<\/mo>+<\/mo>45<\/mn>\u00d7<\/mo>(<\/mo>?<\/mo>)<\/mo><\/mrow>210\\times(-1)+45\\times(?)<\/annotation><\/semantics><\/math>210\u00d7(\u22121)+45\u00d7(?)… find particular solution then general. 210<\/mn>\u00d7<\/mo>(<\/mo>\u2212<\/mo>2<\/mn>)<\/mo>+<\/mo>45<\/mn>\u00d7<\/mo>(<\/mo>9<\/mn>+<\/mo>?<\/mo>)<\/mo><\/mrow>210\\times(-2)+45\\times(9+?)<\/annotation><\/semantics><\/math>210\u00d7(\u22122)+45\u00d7(9+?)… Actually: divide through: 14<\/mn>x<\/mi>+<\/mo>3<\/mn>y<\/mi>=<\/mo>1<\/mn><\/mrow>14x+3y=1<\/annotation><\/semantics><\/math>14x+3y=1. Back-sub: gcd<\/mi>\u2061<\/mo>(<\/mo>14<\/mn>,<\/mo>3<\/mn>)<\/mo>=<\/mo>1<\/mn><\/mrow>\\gcd(14,3)=1<\/annotation><\/semantics><\/math>gcd(14,3)=1; 14<\/mn>=<\/mo>4<\/mn>\u00d7<\/mo>3<\/mn>+<\/mo>2<\/mn><\/mrow>14=4\\times3+2<\/annotation><\/semantics><\/math>14=4\u00d73+2; 3<\/mn>=<\/mo>1<\/mn>\u00d7<\/mo>2<\/mn>+<\/mo>1<\/mn><\/mrow>3=1\\times2+1<\/annotation><\/semantics><\/math>3=1\u00d72+1; so 1<\/mn>=<\/mo>3<\/mn>\u2212<\/mo>1<\/mn>\u00d7<\/mo>2<\/mn>=<\/mo>3<\/mn>\u2212<\/mo>(<\/mo>14<\/mn>\u2212<\/mo>4<\/mn>\u00d7<\/mo>3<\/mn>)<\/mo>=<\/mo>5<\/mn>\u00d7<\/mo>3<\/mn>\u2212<\/mo>14<\/mn><\/mrow>1=3-1\\times2=3-(14-4\\times3)=5\\times3-14<\/annotation><\/semantics><\/math>1=3\u22121\u00d72=3\u2212(14\u22124\u00d73)=5\u00d73\u221214. So 14<\/mn>\u00d7<\/mo>(<\/mo>\u2212<\/mo>1<\/mn>)<\/mo>+<\/mo>3<\/mn>\u00d7<\/mo>5<\/mn>=<\/mo>1<\/mn><\/mrow>14\\times(-1)+3\\times5=1<\/annotation><\/semantics><\/math>14\u00d7(\u22121)+3\u00d75=1. Scale by 15: 14<\/mn>\u00d7<\/mo>(<\/mo>\u2212<\/mo>15<\/mn>)<\/mo>+<\/mo>3<\/mn>\u00d7<\/mo>75<\/mn>=<\/mo>15<\/mn><\/mrow>14\\times(-15)+3\\times75=15<\/annotation><\/semantics><\/math>14\u00d7(\u221215)+3\u00d775=15, i.e. 210<\/mn>\u00d7<\/mo>(<\/mo>\u2212<\/mo>1<\/mn>)<\/mo>+<\/mo>45<\/mn>\u00d7<\/mo>5<\/mn>=<\/mo>15<\/mn><\/mrow>210\\times(-1)+45\\times5=15<\/annotation><\/semantics><\/math>210\u00d7(\u22121)+45\u00d75=15… General solution: x=\u22121+3tx=-1+3t x=\u22121+3t, y=5\u221214ty=5-14t y=5\u221214t<\/strong> for any integer t<\/mi><\/mrow>t<\/annotation><\/semantics><\/math>t.<\/p>\n\n\n\n
                \n
              1. gcd<\/mi>\u2061<\/mo>(<\/mo>5<\/mn>,<\/mo>13<\/mn>)<\/mo>=<\/mo>1<\/mn><\/mrow>\\gcd(5,13)=1<\/annotation><\/semantics><\/math>gcd(5,13)=1: 13<\/mn>=<\/mo>2<\/mn>\u00d7<\/mo>5<\/mn>+<\/mo>3<\/mn><\/mrow>13=2\\times5+3<\/annotation><\/semantics><\/math>13=2\u00d75+3; 5<\/mn>=<\/mo>1<\/mn>\u00d7<\/mo>3<\/mn>+<\/mo>2<\/mn><\/mrow>5=1\\times3+2<\/annotation><\/semantics><\/math>5=1\u00d73+2; 3<\/mn>=<\/mo>1<\/mn>\u00d7<\/mo>2<\/mn>+<\/mo>1<\/mn><\/mrow>3=1\\times2+1<\/annotation><\/semantics><\/math>3=1\u00d72+1. Back-sub: 1<\/mn>=<\/mo>3<\/mn>\u2212<\/mo>2<\/mn>=<\/mo>3<\/mn>\u2212<\/mo>(<\/mo>5<\/mn>\u2212<\/mo>3<\/mn>)<\/mo>=<\/mo>2<\/mn>\u00d7<\/mo>3<\/mn>\u2212<\/mo>5<\/mn>=<\/mo>2<\/mn>(<\/mo>13<\/mn>\u2212<\/mo>2<\/mn>\u00d7<\/mo>5<\/mn>)<\/mo>\u2212<\/mo>5<\/mn>=<\/mo>2<\/mn>\u00d7<\/mo>13<\/mn>\u2212<\/mo>5<\/mn>\u00d7<\/mo>5<\/mn><\/mrow>1=3-2=3-(5-3)=2\\times3-5=2(13-2\\times5)-5=2\\times13-5\\times5<\/annotation><\/semantics><\/math>1=3\u22122=3\u2212(5\u22123)=2\u00d73\u22125=2(13\u22122\u00d75)\u22125=2\u00d713\u22125\u00d75. So 5<\/mn>\u00d7<\/mo>(<\/mo>\u2212<\/mo>5<\/mn>)<\/mo>+<\/mo>13<\/mn>\u00d7<\/mo>2<\/mn>=<\/mo>1<\/mn><\/mrow>5\\times(-5)+13\\times2=1<\/annotation><\/semantics><\/math>5\u00d7(\u22125)+13\u00d72=1, meaning 5<\/mn>\u2212<\/mo>1<\/mn><\/mrow><\/msup>\u2261<\/mo>\u2212<\/mo>5<\/mn>\u2261<\/mo>8<\/mn><\/mspace><\/mspace>(<\/mo>m<\/mi>o<\/mi>d<\/mi><\/mrow><\/mspace>13<\/mn>)<\/mo><\/mrow>5^{-1}\\equiv -5\\equiv 8\\pmod{13}<\/annotation><\/semantics><\/math>5\u22121\u2261\u22125\u22618(mod13). Modular inverse of 5 mod 13 is 8.<\/strong> Check: 5<\/mn>\u00d7<\/mo>8<\/mn>=<\/mo>40<\/mn>=<\/mo>3<\/mn>\u00d7<\/mo>13<\/mn>+<\/mo>1<\/mn>\u2261<\/mo>1<\/mn><\/mspace><\/mspace>(<\/mo>m<\/mi>o<\/mi>d<\/mi><\/mrow><\/mspace>13<\/mn>)<\/mo><\/mrow>5\\times8=40=3\\times13+1\\equiv1\\pmod{13}<\/annotation><\/semantics><\/math>5\u00d78=40=3\u00d713+1\u22611(mod13) \u2713<\/li>\n\n\n\n
              2. gcd<\/mi>\u2061<\/mo>(<\/mo>17<\/mn>,<\/mo>11<\/mn>)<\/mo>=<\/mo>1<\/mn>\u2223<\/mo>100<\/mn><\/mrow>\\gcd(17,11)=1\\mid100<\/annotation><\/semantics><\/math>gcd(17,11)=1\u2223100 \u2713. Find particular solution: back-sub gives 17<\/mn>\u00d7<\/mo>2<\/mn>\u2212<\/mo>11<\/mn>\u00d7<\/mo>3<\/mn>=<\/mo>1<\/mn><\/mrow>17\\times2-11\\times3=1<\/annotation><\/semantics><\/math>17\u00d72\u221211\u00d73=1… actually 17<\/mn>=<\/mo>1<\/mn>\u00d7<\/mo>11<\/mn>+<\/mo>6<\/mn><\/mrow>17=1\\times11+6<\/annotation><\/semantics><\/math>17=1\u00d711+6; 11<\/mn>=<\/mo>1<\/mn>\u00d7<\/mo>6<\/mn>+<\/mo>5<\/mn><\/mrow>11=1\\times6+5<\/annotation><\/semantics><\/math>11=1\u00d76+5; 6<\/mn>=<\/mo>1<\/mn>\u00d7<\/mo>5<\/mn>+<\/mo>1<\/mn><\/mrow>6=1\\times5+1<\/annotation><\/semantics><\/math>6=1\u00d75+1. So 1<\/mn>=<\/mo>6<\/mn>\u2212<\/mo>5<\/mn>=<\/mo>6<\/mn>\u2212<\/mo>(<\/mo>11<\/mn>\u2212<\/mo>6<\/mn>)<\/mo>=<\/mo>2<\/mn>\u00d7<\/mo>6<\/mn>\u2212<\/mo>11<\/mn>=<\/mo>2<\/mn>(<\/mo>17<\/mn>\u2212<\/mo>11<\/mn>)<\/mo>\u2212<\/mo>11<\/mn>=<\/mo>2<\/mn>\u00d7<\/mo>17<\/mn>\u2212<\/mo>3<\/mn>\u00d7<\/mo>11<\/mn><\/mrow>1=6-5=6-(11-6)=2\\times6-11=2(17-11)-11=2\\times17-3\\times11<\/annotation><\/semantics><\/math>1=6\u22125=6\u2212(11\u22126)=2\u00d76\u221211=2(17\u221211)\u221211=2\u00d717\u22123\u00d711. Scale by 100: 17<\/mn>\u00d7<\/mo>200<\/mn>+<\/mo>11<\/mn>\u00d7<\/mo>(<\/mo>\u2212<\/mo>300<\/mn>)<\/mo>=<\/mo>100<\/mn><\/mrow>17\\times200+11\\times(-300)=100<\/annotation><\/semantics><\/math>17\u00d7200+11\u00d7(\u2212300)=100. General: x<\/mi>=<\/mo>200<\/mn>\u2212<\/mo>11<\/mn>t<\/mi><\/mrow>x=200-11t<\/annotation><\/semantics><\/math>x=200\u221211t, y<\/mi>=<\/mo>\u2212<\/mo>300<\/mn>+<\/mo>17<\/mn>t<\/mi><\/mrow>y=-300+17t<\/annotation><\/semantics><\/math>y=\u2212300+17t. Positive integer solutions: x<\/mi>><\/mo>0<\/mn><\/mrow>x>0<\/annotation><\/semantics><\/math>x>0: t<\/mi><<\/mo>200<\/mn>\/<\/mi>11<\/mn>\u2248<\/mo>18.2<\/mn><\/mrow>t<200\/11\\approx18.2<\/annotation><\/semantics><\/math>t<200\/11\u224818.2; y<\/mi>><\/mo>0<\/mn><\/mrow>y>0<\/annotation><\/semantics><\/math>y>0: t<\/mi>><\/mo>300<\/mn>\/<\/mi>17<\/mn>\u2248<\/mo>17.6<\/mn><\/mrow>t>300\/17\\approx17.6<\/annotation><\/semantics><\/math>t>300\/17\u224817.6. So t<\/mi>=<\/mo>18<\/mn><\/mrow>t=18<\/annotation><\/semantics><\/math>t=18: x<\/mi>=<\/mo>200<\/mn>\u2212<\/mo>198<\/mn>=<\/mo>2<\/mn><\/mrow>x=200-198=2<\/annotation><\/semantics><\/math>x=200\u2212198=2, y<\/mi>=<\/mo>\u2212<\/mo>300<\/mn>+<\/mo>306<\/mn>=<\/mo>6<\/mn><\/mrow>y=-300+306=6<\/annotation><\/semantics><\/math>y=\u2212300+306=6. (x,y)=(2,6)(x,y)=(2,6) (x,y)=(2,6) is the only positive solution.<\/strong><\/li>\n<\/ol>\n\n\n\n
                \n\n\n\n

                Frequently Asked Questions<\/h2>\n\n\n\n

                What is the Euclidean algorithm?<\/strong> A method for finding the greatest common divisor (GCD) of two integers by repeated division with remainder. At each step, the larger number is replaced by the smaller, and the smaller by the remainder, until the remainder is 0. The last non-zero remainder is the GCD.<\/p>\n\n\n\n

                Why is the Euclidean algorithm useful?<\/strong> It finds the GCD far more efficiently than prime factorisation for large numbers. It is also the foundation for the extended Euclidean algorithm, which solves linear Diophantine equations and finds modular inverses \u2014 both essential in competition number theory and cryptography.<\/p>\n\n\n\n

                What is the extended Euclidean algorithm?<\/strong>An extension that, in addition to finding gcd<\/mi>\u2061<\/mo>(<\/mo>a<\/mi>,<\/mo>b<\/mi>)<\/mo><\/mrow>\\gcd(a, b)<\/annotation><\/semantics><\/math>gcd(a,b), finds integers x<\/mi><\/mrow>x<\/annotation><\/semantics><\/math>x and y<\/mi><\/mrow>y<\/annotation><\/semantics><\/math>y satisfying a<\/mi>x<\/mi>+<\/mo>b<\/mi>y<\/mi>=<\/mo>gcd<\/mi>\u2061<\/mo>(<\/mo>a<\/mi>,<\/mo>b<\/mi>)<\/mo><\/mrow>ax + by = \\gcd(a, b)<\/annotation><\/semantics><\/math>ax+by=gcd(a,b) (B\u00e9zout’s identity). It uses back-substitution through the steps of the standard algorithm.<\/p>\n\n\n\n

                What is B\u00e9zout’s lemma?<\/strong>For any integers a<\/mi><\/mrow>a<\/annotation><\/semantics><\/math>a and b<\/mi><\/mrow>b<\/annotation><\/semantics><\/math>b, there exist integers x<\/mi><\/mrow>x<\/annotation><\/semantics><\/math>x and y<\/mi><\/mrow>y<\/annotation><\/semantics><\/math>y such that a<\/mi>x<\/mi>+<\/mo>b<\/mi>y<\/mi>=<\/mo>gcd<\/mi>\u2061<\/mo>(<\/mo>a<\/mi>,<\/mo>b<\/mi>)<\/mo><\/mrow>ax + by = \\gcd(a, b)<\/annotation><\/semantics><\/math>ax+by=gcd(a,b). The extended Euclidean algorithm finds these x<\/mi><\/mrow>x<\/annotation><\/semantics><\/math>x and y<\/mi><\/mrow>y<\/annotation><\/semantics><\/math>y explicitly.<\/p>\n\n\n\n

                Does the Euclidean algorithm appear in the Ontario curriculum?<\/strong> GCD and LCM are in the Ontario curriculum from Grade 8 onward, but the Euclidean algorithm specifically is not prescribed. It is taught as a competition mathematics tool and a more efficient alternative to factor-list methods.<\/p>\n\n\n\n

                How does the Euclidean algorithm relate to the Euclid Contest?<\/strong> The Euclid Contest (CEMC) is named after Euclid, who described the algorithm around 300 BCE. The algorithm itself \u2014 and its extension to Diophantine equations and modular inverses \u2014 appears in Euclid Contest number theory problems at the Part B and Part C level.<\/p>\n\n\n\n

                \n\n\n\n

                See our related guides: Fermat’s Little Theorem guide<\/a> \u00b7 rules of divisibility guide<\/a> \u00b7 perfect numbers guide<\/a> \u00b7 Euclid math contest guide<\/a> \u00b7 COMC math contest guide<\/a> \u00b7 Canadian Mathematical Olympiad guide<\/a> \u00b7 AMC 8 guide<\/a> \u00b7 Gauss math contest guide<\/a> \u00b7 Grade 8 math curriculum Ontario<\/a> \u00b7 math competitions in Canada<\/a><\/em><\/p>\n\n\n\n

                \n\n\n\n

                The Euclidean algorithm is ancient mathematics that still underlies modern cryptography and competition number theory. Know it properly.<\/strong><\/p>\n\n\n\n

                \"euclidean<\/a><\/figure>\n","protected":false},"excerpt":{"rendered":"

                The Euclidean algorithm is one of the oldest algorithms in mathematics \u2014 described by Euclid around … Euclidean Algorithm Explained: Definition, Steps and Applications<\/span>Read more<\/a><\/p>\n","protected":false},"author":1,"featured_media":65477,"comment_status":"closed","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[1752,5907,17135,17160],"tags":[],"class_list":["post-65476","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-competitions","category-education","category-study-tips-and-tools","category-math-skills"],"yoast_head":"\nEuclidean Algorithm: Definition, Steps, Examples and Applications<\/title>\n<meta name=\"description\" content=\"The Euclidean algorithm \u2014 how to apply it step by step, why it works, extended Euclidean algorithm, and where it appears in competitions.\" \/>\n<meta name=\"robots\" content=\"index, follow, max-snippet:-1, max-image-preview:large, max-video-preview:-1\" \/>\n<link rel=\"canonical\" href=\"https:\/\/blog-admin.thethinkacademy.com\/blog\/2026\/08\/19\/euclidean-algorithm-guide\/\" \/>\n<meta property=\"og:locale\" content=\"en_US\" \/>\n<meta property=\"og:type\" content=\"article\" \/>\n<meta property=\"og:title\" content=\"Euclidean Algorithm: Definition, Steps, Examples and Applications\" \/>\n<meta property=\"og:description\" content=\"The Euclidean algorithm \u2014 how to apply it step by step, why it works, extended Euclidean algorithm, and where it appears in competitions.\" \/>\n<meta property=\"og:url\" content=\"https:\/\/blog-admin.thethinkacademy.com\/blog\/2026\/08\/19\/euclidean-algorithm-guide\/\" \/>\n<meta property=\"og:site_name\" content=\"Think Academy Canada Blog\" \/>\n<meta property=\"article:published_time\" content=\"2026-08-19T09:37:10+00:00\" \/>\n<meta property=\"article:modified_time\" content=\"2026-08-19T09:37:12+00:00\" \/>\n<meta property=\"og:image\" content=\"https:\/\/blog-admin.thethinkacademy.com\/wp-content\/uploads\/2026\/08\/ChatGPT-Image-Aug-19-2026-10_16_30-AM-1.png\" \/>\n\t<meta property=\"og:image:width\" content=\"1402\" \/>\n\t<meta property=\"og:image:height\" content=\"1122\" \/>\n\t<meta property=\"og:image:type\" content=\"image\/png\" \/>\n<meta name=\"author\" content=\"Think Academy\" \/>\n<meta name=\"twitter:card\" content=\"summary_large_image\" \/>\n<meta name=\"twitter:label1\" content=\"Written by\" \/>\n\t<meta name=\"twitter:data1\" content=\"Think Academy\" \/>\n\t<meta name=\"twitter:label2\" content=\"Est. reading time\" \/>\n\t<meta name=\"twitter:data2\" content=\"18 minutes\" \/>\n<script type=\"application\/ld+json\" class=\"yoast-schema-graph\">{\"@context\":\"https:\\\/\\\/schema.org\",\"@graph\":[{\"@type\":\"Article\",\"@id\":\"https:\\\/\\\/blog-admin.thethinkacademy.com\\\/blog\\\/2026\\\/08\\\/19\\\/euclidean-algorithm-guide\\\/#article\",\"isPartOf\":{\"@id\":\"https:\\\/\\\/blog-admin.thethinkacademy.com\\\/blog\\\/2026\\\/08\\\/19\\\/euclidean-algorithm-guide\\\/\"},\"author\":{\"name\":\"Think Academy\",\"@id\":\"https:\\\/\\\/blog-admin.thethinkacademy.com\\\/#\\\/schema\\\/person\\\/5e5752520edd7febcc1056443eab8850\"},\"headline\":\"Euclidean Algorithm Explained: Definition, Steps and Applications\",\"datePublished\":\"2026-08-19T09:37:10+00:00\",\"dateModified\":\"2026-08-19T09:37:12+00:00\",\"mainEntityOfPage\":{\"@id\":\"https:\\\/\\\/blog-admin.thethinkacademy.com\\\/blog\\\/2026\\\/08\\\/19\\\/euclidean-algorithm-guide\\\/\"},\"wordCount\":2734,\"image\":{\"@id\":\"https:\\\/\\\/blog-admin.thethinkacademy.com\\\/blog\\\/2026\\\/08\\\/19\\\/euclidean-algorithm-guide\\\/#primaryimage\"},\"thumbnailUrl\":\"https:\\\/\\\/blog-admin.thethinkacademy.com\\\/wp-content\\\/uploads\\\/2026\\\/08\\\/ChatGPT-Image-Aug-19-2026-10_16_30-AM-1.png\",\"articleSection\":[\"Competitions\",\"Education\",\"Study Tips And Tools\",\"Math Skills\"],\"inLanguage\":\"en-US\"},{\"@type\":\"WebPage\",\"@id\":\"https:\\\/\\\/blog-admin.thethinkacademy.com\\\/blog\\\/2026\\\/08\\\/19\\\/euclidean-algorithm-guide\\\/\",\"url\":\"https:\\\/\\\/blog-admin.thethinkacademy.com\\\/blog\\\/2026\\\/08\\\/19\\\/euclidean-algorithm-guide\\\/\",\"name\":\"Euclidean Algorithm: Definition, Steps, Examples and Applications\",\"isPartOf\":{\"@id\":\"https:\\\/\\\/blog-admin.thethinkacademy.com\\\/#website\"},\"primaryImageOfPage\":{\"@id\":\"https:\\\/\\\/blog-admin.thethinkacademy.com\\\/blog\\\/2026\\\/08\\\/19\\\/euclidean-algorithm-guide\\\/#primaryimage\"},\"image\":{\"@id\":\"https:\\\/\\\/blog-admin.thethinkacademy.com\\\/blog\\\/2026\\\/08\\\/19\\\/euclidean-algorithm-guide\\\/#primaryimage\"},\"thumbnailUrl\":\"https:\\\/\\\/blog-admin.thethinkacademy.com\\\/wp-content\\\/uploads\\\/2026\\\/08\\\/ChatGPT-Image-Aug-19-2026-10_16_30-AM-1.png\",\"datePublished\":\"2026-08-19T09:37:10+00:00\",\"dateModified\":\"2026-08-19T09:37:12+00:00\",\"author\":{\"@id\":\"https:\\\/\\\/blog-admin.thethinkacademy.com\\\/#\\\/schema\\\/person\\\/5e5752520edd7febcc1056443eab8850\"},\"description\":\"The Euclidean algorithm \u2014 how to apply it step by step, why it works, extended Euclidean algorithm, and where it appears in competitions.\",\"breadcrumb\":{\"@id\":\"https:\\\/\\\/blog-admin.thethinkacademy.com\\\/blog\\\/2026\\\/08\\\/19\\\/euclidean-algorithm-guide\\\/#breadcrumb\"},\"inLanguage\":\"en-US\",\"potentialAction\":[{\"@type\":\"ReadAction\",\"target\":[\"https:\\\/\\\/blog-admin.thethinkacademy.com\\\/blog\\\/2026\\\/08\\\/19\\\/euclidean-algorithm-guide\\\/\"]}]},{\"@type\":\"ImageObject\",\"inLanguage\":\"en-US\",\"@id\":\"https:\\\/\\\/blog-admin.thethinkacademy.com\\\/blog\\\/2026\\\/08\\\/19\\\/euclidean-algorithm-guide\\\/#primaryimage\",\"url\":\"https:\\\/\\\/blog-admin.thethinkacademy.com\\\/wp-content\\\/uploads\\\/2026\\\/08\\\/ChatGPT-Image-Aug-19-2026-10_16_30-AM-1.png\",\"contentUrl\":\"https:\\\/\\\/blog-admin.thethinkacademy.com\\\/wp-content\\\/uploads\\\/2026\\\/08\\\/ChatGPT-Image-Aug-19-2026-10_16_30-AM-1.png\",\"width\":1402,\"height\":1122},{\"@type\":\"BreadcrumbList\",\"@id\":\"https:\\\/\\\/blog-admin.thethinkacademy.com\\\/blog\\\/2026\\\/08\\\/19\\\/euclidean-algorithm-guide\\\/#breadcrumb\",\"itemListElement\":[{\"@type\":\"ListItem\",\"position\":1,\"name\":\"Home\",\"item\":\"https:\\\/\\\/blog-admin.thethinkacademy.com\\\/\"},{\"@type\":\"ListItem\",\"position\":2,\"name\":\"Euclidean Algorithm Explained: Definition, Steps and Applications\"}]},{\"@type\":\"WebSite\",\"@id\":\"https:\\\/\\\/blog-admin.thethinkacademy.com\\\/#website\",\"url\":\"https:\\\/\\\/blog-admin.thethinkacademy.com\\\/\",\"name\":\"Think Academy Canada Blog\",\"description\":\"\",\"potentialAction\":[{\"@type\":\"SearchAction\",\"target\":{\"@type\":\"EntryPoint\",\"urlTemplate\":\"https:\\\/\\\/blog-admin.thethinkacademy.com\\\/?s={search_term_string}\"},\"query-input\":{\"@type\":\"PropertyValueSpecification\",\"valueRequired\":true,\"valueName\":\"search_term_string\"}}],\"inLanguage\":\"en-US\"},{\"@type\":\"Person\",\"@id\":\"https:\\\/\\\/blog-admin.thethinkacademy.com\\\/#\\\/schema\\\/person\\\/5e5752520edd7febcc1056443eab8850\",\"name\":\"Think Academy\",\"image\":{\"@type\":\"ImageObject\",\"inLanguage\":\"en-US\",\"@id\":\"https:\\\/\\\/secure.gravatar.com\\\/avatar\\\/f79e3f7bff09863820040f04b26b5731542ae3733cf505c30733842df6e7ff82?s=96&d=mm&r=g\",\"url\":\"https:\\\/\\\/secure.gravatar.com\\\/avatar\\\/f79e3f7bff09863820040f04b26b5731542ae3733cf505c30733842df6e7ff82?s=96&d=mm&r=g\",\"contentUrl\":\"https:\\\/\\\/secure.gravatar.com\\\/avatar\\\/f79e3f7bff09863820040f04b26b5731542ae3733cf505c30733842df6e7ff82?s=96&d=mm&r=g\",\"caption\":\"Think Academy\"},\"sameAs\":[\"https:\\\/\\\/blog-admin.thethinkacademy.com\"],\"url\":\"https:\\\/\\\/blog-admin.thethinkacademy.com\\\/blog\\\/author\\\/thinkacademy\\\/\"}]}<\/script>\n<!-- \/ Yoast SEO plugin. -->","yoast_head_json":{"title":"Euclidean Algorithm: Definition, Steps, Examples and Applications","description":"The Euclidean algorithm \u2014 how to apply it step by step, why it works, extended Euclidean algorithm, and where it appears in competitions.","robots":{"index":"index","follow":"follow","max-snippet":"max-snippet:-1","max-image-preview":"max-image-preview:large","max-video-preview":"max-video-preview:-1"},"canonical":"https:\/\/blog-admin.thethinkacademy.com\/blog\/2026\/08\/19\/euclidean-algorithm-guide\/","og_locale":"en_US","og_type":"article","og_title":"Euclidean Algorithm: Definition, Steps, Examples and Applications","og_description":"The Euclidean algorithm \u2014 how to apply it step by step, why it works, extended Euclidean algorithm, and where it appears in competitions.","og_url":"https:\/\/blog-admin.thethinkacademy.com\/blog\/2026\/08\/19\/euclidean-algorithm-guide\/","og_site_name":"Think Academy Canada Blog","article_published_time":"2026-08-19T09:37:10+00:00","article_modified_time":"2026-08-19T09:37:12+00:00","og_image":[{"width":1402,"height":1122,"url":"https:\/\/blog-admin.thethinkacademy.com\/wp-content\/uploads\/2026\/08\/ChatGPT-Image-Aug-19-2026-10_16_30-AM-1.png","type":"image\/png"}],"author":"Think Academy","twitter_card":"summary_large_image","twitter_misc":{"Written by":"Think Academy","Est. reading time":"18 minutes"},"schema":{"@context":"https:\/\/schema.org","@graph":[{"@type":"Article","@id":"https:\/\/blog-admin.thethinkacademy.com\/blog\/2026\/08\/19\/euclidean-algorithm-guide\/#article","isPartOf":{"@id":"https:\/\/blog-admin.thethinkacademy.com\/blog\/2026\/08\/19\/euclidean-algorithm-guide\/"},"author":{"name":"Think Academy","@id":"https:\/\/blog-admin.thethinkacademy.com\/#\/schema\/person\/5e5752520edd7febcc1056443eab8850"},"headline":"Euclidean Algorithm Explained: Definition, Steps and Applications","datePublished":"2026-08-19T09:37:10+00:00","dateModified":"2026-08-19T09:37:12+00:00","mainEntityOfPage":{"@id":"https:\/\/blog-admin.thethinkacademy.com\/blog\/2026\/08\/19\/euclidean-algorithm-guide\/"},"wordCount":2734,"image":{"@id":"https:\/\/blog-admin.thethinkacademy.com\/blog\/2026\/08\/19\/euclidean-algorithm-guide\/#primaryimage"},"thumbnailUrl":"https:\/\/blog-admin.thethinkacademy.com\/wp-content\/uploads\/2026\/08\/ChatGPT-Image-Aug-19-2026-10_16_30-AM-1.png","articleSection":["Competitions","Education","Study Tips And Tools","Math Skills"],"inLanguage":"en-US"},{"@type":"WebPage","@id":"https:\/\/blog-admin.thethinkacademy.com\/blog\/2026\/08\/19\/euclidean-algorithm-guide\/","url":"https:\/\/blog-admin.thethinkacademy.com\/blog\/2026\/08\/19\/euclidean-algorithm-guide\/","name":"Euclidean Algorithm: Definition, Steps, Examples and Applications","isPartOf":{"@id":"https:\/\/blog-admin.thethinkacademy.com\/#website"},"primaryImageOfPage":{"@id":"https:\/\/blog-admin.thethinkacademy.com\/blog\/2026\/08\/19\/euclidean-algorithm-guide\/#primaryimage"},"image":{"@id":"https:\/\/blog-admin.thethinkacademy.com\/blog\/2026\/08\/19\/euclidean-algorithm-guide\/#primaryimage"},"thumbnailUrl":"https:\/\/blog-admin.thethinkacademy.com\/wp-content\/uploads\/2026\/08\/ChatGPT-Image-Aug-19-2026-10_16_30-AM-1.png","datePublished":"2026-08-19T09:37:10+00:00","dateModified":"2026-08-19T09:37:12+00:00","author":{"@id":"https:\/\/blog-admin.thethinkacademy.com\/#\/schema\/person\/5e5752520edd7febcc1056443eab8850"},"description":"The Euclidean algorithm \u2014 how to apply it step by step, why it works, extended Euclidean algorithm, and where it appears in competitions.","breadcrumb":{"@id":"https:\/\/blog-admin.thethinkacademy.com\/blog\/2026\/08\/19\/euclidean-algorithm-guide\/#breadcrumb"},"inLanguage":"en-US","potentialAction":[{"@type":"ReadAction","target":["https:\/\/blog-admin.thethinkacademy.com\/blog\/2026\/08\/19\/euclidean-algorithm-guide\/"]}]},{"@type":"ImageObject","inLanguage":"en-US","@id":"https:\/\/blog-admin.thethinkacademy.com\/blog\/2026\/08\/19\/euclidean-algorithm-guide\/#primaryimage","url":"https:\/\/blog-admin.thethinkacademy.com\/wp-content\/uploads\/2026\/08\/ChatGPT-Image-Aug-19-2026-10_16_30-AM-1.png","contentUrl":"https:\/\/blog-admin.thethinkacademy.com\/wp-content\/uploads\/2026\/08\/ChatGPT-Image-Aug-19-2026-10_16_30-AM-1.png","width":1402,"height":1122},{"@type":"BreadcrumbList","@id":"https:\/\/blog-admin.thethinkacademy.com\/blog\/2026\/08\/19\/euclidean-algorithm-guide\/#breadcrumb","itemListElement":[{"@type":"ListItem","position":1,"name":"Home","item":"https:\/\/blog-admin.thethinkacademy.com\/"},{"@type":"ListItem","position":2,"name":"Euclidean Algorithm Explained: Definition, Steps and Applications"}]},{"@type":"WebSite","@id":"https:\/\/blog-admin.thethinkacademy.com\/#website","url":"https:\/\/blog-admin.thethinkacademy.com\/","name":"Think Academy Canada Blog","description":"","potentialAction":[{"@type":"SearchAction","target":{"@type":"EntryPoint","urlTemplate":"https:\/\/blog-admin.thethinkacademy.com\/?s={search_term_string}"},"query-input":{"@type":"PropertyValueSpecification","valueRequired":true,"valueName":"search_term_string"}}],"inLanguage":"en-US"},{"@type":"Person","@id":"https:\/\/blog-admin.thethinkacademy.com\/#\/schema\/person\/5e5752520edd7febcc1056443eab8850","name":"Think Academy","image":{"@type":"ImageObject","inLanguage":"en-US","@id":"https:\/\/secure.gravatar.com\/avatar\/f79e3f7bff09863820040f04b26b5731542ae3733cf505c30733842df6e7ff82?s=96&d=mm&r=g","url":"https:\/\/secure.gravatar.com\/avatar\/f79e3f7bff09863820040f04b26b5731542ae3733cf505c30733842df6e7ff82?s=96&d=mm&r=g","contentUrl":"https:\/\/secure.gravatar.com\/avatar\/f79e3f7bff09863820040f04b26b5731542ae3733cf505c30733842df6e7ff82?s=96&d=mm&r=g","caption":"Think Academy"},"sameAs":["https:\/\/blog-admin.thethinkacademy.com"],"url":"https:\/\/blog-admin.thethinkacademy.com\/blog\/author\/thinkacademy\/"}]}},"yoast_meta_description":"The Euclidean algorithm \u2014 how to apply it step by step, why it works, extended Euclidean algorithm, and where it appears in competitions.","yoast_focus_keyword":"euclidean algorithm","yoast_seo_title":"Euclidean Algorithm: Definition, Steps, Examples and Applications","_links":{"self":[{"href":"https:\/\/blog-admin.thethinkacademy.com\/wp-json\/wp\/v2\/posts\/65476","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/blog-admin.thethinkacademy.com\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/blog-admin.thethinkacademy.com\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/blog-admin.thethinkacademy.com\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/blog-admin.thethinkacademy.com\/wp-json\/wp\/v2\/comments?post=65476"}],"version-history":[{"count":1,"href":"https:\/\/blog-admin.thethinkacademy.com\/wp-json\/wp\/v2\/posts\/65476\/revisions"}],"predecessor-version":[{"id":65481,"href":"https:\/\/blog-admin.thethinkacademy.com\/wp-json\/wp\/v2\/posts\/65476\/revisions\/65481"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/blog-admin.thethinkacademy.com\/wp-json\/wp\/v2\/media\/65477"}],"wp:attachment":[{"href":"https:\/\/blog-admin.thethinkacademy.com\/wp-json\/wp\/v2\/media?parent=65476"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/blog-admin.thethinkacademy.com\/wp-json\/wp\/v2\/categories?post=65476"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/blog-admin.thethinkacademy.com\/wp-json\/wp\/v2\/tags?post=65476"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}