Stack Exchange Network

Stack Exchange network consists of 174 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Questions tagged [least-common-multiple]

For questions about the least common multiple of a collection of numbers (or more generally, elements of a commutative ring).

3
votes
3answers
107 views

Numerical example for $\gcd(a,b)=\prod p_i^{\min(a_i,b_i)}$

I'm actually having trouble understanding the above corollary. Can anyone please provide a numerical example of that corollary? Thank You So Very Much in advance. Corollary If $a=\prod p_i^{a_i}$ ...
3
votes
1answer
48 views

Find divisors $n_i$ of $a_i$, mutualy coprime, with $\prod n_i=\operatorname{lcm}(a_i)$

We are given $k$ positive integers $a_i$, and want as many positive integers $n_i$ each dividing the respective $a_i$, with the $n_i$ mutually coprime, and the product of the $n_i$ equal to to the ...
0
votes
1answer
19 views

Fastest way to find LCM and HCF of multiple numbers?

Is there any shortcut approach to find LCM and HCF of multiple numbers apart from prime factorization and hit and trial method (writing down all the multiples of respective numbers and comparing them ...
1
vote
1answer
33 views

Let m be the least common multiple of a,b and c be another common multiple. Prove that m divides c. [duplicate]

I have tried to solve the problem. I have started by assigning m=(ab)/d, where d is the greatest common divisor of a and b. Then I set up c = aq. That is where I am stuck. I am really not sure what to ...
0
votes
0answers
32 views

Is it true that if $x \ge 2000$, then the least common multiple of $\{1,2,3,\dots,x\}$ is greater than $2.499^x$

As I was reading through Jitsuro Nagura's proof, I am seeing that he showed for $x \ge 2000$: $$\psi(x) \ge 0.916x$$ where $\psi(x) = \sum\limits_{m=1}^{\infty}\vartheta(\sqrt[m]{x})$ and where $\...
0
votes
1answer
30 views

$S_3\oplus S_3$ has an element of order $4,6,9$ or $18$.

$S_3\oplus S_3$ has an element of order $4,6,9$ or $18$. $\oplus$ is the direct sum. Its order is $36$ so by sylow theorem it has subgroups of order $4$ and $9$. Also order of a permutation is the ...
0
votes
4answers
49 views

LCM and GCD polynomial relationship

I need some help with constructing a proof for the following statement,$ \frac{P_1 P_2}{hcf(m,n)} = lcm(P_1,P_2)$ where $P_1$ and $P_2$ are polynomials with real coefficients. I know how to do the ...
-1
votes
2answers
61 views

Relation between GCD and LCM [duplicate]

When I was learning about GCD and LCM I found this relation somewhere. But I didn't get proof for this relation. $$\frac{\gcd(a,b,c)^2}{\gcd(a,b)*\gcd(b,c)*\gcd(c,a)}=\frac{\operatorname{lcm}(a,b,c)^2}...
1
vote
2answers
22 views

Find minimum integer $n$ and $m$ such that $36^n = 16^m, n \in \mathbb{Z}, m \in \mathbb{Z}$?

How would I go about finding the minimum $n$ and $m$ such that $36^n = 16^m, n \in \mathbb{Z}, m \in \mathbb{Z}$? The practical reason for this is that I would like to find the minimum number of hex ...
0
votes
0answers
17 views

Lcm, hcf simple question

Jack needs to pack 48 pencils, 24 pens and 20 ballpoints in boxes. All boxes are identical. What is the largest number of boxes that can be packed? And what will be the number of stationary items in ...
4
votes
0answers
41 views

If $1\le a_1<\cdots<a_n\le 2n$ satisfy $\operatorname{lcm}(a_i,a_j)>2n$ for $i\ne j$, is $a_i>\frac{2n}{3}$ for all $i$?

If integers $1\le a_1<\cdots<a_n\le 2n$ satisfy $\operatorname{lcm}(a_i,a_j)>2n$ for $i\ne j$, is it true that $a_i>\frac{2n}{3}$ for all $i$? My attempt: Suppose that $i<j$, then $\...
1
vote
1answer
37 views

Is this proof acceptable?

Proposition: If $g$ is any common factor of $m$ and $n$ where $g,m,n \in$ $\mathbb N$ then $g \mid lcm(m,n)$ Proof: As $m \mid lcm(m,n)$ and $n \mid lcm(m,n)$ by transitivity of divisibility $g \...
0
votes
0answers
37 views

Using Least common multiple to establish a lower bound for a ratio of primorials

Let $x\#$ be the primorial for $x$. Let $\text{lcm}(x)$ be the least common multiple of $\{1, 2, 3, \dots, x\}$. It occurs to me that for $x \ge 4$, it is straight forward to find a lower bound of $\...
0
votes
0answers
39 views

Specific question on lcm and gcd of rings.

I can't prove this statement: Let $a_1,a_2,...,a_n$ and $b_1,b_2,...,b_n$ be non zero elements of an integral domain $R$ such that $a_1b_1=a_2b_2=\cdots=a_nb_n=x$ If $gcd(ra_1,ra_2,...,ra_n)$ exists ...
2
votes
0answers
55 views

Using least common multiple to prove there exists a prime between $2x$ and $3x$

Let $\text{lcm}(x)$ be the least common multiple of $\{1,2,3,\dots, x\}$. Hanson showed that $\text{lcm}(x) < 3^x$ I'm wondering if the following argument is valid for showing that there is ...
-1
votes
1answer
39 views

Show that $\alpha = (1 2 3)(2 3 4)(5 6 7)(7 8 9 10)$ has order $10$ in $S_n$ $(n\geq10)$.

So I have done problem #13 in section 7.5 of t book Abstract Algebra: An Intorduction, 3rd Edition by Thomas W. Hungerford (ISBN: 978-1-1115696-2-4). multiple times over now, but I still get the order ...
0
votes
1answer
26 views

If $g = gcd(a,b)$ prove (a,b)=(g). Furthermore, if $k = lcm(a,b)$ prove that $(a)\cap(b) = (k)$

$a,b \in \mathbb{Z}$. $(a,b),\hspace{0.4mm}(g)$ and $(k)$ are principle ideals I'm new to this kind of problems, so I don't even know how to start it. Some help would be appreciated.
1
vote
1answer
22 views

Product of gcd and lcm for multivariate polynomials

This maybe trivial but I don't know how to conclude the proof. Consider the ring of multivariate polynomials with field coefficients $K[X_1,\dots,X_n]$. Take two nonzero polynomials $F$ and $G$ and ...
1
vote
1answer
88 views

Upper bound for a ratio of two least common multiples

Let $\text{lcm}(x)$ be the least common multiple of $\{1,2,3,\dots,x\}$ Let $x\#$ be the the primorial for $x$. It occurs to me that for $x \ge 10$: $$\frac{\text{lcm}(x^2+x)}{\text{lcm}(x^2)} < ...
4
votes
3answers
57 views

Connection between GCD and LCM of two numbers

These two exercises I encountered recently seem to develop some type of connection between GCD and LCM I can't quite figure out. Exercise 1: Find all the numbers $x$ and $y$ such that: $a) \ ...
0
votes
0answers
18 views

Coprimality of elements of set of numbers with maximum LCM and given fixed sum.

If we have to find a set $S$ such that it has a given sum $n$ and it's LCM is maximum, then it is intuitive that the elements of the set should be coprime. However I can't find any formal proof. I ...
2
votes
1answer
77 views

Is this approach valid for using least common multiple to establish Bertrand's postulate

Let $\text{lcm}(x)$ be the least common multiple of $\{1,2,3,\dots,x\}$. Denis Hanson showed that $\text{lcm}(x) < 3^x$ and M. Nair showed that $\text{lcm}(x) > 2^x$. Neither used Bertrand's ...
0
votes
0answers
47 views

Prove $\frac{ab}{m} = \gcd(a,b)$ when $m=\operatorname{lcm}(a,b)$, for all natural numbers $a$ and $b$.

Prove $\frac{ab}{m} = \gcd(a,b)$ when $m= \operatorname{lcm}(a,b)$ for all natural numbers $a$ and $b$. I should be able to prove this using only basic rules of $\gcd$ and lcm. I instead let $m$ be a ...
3
votes
1answer
276 views

Reasoning about factorials: is this equation correct?

I was playing around with the möbius inversion formula and factorials and I came up with an equation that I found interesting: $$\prod_{i\ge2}\left\lfloor\frac{x}{i}\right\rfloor! = \prod_{i \ge 2}\...
0
votes
0answers
48 views

Prove that, $\textrm{LCM}(\textrm{GCD}(m,x),\textrm{GCD}(n,x)) = \textrm{GCD}(\textrm{LCM}(m,n),x)$

I want to show that for $m,n,x \in \mathbb{Z}$, \begin{align*} \textrm{LCM}\left(\textrm{GCD}\left(m,x\right),\textrm{GCD}\left(n,x\right)\right) = \textrm{GCD}\left(\textrm{LCM}\left(m,n\right),x\...
0
votes
0answers
34 views

In which rings are gcd and lcm defined?

Greatest common divisor and least common multiple exist for elements of integers, univariate polynomial ring and multivariate polynomial rings. So in most general manner, in which rings do gcd and ...
0
votes
0answers
47 views

Reasoning with factorials and the Möbius inversion — does this make sense?

It is well known that a factorial can restated as a product of least common multiples: $$\log(x!) = \sum_{m=1}^{\infty}\psi\left(\frac{x}{m}\right)$$ Using Möbius inversion formula, it occurs to me ...
0
votes
0answers
32 views

I'm not clear why the reasoning that M. Nair used is valid in one of his classic proofs.

I am reading through M. Nair's On Chebyshev-Type Inequalities for Primes and I am unclear on why one of his key steps is valid. Let $d_n$ be the least common multiple of $1,2,\dots,n$ such that: $$...
0
votes
1answer
48 views

Question about integration by parts as used in a previous answer on MSE.

I was reading through this answer to a question about the lower bound of a least common multiple. The question is about showing that: $$\text{lcm}(1,2,\dots,n) > 2^n$$ I was not clear on one ...
0
votes
0answers
33 views

Need help with the first step in Theorem 1 of Nair's classic paper on Least Common Multiple

I am now reading through M. Nair's classic paper on the lower bound of the least common multiple. The first step in Theorem 1 is not obvious to me. I would greatly appreciate it if someone could ...
0
votes
3answers
32 views

How to yield lcm between several numbers?

How to find LCM between several numbers? For example, how to find LCM between the numbers 7, 24, 3 and 10?
0
votes
0answers
55 views

Any faster algorithm to find the least common multiple?

To find the least common multiple of $a,b$, call it $\operatorname{lcm}(a,b)$, divide there product by there greatest common divisor. However, finding the gcd requires at most $\log n$ time. I am ...
3
votes
0answers
67 views

Still unclear why Hanson's proof that $\text{lcm}(1,…,n)<3^n$ is not sufficient to resolve Legendre's Conjecture.

This is my second question on this topic. In my first question, mathlove quickly found the mistake. Correcting for the previous mistake, there is still a mistake in my analysis but I can't find it. ...
0
votes
0answers
57 views

Reasoning about least common multiples using ratios of factorials.

Let $\text{lcm}(n)$ be the least common multiple of $(1, 2, \dots, \lfloor n\rfloor)$. As I understand it, there is a well-known relationship between a factorial and the ratio of least common ...
6
votes
1answer
118 views

Why isn't Legendre's Conjecture resolved by the work done by Nair and Hanson in relation to Least Common Multiples?

I recently discovered the work done by Hanson and Nair. As I worked through Hanson's proof, an argument occurred to me regarding Legendre's Conjecture. Clearly, my argument is wrong. It is too ...
0
votes
1answer
38 views

What is the definition of the least common multiple of elements of a group rather than their orders?

In an answer to my question here Relationship between order of $(x,y)$ in $G \times G'$ and order of disjoint permutations, which both involve LCMs?, it is said that Let $G$ be a group, $a\in G$...
1
vote
1answer
33 views

Trying to understand a lemma in a math paper on LCM

Through Wikipedia, I discovered the following Arxiv.org article on Least Common Multiple. I have not seen the notation referenced and I am not clear how $\gamma$ is defined since it stated to be a ...
3
votes
1answer
83 views

Not clear in one step in the inequality for the proof LCM$(1,2,\dots,n) < 3^n$

I believe that I am following Hanson's proof up until this point (page 36): $$C(n) < \dfrac{(en)^{k-1+1/(a_{k+1}+1)}w^n}{(a_1)^{(a_1-1)/a_1}(a_2)^{(a_2-1)/a_2}\dots(a_m)^{(a_k-1)/a_k}}$$ where $...
1
vote
0answers
76 views

Did I find a mistake in a classic proof? If not, could someone help me understand?

I am working through Denis Hanson's proof that LCM$(1,2,3,\dots,n) < 3^n$ To be clear, the mistake is minor and does not affect the result achieved. Still, I was surprised. Here's what I believe ...
1
vote
1answer
64 views

Question regarding $C(n)$ and $B(n)$ in Hanson's proof that $\prod\limits_{p^a \le n} p < 3^n$

In Denis Hanson's proof, he defines two terms: (1) $B(n)$: which is the Least Common Multiple of $\{1,2,\dots,n\}$ $$B(n) = \prod\limits_{p^a \le n}p$$ (2) $C(n)$: an integer $$C(n) = \dfrac{n!}{\...
2
votes
2answers
67 views

Derive the identity elements of lcm and gcd

Find the identity element of the binary operations $*,*'$ on $\mathbb{N}$ given by $a*b = lcm(a,b)$ and $a*'b = \gcd(a,b)$, where $\mathbb{N}=\{1,2,3...\}$ I know the identity element for lcm is $1$ ...
4
votes
2answers
72 views

How to find GCD and LCM of a factorial and a large number?

So I was given this question: $n = 2^{16}3^{19}17^{12}$ Find $\gcd(n, 40!)$ and $\operatorname{lcm}(n, 40!)$. I understand how to find the GCD and LCM when its two really large numbers (given ...
-1
votes
3answers
86 views

What will be 6th number in this series? [closed]

An ascending series of numbers satisfied the following conditions When divided by 3, 4, 5 and 6 the number leaves the remainder of 2. When divided by 11, The number leaves no reminder. The 6th ...
1
vote
1answer
37 views

Is there an concept of Least Common Odd Multiple?

Background I come into a problem where I need to define the least common Odd multiple. Say I have two integer $a,b \in \mathbb{N}$, I want to define $c$ such that $a|c$ and $b|c$ in an oddly number ...
0
votes
0answers
58 views

About the mutinous numbers

This is just repost of a question that was raised in an answer here. For any positive integer $m>0$, let $$ q_{n}(m):=\frac{ \text{lcm}(n+1,n+2,..,n+m)}{m{n+m\choose m}}.$$ $ q_{n}(m)$ is an ...
0
votes
1answer
30 views

Which integers have inverses with respect to lcm operator, a*b=lcm (a,b) [closed]

I know that the identity of this operator is 1, but am not sure about the inverse.
-2
votes
3answers
41 views

Find the value of a if A divisable by 3 [closed]

$A=0.\overline{a}+0.\overline{aa}+0.\overline{aaa}\: \\ \text{If A is divisable by 3, }\: \text{find the value of} \: a\: $
1
vote
1answer
39 views

Is this a simple LCM or Ad hoc problem or modular arithmetic problem?

I've got a Kindergarten problem, which is to find smallest number which will be satisfied following condition: If we divide that number with $4, 6$ and $10$ then $2, 4$ and $8$ will be remainder ...
0
votes
0answers
27 views

Number Theory: Divisibilty

Q: Prove that if a and b are positive integers satisfying (a,b)=[a,b}, then a=b. My approach (with ans): (a,b) means gcd, and I let g=(a,b) since g is the gcd, then I get these two: g|a and g|b, ...
2
votes
1answer
166 views

Least Common Multiple and the product of a sequence of consecutive integers

Let $x>0, n>0$ be integers. Let LCM$(x+1, x+2, \dots, x+n)$ be the least common multiple of $x+1, x+2, \dots, x+n$. Let $v_p(u)$ be the highest power of $p$ that divides $u$. It seems to me ...