GCD_through_successive_subtractions.svg
Summary
Description GCD through successive subtractions.svg |
English:
The
set
of
common
divisors
of two given
natural numbers
is the set of divisors of one and only one natural number, called the “greatest common divisor” of the initial pair. To prove its existence, it is sufficient to exhibit we can always calculate it, from any pair of natural numbers. How to understand “greatest”?
The order
in question is divisibility:
a partial order
on set ℕ of natural numbers. For example, 2 is a common divisor
that can be written:
We will soon calculate the greatest common divisor
Zero is multiple of any natural number, in other words, zero is the
greatest
element of ℕ for divisibility.
is not the greatest natural number for the usual order
relation
, of which the symbol
The least element of ℕ for divisibility is 1.
the set of common divisors are multiples of any element is also a multiple Conversely, every common divisor is also a divisor In other words, also the set of common divisors Under the algorithm of the image, is replaced and then by repeating the process replaced And then replaced Finally the step‑by‑step process replaces the initial pair goes out of the loop of subtractions, and affirms: Instead of replacing with the four successive pairs: we could get directly the last pair by the Euclidean division It does not matter there are 4 successive subtractions of 6, we can ignore 4: the quotient value of this Euclidean division. Actually, every sequence of subtractions of a same number can be replaced with an Euclidean division by this number. Thus we discover the more known algorithm of GCD through successive Euclidean divisions, by improving the present algorithm of subtractions.
A novice
in coding
can copy and paste in a window dedicated to
JavaScript
one of the following comparisons, and then command the execution:
/* To open a Firefox window
dedicated to JavaScript code: Shift + F4 */
d = r = k = 182; p = 238; // example of input values,
// that we can replace with two other natural numbers
if( s = p){ // if the common value of s and p is not zero
while(r){ // while the value of r is not zero
if(r < s){ // in this case, reverse the values of r and s
d = s; s = r; r = d }
r = r-s } // end of the loop 'while(r)'
d = s } // end of the block that begins with 'if( s = p)'
" GCD("+ k +", "+ p +") = "+ d; // output: a String object
// Keyboard shortcut in Firefox to execute the code: Ctrl + L
On the image top, means that of natural numbers. The previous JavaScript code works only if the two input values are natural numbers. Here is an improvement of the previous code, where the input values assigned are verified. try{ // in case of error in this block,
// execution failure of this code block, go to 'catch'
d = r = k = 408; p = 255; // example of input values
var b; // global scope declaration
s = function(n){
// to test the value of parameter n: is it a natural number?
b = n.constructor == Number; // Boolean value
if( !b // first incorrect case
|| n < 0 || n != Math.floor(n) // other incorrect cases
) throw n
// in one of the previous cases, n is thrown as error
}; // end of assignment to variable s
s(k); s(p); // verifications
if( s = p){ // if the common value of s and p is not zero
while(r){
if(r < s){d = s; s = r; r = d} r = r-s } d = s }
" GCD("+ k +", "+ p +") = "+ d
}catch(e){ // in case of error (if e is thrown)
" "+( b ? e +" is not a natural number.":
" Incorrect code.")
}
Français :
Voir la version
en français…
|
Date | |
Source | Own work |
Author | Arthur Baelde |
Other versions | |
SVG development
InfoField
|
This /Baelde was created with a
text editor
.
|
Licensing
-
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.