File:GCD through successive divisions.svg

Original file(SVG file, nominally 660 × 825 pixels, file size: 4 KB)

Captions

Captions

The algorithm transforms gradually two positive integers into another pair having the same common divisors.  After each euclidean division,  the divisor‑remainder ordered pair becomes a possible dividend‑divisor,  until a decisive zero.

Summary

edit
Description
English:
The  GCD  of  two  natural  numbers
is their common divisor,  multiple of all their common divisors.  To  calculate  it,
the Euclidean algorithm transforms gradually two positive integers into another pair
having  the  same  set  of  common  divisors.   After  each  euclidean  division,
the  divisor‑remainder  pair  becomes  a  possible  dividend‑divisor,   until  a
decisive  zero.   The  previous  remainder  is  then  the  wanted  GCD.
The   Euclidean   algorithm   finds
the  GCD  of  two  positive  integers
through  successive  divisions.
For  a  same  result,
each  euclidean  division
translated  into  an  iterated  subtraction.
 Flow  charts,   in  order  to  calculate  the  GCD  of  two  natural  integers 

Key of the proof:   if two integers are multiples of a certain integer k,  then their difference
or their sum is also a multiple of k
.  Consequence:  the set of common divisors of a given pair
of  integers  is  unchanged,   when  the  greatest  element  of  the  pair  is  replaced  with
the  positive  difference  of  the  two  elements,   like  in  the  second  flow  chart.
For  example,   72–20 = 52,  52–20 = 32,  32–20 = 12.   And  the  following  ordered  pairs
have  the  same  set  of  common  divisors:   (72,  20),  (52,  20),  (32,  20),  (12,  20). 
In short,  (72,  20)  and  (20,  12)  have the same common divisors.  When  72  and  20
enter  the  Euclidean  algorithm  as  initial  values  of  d  and  g,   12  appears  in  this
subsequenceof remainders:   (72,  20,  12),   returned  below  in  the  second  example.

20  is  the  remainder  of  the  euclidean  division of  20  by  72,
while  12  is the remainder when you divise  72  by  20.   In pseudo‑code,  the expression
20  mod  72  evaluates to  20,  while  72  mod  20  evaluates to  12.  Indeed  20 = 20 - 0 × 72,
while  12 = 72 - 3 × 20.   Each quotient like  0  or  3  falls into oblivion in the Euclidean algorithm.
In Python    like  in JavaScript,   20 % 72  returns  20,   and   72 % 20  —> 12,
where   %   means  modulo.


First  translation  in  JavaScript.
When  you  copy  the  following  line, 
and then paste it in the adress bar of your browser : 
JavaScript: g = 72; d = 20; s =" PGCD("+ d +", "+ g +") = "; while( g ){ r = d % g; d = g; g = r } s + d;
your  browser  executes  the  JavaScript code
when you type  Enter.   If it is not executed,
then  enable  JavaScript   in  your  browser.
And then by entering other positive integers
instead of  72 and 20,  you obtain their GCD.

Second  translation  in  JavaScript.
  Example  more  comprehensible,
  through  copious  comments  placed  between   /*  and  */
/*  To open  a  Firefox  window
 dedicated to JavaScript code:   Shift + F4   */

 d = 20; g = 72;
/*  Imperative:  two positive integers enter the calculation.
 These conditions could be automatically verified in a more
 developed function    GCD = function(… ){… },    which
 would return an alert message in a case of abnormal use.
 See  instruction  try  in
File:GCD_through successive_subtractions.svg
 Here an abnormal use is not anticipated.  Therefore take care
 to  replace   20  and  72   with positive integers,
 when you order the GCD of two other numbers.

 Why name  g  the second variable ?⸮      G   evokes   “Greatest”
 in acronym  GCD,   zero being the greatest (positive) integer
 for the partial order named  “divisibility”:
 zero is the mUlTiPlE of all integers.  */

mcd = "(" + d +", "+ g;
/*  Just after the values of type  Number  are assigned
 to  d  and  g,   a value of type  String  is attributed to the
 variable named  mcd.   “String”  means  “string of characters”.
 The first character  mcd.charAt( 0 )  is a parenthesis.   And
 then the sign   +   orders either   “add the numbers”  or
 “concatenate the strings”,  according to the context.  After
 a string,   +  orders a concatenation.  So the value Number of
 d  is tacitly converted into its writing in decimal numeration:
 a short‑lived string   (20.).toString( 10 )  comes after  "("
 of length 1.  The syntax that folllows has a similar meaning.

 The values   20  and  72   are stored in the initial value
 "(20, 72"  of  mcd,   before the loop below modifies the
 two values  Number  to obtain their GCD.  */


//  sqr = " Sequence of “all remainders”:\n " + mcd;
/*  Two slashes  //  marks a beginning of comment
 placed on the same line,   not executed by an interpreter
 of JavaScript.  The line above that begins with two slashes
 is a comment,  like here the text placed between its two
 particular pairs of characters  (like in CSS).

 But if this first pair of slashes is removed,
 then this line becomes an executable bit of code like the others,
 so the value  String   on this new code line is assigned to  sqr.
 The character  "\n"  of this string begins its second line,  equal
 to  mcd  for the moment.   Below the unique loop of the code will
 modify the initial value of  sqr,  if the second pair of slashes
 is also removed in this loop.  */


while( g ){
/*  beginning of the  loop.
 Between the brackets of  while,   the expression is implicitly
 translated for a short while into an object of type  Boolean,
 if necessary.   Its  value  is  true  or  false.
 Equivalent code:   while( Boolean( g ))
 For example,   Boolean( 72 )  returns  true:
 the required value to enter the loop.

 Other equivalent code:   while( g > 0 )
 You can verify,  of course:    ( 72 > 0 )  —> true
 ( 72 > 0 ).constructor  —> function Boolean() { [native code] }

 In a later case,   Boolean( 0 )  —> false.
 When  Boolean( g )  returns  false,   the entry into the loop
 is refused,  and the code after the loop is executed.  */

    r = d % g;
/*  %  is the operator  modulo.
 At the first instance of the variable name  r,
 a new variable named  r  is created,  of global scope.
 The remainder of the euclidean division of  d  by  g
 is assigned to the variable  r  (r like “remainder”).
*/

    d = g; g = r;
/*  possible  dividend-divisor  pair
 of a further division,   if  g  is not zero  */

//    sqr += ", "+ g;
/*  facultative code actually considered as comment,
 but executable if the slashes are removed.  An error
 is returned if this only pair of slashes is removed.
 Equivalent code:   sqr = sqr + ", "+ g;  */
}
/*  end of the  loop  while( g )  */


" GCD" + mcd +") = "+ d;  /*  returns a string with the wanted GCD
*/

//  sqr += ").";
/*  When the three pairs of slashes above are removed,
 the definitive value of  sqr  is returned:   the sequence
 of  “all remainders”  for the initial value of pair  (d, g).
 Anywhere in the sequence of remainders,  two successive
 integers have always the same set of common divisors.

 Keyboard shortcut in Firefox to execute the code:   Ctrl + L   */
Date
Source Own work
Author Arthur Baelde
Other versions
SVG development
InfoField
 
The SVG code is valid.
 
This /Baelde was created with a text editor.

Licensing

edit
Arthur Baelde, the copyright holder of this work, hereby publishes it under the following license:
w:en:Creative Commons
attribution share alike
This file is licensed under the Creative Commons Attribution-Share Alike 4.0 International license.
Attribution: Arthur Baelde
You are free:
  • to share – to copy, distribute and transmit the work
  • to remix – to adapt the work
Under the following conditions:
  • attribution – You must give appropriate credit, provide a link to the license, and indicate if changes were made. You may do so in any reasonable manner, but not in any way that suggests the licensor endorses you or your use.
  • share alike – If you remix, transform, or build upon the material, you must distribute your contributions under the same or compatible license as the original.

File history

Click on a date/time to view the file as it appeared at that time.

Date/TimeThumbnailDimensionsUserComment
current13:09, 22 May 2024Thumbnail for version as of 13:09, 22 May 2024660 × 825 (4 KB)Arthur Baelde (talk | contribs)Uploaded own work with UploadWizard

Metadata