Least Common Multiple (LCM)



The least common multiple (LCM) of two or more numbers is the smallest number that is a multiple of each of the given numbers. In other words, it is the smallest number that is divisible by all the given numbers without leaving a remainder.

If $a$ and $b$ are integers, then a common multiple of $a$ and $b$ is an integer $c$ such that $a|c$ and $b|c$.If  $a$ and $b$ are both non zero, then they have positive common multiples, so by the well ordering principle they have a least common multiple, or more precisely, a least positive common multiple.This is the unique positive integer $l$ satisfying
1)if $a|l$ and $b|l$ ( so $l$ is the common multiple) and 
2)if $a|c$ and $b|c$ , with $c>0$ and $l \le c$ ( so no positive common multiple is less than $l$).

we usually denote $l$ by $lcm(a,b)$. or simply $[a,b]$.For example $lcm(15,10)=30$, Since the positive multiples of 15 are 15,30,45,....while those of 10 are 10,20,30,40,.....The properties of least common multiples can be deduced from those of the greatest common divisor, by means of the following result.
If $a$ and $b$ are positive integers, with $d=gcd(a,b)$ and $l=lcm(a,b)$. Then $$dl=ab$$ 

To find the LCM of two or more numbers, you can use various methods, such as prime factorization, listing multiples, or using the LCM formula.

Here's how you can find the LCM using the prime factorization method:

Prime Factorization Method:
Express each number as a product of its prime factors.
Identify the highest power of each prime factor that appears in any of the factorizations.
Multiply all the highest powers together to find the LCM.

Example: 
Let's find the LCM of 12 and 18:
Prime factorization of 12: $12=2^2 \times 3^1$
Prime factorization of 18: $18 = 2 \times 3^2$

The highest power of 2 is $2^2$, and the highest power of 3 is $3^2$.

$LCM = 2^2 \times 3^2 = 4 \times 9 =36$

Listing Multiples Method:
List the multiples of each number until you find a common multiple.
The first common multiple is the LCM.


LCM Formula:

If you have two numbers, $a$ and $b$, the LCM can be calculated using the formula:

$\text{LCM}(a, b) = \frac{|a \times b|}{\text{GCD}(a,b)}$

where $\text{GCD}(a, b)$ represents the greatest common divisor of $a$ and $b$.

Example:

Find the LCM of 15 and 25 using the LCM formula.

First, we need to find the greatest common divisor (GCD) of 15 and 25.

To find the GCD, we can use the Euclidean algorithm or simply list the common factors. In this case, the common factors of 15 and 25 are 1 and 5. The greatest common divisor (GCD) is 5.


Now, we can use the LCM formula: $\text{LCM}(a, b) = \frac{|a \times b|}{\text{GCD}(a, b)}$

Substitute the values: $\text{LCM}(15, 25) = \frac{|15 \times 25|}{5}$

Calculate the product: $\text{LCM}(15, 25) = \frac{375}{5} = 75$
So, the LCM of 15 and 25 is 75.

Choose the method that works best for you or fits the numbers you are dealing with. The prime factorization method is generally efficient for smaller numbers, while the LCM formula can be more efficient for larger numbers or when you already have the GCD available.

Example:Find LCM of 1240 and 5300 using GCD ( university Question)

GCD(5300,1240)=20

LCM(5300,1240)=(5300*1240)/20=328600

Comments

Post a Comment

Popular posts from this blog

Number Theory CST 292 KTU IV Semester Honors Course Notes Dr Binu V P 9847390760

About me Syllabus Scheme Teaching Plan Model Question Paper University Question Papers Assignment-1 Module-1  Introduction Well ordering principle Group Ring Fields Group Ring Fields in detail Divisibility Modular Arithmetic GCD- Euclidean Algorithm Bezout's Identity Extended Euclidean Algorithm LCM-Least Common Multiple Linear Diophantine Equations Modular Division Module-II Prime Numbers and Prime-Power Factorisation Fermat and Mersenne Prime Primality Testing and Factorization Miller Rabin Primality Testing Algorithm Fermat  Factorization Congruence Modular Exponentiation Linear Congruences Simultaneous Linear Congruences- Chinese Remainder Theorem Fermat's Little Theorem and Euler's Theorem Wilson's Theorem Module-III Congruence with Prime modulus Congruence with Prime power modulus Pseudoprime and Carmichael Numbers Euler's Totient Function Cryptography The Group of Units - Primitive Roots Module-IV Quadratic Residues-Legendre and Jacobi Symbols Arithmetic Func
Read more

Sum of Squares

Image
In this our aim is to determine which integers can be expressed as the sum of given number of squares ie; which have the form $x_1^2+x_2^2+\cdots+x_k^2$, where each $x_i \in \mathbb{Z}$, for a given $k$. Definition: For each integer $k \ge 1$, let $S_k=\{n|n=x_1^2+x_2^2+\cdots+x_k^2$ for some $x_1,x_2,\ldots,x_k \in \mathbb{Z} \}$ , the set of all sum of $k$ squares. Example: $S_1=\{0,1,4,9,\ldots\}$ is the set of all squares. By inspection $S_2$, the set of sum of two squares contains 0,1,2,4,5 and 8 but not 3,6, or 7. Lemma: The set $S_2$ contains, the sum of two squares is closed under multiplication ie; if $s,t \in S_2$ , then $st \in S_2$. Proof:Let $s=a_1^2+b_1^2$ and $t=a_2^2+b_2^2$ be the elements of $S_2$, where $a_1,b_1,a_2,b_2 \in \mathbb{Z}$. Then the identity $$(a_1^2+b_1^2)(a_2^2+b_2^2)=(a_1a_2-b_1b_2)^2+(a_1b_2+b_1a_2)^2$$ This shows that $st \in S_2$ Example: We have $8=2^2+2^2$ and $10=3^2+1^2$ so $8.10=80=(2.3-2.1)^2+(2.1+2.3)^2=4^2+8^2$ Note: an equivalent ident
Read more

Quadratic Residues-Legendre and Jacobi Symbols

Image
Quadratic Congruence   There is a general question whether an integer $a$ has a square root $\pmod{n}$ and if so, how many are there and how one can find them. We know that the solution of the quadratic equation can be found by  $$x=\frac{-b \pm \sqrt{b^2-4ac}}{2a}$$ If we want to apply this to the case where $a,b,c \in Z_n$, then $2a$ to be unit in $\pmod{n}$, so that we can divide by $2a$. We can write the equation in the form $$(2ax+b)^2=b^2-4ac$$ If we can find all the square roots $s$ of $b^2-4ac$ in $\mathbb{Z}_n$, we can then find all the solutions $x \in \mathbb{Z}_n$ of the quadratic equation of the form $2ax+b=s$, or equivalently $x=(s-b)/2a$. If we look at the square roots at $\mathbb{Z}_{15}$, then  1 and 4 have four square roots each($\pm 1 ,\pm 4$ and $\pm 2,\pm 7$ respectively, while the other units have none. Example: Find all the solutions of $x^2-3x+2 \equiv 0 \pmod{15}$ given $a=1, b=−3$ and $c=2,$ we have: $b^2−4ac=(−3)^2−4(1)(2)=9−8=1$ So, $b^2−4ac=1.$ Now, we ne
Read more