GCD vs LCM

Number Theory Level 1

What positive integer, $x,$ satisfies these equations?

$\text{gcd}(391,x) = 23$
$\text{lcm}(391,x) = 7429$

Note: $\text{gcd}$ and $\text{lcm}$ denote the greatest common divisor and lowest common multiple respectively.

The answer is 437.

8 solutions

Mehul Arora
May 5, 2015

We know that For Integers $a,b$ ,

$LCM(a,b)\times HCF(a,b) = |a\times b|$

Plugging in Values, We get, $\dfrac {7429 \times 23}{391}=x$

Hence, The answer is 437 $\huge\ddot\smile$

Correction: If you're stating for all integers $a,b$ , it should be $|a\times b|$ in RHS of the identity you stated so that even the negative integers $a,b$ are accounted for.

Advice: It'd be better if you posted a proof of this too. Hint: Fundamental Theorem of Arithmetic and definition of GCD and LCM.

Prasun Biswas - 6 years, 1 month ago

Would this count as a proof?

Since we know the GCD of 391 and $x$ is 23, then $x = 23n$ (a multiple of 23).

Since the LCM of 391 and $23n$ is 7429, dividing 7429 by 391 would give us our $n$ value $(n=19)$ . Then we multiply 23 by $n$ to get $(23)(19)=\boxed{437}$ .

Feathery Studio - 6 years, 1 month ago

Well, Yes. It will count as a proof according to me. But, @Prasun Biswas will have the final Say! :D

Mehul Arora - 6 years, 1 month ago

That's a nice way to get the answer. For clarity, you should mention that we have $n$ such that $\gcd\left(n,\dfrac{391}{23}\right)=1$ . The rest of your method is trivial.

Anyway, this is not a general proof. This only solves the posed problem. It doesn't prove the general identity. By proof, I meant a proof of the identity Mehul stated, which generalizes the problem for all integers $a,b$ .

Prasun Biswas - 6 years, 1 month ago

How about this?

$GCF(a, b)=n$

$LCM(a, b) = x$

Therefore $b=mn$ because $b$ must be a multiple of $n$ , and $m$ would be the other factor, and $a=nt$ , where $t$ would be the other factor.

The LCM of the two integers must have these 3 integers as its factors: $n$ , $m$ , and $t$ . When we multiply the two integers, we get $mn^{2}t$ . Now, I never that $n^2$ had to be a factor, so we can divide the previously stated expression by $n$ to get $mnt = am$ . The reason for doing this is that we have an unnecessary factor, and there is still one of that factor left, so the two integers would still have it as their multiple. Therefore, $am=x$ , and when we multiply both sides by n, we get $amn=nx$ , or $ab=nx$ , thus proving that $GCF(a, b)\times LCM(a, b) = a\times b$ .

Feathery Studio - 6 years, 1 month ago

Quintessence Anx
May 12, 2015

We are given:

$gcd(391, x) = 23 \\ lcm(391,x) = 7429$

From the lcm we have: $\frac{7429}{391} = 19$

What to notice:

The gcd of 391 and a number is a prime number, 23.
The product of 391 and another prime number, 19, is the lcm 7429.

The following properties are vital:

Both 23 and 19 are prime
The fact that lcm limits to the least common and...
...the fact that gcd limits to the greatest common .

Basically: the least and greatest common multiple/divisor are both prime numbers, so $x$ must be the product of these prime numbers, so $23 * 19 = 437$ .

A Former Brilliant Member
Jul 24, 2017

Note that

$gcd(M,N) \times lcm(M,N)=M \times N$

Hence,

$23(7429)=391x$

$x=$ $\color{#D61F06}\large \boxed{437}$

Dustin Moriarty
May 22, 2015

Question:

$GCD[391,x]=23$

$LCM\left[391,x\right]=7429$

Convert LCM into an equation using GCD.

$\frac{391x}{GCD\left[391,x\right]}=7429$

Substitute $GCD[391,x]$ for 23. Note that $391=17\times23$ and $7429=17\times19\times23$ .

$\frac{391x}{23}=7429$

$\boxed{x=437}$

Wildan Bagus Wicaksono
Jun 30, 2017

$LCM(a, b) \times GCD(a, b) = ab$

$7429 \times 23 = 391 \times x$

$\frac{7429 \times 23}{391}$ $= \large x$

$19 \times 23 = 437$

So, $\large x$ is 437

Samraat Choudhury
May 7, 2015

(7429*23)/391=x

Moderator note:

Why? When typing a solution, try to put yourself in the shoes of other people and see whether they can understand your solution.

Rohan Rao
May 6, 2015

GCD X LCM = PRODUCT OF THE 2 INTEGERS HENCE. 391 x X = 23 x 7429 hence x = 23 x 7429 / 391 x = 437

You can check out the Fundamental Theorem of arithmetic for More Details to the Concept of HCF,LCM and relation to the Numbers

Ashish Gupta
May 5, 2015

For two numbers a and b, Lcm x Hcf = a x b There's a formula for 3, 4 and in general n numbers.

GCD vs LCM

The answer is 437.

8 solutions

Moderator note:

0 pending reports