The greatest common divisor(GCD) of two integers is an integer that divides the two numbers at the same time giving an integer quotient and a null remainder and there is not an integer greater than it which is at the same time a divisor of the two numbers.
The greatest common divisor is also the greatest common factor of the two numbers.
If it is impossible to factorize two numbers, it is because their unique common factor is equal to 1, then their greatest common multiple is equal to 1 too.
Example : the greatest common divisor(GCD) of 10 and 6 is 2. Then we can make the factorization of 10 + 6 by choosing their GCD as the common factor: 10 + 6 = 2(5 + 3) so the GCD of 5 and 3 is 1.
The GCD is used for example to simplify a fraction in order to make it irreducible, we calculate the greatest common divisor of its numerator and its denominator and by simplifying them by the GCD calculated, we find the irreducible equivalent of that fraction.
Click on the link below for downloading the JavaScript project of the application.
Download source code
Code snippet:
var nombre1,nombre2,diviseur;
nombre1=parseInt(prompt("Enter the first number"));
nombre2=parseInt(prompt("Enter the second number"));
if(nombre1>0 && nombre2>0){
for(var i=1;i<=nombre1;i++){
if((nombre1%i==0)&&(nombre2%i==0)){
diviseur=i;
}
}
alert("GCD("+nombre1+";"+nombre2+")"+" = "+diviseur);
}
What is a prime number in maths?
We know by definition that a prime number is a whole number which has only two divisors, 1 and the number itself.
Note: 1 is not a prime number. Apart from 2 all prime numbers are odd numbers but not all odd numbers are prime numbers.
Here is the list of all prime numbers less than 50:
2; 3; 5; 7; 11; 13; 17; 19; 23; 29; 31; 37; 41; 43; 47.
To manually check if positive integers are prime numbers, we do a successive division of those integers by the successive prime numbers starting from the smallest.
We stop the successive divisions at the level of the division which gives a zero remainder(first case) or at the level of that which gives a quotient less than or equal to the divisor(second case).
In the first case we conclude that the whole number is not a prime number.
In the second case we conclude that the whole number is a prime number.
Example: Let's check if 15 and 17 are prime numbers.
15/2 : quotient=7 remainder=1
15/3 : quotient=5 remainder=0
Since the remainder of the second division is zero then 15 is not a prime number.
17/2 : quotient=8 remainder=1
17/3 : quotient=5 remainder=2
17/5 : quotient=3 remainder=2
As the third division gives a quotient less than the divisor, we stop there and conclude that 17 is a prime number.
Knowing the prime numbers makes it easy to decompose a given number into products of prime factors.
This arithmetic JavaScript example of code can help you to verify if a given whole number is a prime number. The algorithm used in this program acts by dividing the number to check several times by divisors which evolve from 1 to the number to check, by addition of 1 to the divisor at each new division. Everytime the rest of a division is null, a variable which contains zero at the beginning of the program increase by one. At the end, the program verify the contents of the variable, if the number in the variable is bigger than 2, the program displays the number to check, followed by the phrase 'is not a prime number' otherwise the variable contains 2 and the program displays the number to check, followed by the phrase 'is a prime number'.
Download source code
Code snippet:
var nombre, compte=0;
nombre=parseInt(prompt("Enter a number"));
if(nombre>0){
for(var i=1;i<=nombre;i++){
if(nombre%i==0){
compte=compte+1;
}
}
if(compte==2){
alert(nombre+" is a prime number.");
}
else{
alert(nombre+" is not a prime number.");
}
}
else{
alert("Enter a value > 0 ");
}
You can find here the source code of a JavaScript program that displays a list of prime numbers in the range of two integers that you choose.
A list of prime numbers with JavaScript.
What are the least common multiples?
In math, by definition, the least common multiple or lowest common multiple of two whole numbers is the smallest number(positive integer) which is the multiple at the same time of the two numbers. This means that if
the least common multiple is successively divided by the two numbers
we are going to see that the rests of the two divisions are null and it is impossible to find another common multiple of the two numbers that is smallest than the least common multiple. For example: 12 is the least common multiple of 4 and 6, that means there is not another number smallest than 12 that is divisible by both 4 and 6.
Here are some examples of least common multiples:
The least common multiple of 3 and 4 is 12
The least common multiple of 8 and 12 is 24
The least common multiple of 9 and 12 is 36
The least common multiple of 6 and 8 is 24
The least common multiple of 4 and 9 is 36
Here is the method to manually calculate the least common multiple of two integers:
• Decompose each of the two numbers into products of prime factors;
• We express the prime factors having the same value as a power, for each of the two numbers;
• We choose each common-factor to the two numbers. In the case where two factors, one of which belongs to the first number and the other to the second number, have the same value and the same power, one of the two is chosen; if they have the same value and different powers, the one with the greatest power is chosen.
• We also choose the factors not common to the two numbers.
The least common multiple is obtained by multiplying the chosen common and not common factors together.
example 1: 12=2^2*3 and 30=2*3*5
The least common multiple of 12 and 30 is 2^2*3*5=4*3*5=60
example 2: 16=2^4 and 20=2^2*5
The least common mutiple of 16 and 20 is 2^4*5=16*5=80
If two integers have no common factors greater than 1, their least common multiple is their product, just multiply the two numbers together.
We are going to see how the algorithm of this JavaScript example of program works.
The algorithm uses two variables which must contain the two natural numbers whose least common multiple we are looking for. At the beginning, the algorithm considers the least common multiple of the two numbers as the product of the multiplication of the two numbers. This product is divided at the same time by the two numbers, if the rest of the two divisions is zero, a variable called 'multiple' receives the value of the product. As long as the product is bigger than the two numbers, 1 is subtracted from its value and the two divisions start again with the new value of the product. The two simultaneous divisions stop when the algorithm notices that there is no more a new value of the product which is divisible by both numbers or when the value in the variable 'multiple' is equal to one of the two numbers. The last value stored in the variable 'multiple' is then displayed as the least common multiple of the two numbers.
Download source code
Code snippet:
var nombre1,nombre2,multiple;
nombre1=parseInt(prompt("Enter the firs number"));
nombre2=parseInt(prompt("Enter the second number"));
if(nombre1>0 && nombre2>0){
for(var i=nombre1*nombre2;i>=nombre1;i--){
if((i%nombre1==0)&&(i%nombre2==0)){
multiple=i;
}
}
alert("LCM("+nombre1+";"+nombre2+")"+" = "+multiple);
}