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).

0
votes
0answers
26 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
34 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
44 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
0answers
20 views

How to find the least common multiple with an acceleration component

Is it possible to find the least common multiple of two numbers when there is an acceleration or deceleration component. For example if I have two parabola's which intersect at a known given positive ...
-1
votes
1answer
35 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
20 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
84 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
49 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
15 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
37 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
274 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
45 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
32 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
44 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
45 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
30 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
46 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
60 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
51 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
114 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
34 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
32 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
74 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
63 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!}{\...
1
vote
2answers
54 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
64 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
82 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
34 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
57 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
23 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
35 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
143 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 ...
2
votes
0answers
117 views

Question about Least Common Multiples 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 for the set of integers $x+1, x+2, \dots, x+n$. It seems to me that: $$\text{LCM}(x+1, x+2, \dots, x+n) ...
0
votes
3answers
32 views

Suppose a,b are in group G, and commute, with orders m, n.

If $\langle a \rangle \cap \langle b \rangle=\{e\}$ then the group contains one element with least common multiple of m,n. I have constructed the element $ab$ will have order $ab=LCM(m,n)$. $$ LCM(...
0
votes
2answers
29 views

Show that $\exists a, b$ where $\gcd(a,b) = d$ and $\operatorname{lcm}(a,b) = e$ iff $d \mid e$

I want to show, given the natural numbers $d$ and $e$: $$\exists a, b \in \mathbb{N}$$ such that $$ \gcd(a, b) = d$$ and $$\operatorname{lcm}(a, b) = e$$ if and only if $$d \mid e$$ I think I have ...
0
votes
1answer
87 views

Finding minimum number of squares inside a rectangle

I have this question where I have to find the minimum number of squares (of the same dimensions) inside of a rectangle. I found that this problem has a solution where I can calculate the LCM and the ...
0
votes
1answer
46 views

A group of soldiers was asked to fall in line making rows of three.

A group of soldiers was asked to fall in line making rows of three. It was found that there was one soldier extra. Then they were asked to stand in rows of five. It was found there were left two ...
0
votes
3answers
42 views

How do I intuitively explain someone why we calculate LCM by factorization?

Let's say we're trying to find the Least Common Multiple of 36 and 18. First, we start off with the prime factorization of each number: $$ 36 --> 2 * 2 * 3 * 3 $$ $$ 18 --> 2 * 3 * 3 $$ Next, ...
1
vote
2answers
27 views
0
votes
3answers
109 views

Minimize $a+b+c+d$ given $\text{LCM}(a,b,c,d)=1000$ [closed]

Close voters: please drop a comment, what context find you missing. It is the inverse of this problem. Minimize $a+b+c+d$ given $a, b, c, d$ are distinct positive integers, and $\text{lcm}(a,b,c,d)...
4
votes
1answer
259 views

Minimize $LCM(a,b,c,d)$ given $a+b+c+d=1000$

Minimize $$LCM(a,b,c,d)$$ given $\; a, b, c, d\; $ are distinct positive integers, and $$a+b+c+d=1000$$ Any hint?
1
vote
1answer
28 views

equality of LCM

Let $a,b,c,d$ be natural numbers. I want to understand the necessary and sufficient condition on $a,b,c,d$ in order to have $[a,b] = [c,d]$ where $[m,n]$ denote the least common multiple of $m$ and $n$...
0
votes
0answers
29 views

how to compute $\gcd(\frac{a}{b},\frac{c}{d})$? [duplicate]

is there a formula for $gcd(\frac{a}{b},\frac{c}{d})?$ I'm conjeturing $gcd(\frac{a}{b},\frac{c}{d})=\frac{gcd(a,c))}{lcm(b,d)}$ but how to prove it?