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

346 questions
13 views

### Finding all pairs of integers satisfying gcd(a,b) = 6 and lcm(a,b)=540

Given that $$a\cdot b=gcd(a,b)\cdot lcm(a,b)$$ How can we find all the integer solutions $(a,b)$ if $gcd(a,b)=6$ and $lcm(a,b)=540$? The first thing I did was factorizing using the fundamental ...
29 views

### LCM of even and odd integers

Is the least common multiple of an even $2k$ and odd number $2l+1$ always the product of both numbers $2k(2l+1)$ ? And also is the least common multiples of two odd numbers the product of both odd ...
25 views

### Find $\theta\in [0,2\pi]$ if $\theta = \frac{n\pi}{2}$ and $\theta = \frac{2m\pi}{5} + \frac{\pi}{10}$, where $n,m$ are integers

$\theta = \dfrac{n\pi}{2}$ and $\theta = \dfrac{2m\pi}{5} + \dfrac{\pi}{10}$ where $n ,m \in \mathbb Z$. Find $\theta\in [0,2\pi]$. It can be solved by hit and try, of course but is there any ...
59 views

### How many marbles?

One dozen of big marbles and small marbles is 132 gram. If one big marbles is 3 gram heavier than one small marbles, then specify the possibilities of how many are the big marbles and the small ...
189 views

### Can we invert these analogous “Dirichlet” series for GCD / LCM convolution?

We know that $\sum_{ab = n} f(a) g(b)$ is multiplicative in $n$ if $f, g$ are but what about $\sum_{\text{lcm}(a,b) = n} f(a) g(b)$. It associates because of associativity of $\text{lcm}$. Thanks @...
41 views

### Lower Bound on the Sum of Reciprocal of LCM

While reading online, I encountered this post which the author claims that \begin{align} S(N, 1):=\sum_{1\le i, j \le N} \frac{1}{\text{lcm}(i, j)} \geq 3H_N-2 \end{align} and $S(N, 1) \geq H_N^2$ ...
21 views

### $\gcd$ and $\text{lcm}$ of more than $2$ positive integers [duplicate]

For any two positive integers ${n_1,n_2}$, the relationship between their greatest common divisor and their least common multiple is given by $$\text{lcm}(n_1,n_2)=\frac{n_1 n_2}{\gcd(n_1,n_2)}$$ If ...
93 views

65 views

### Problem with least common multiple and greatest common divisor [closed]

Let $n \ge 2$ be an integer and let $a_1,a_2,...,a_n$ be $n$ distinct positive integers. For all pairs $(i,j)$ such that $i \ne j$ numbers $gcd(a_i,a_j)$ and $lcm(a_i,a_j)$ are written on the ...
74 views

41 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 ...
92 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 ...
134 views

109 views

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) \ ... 0answers 19 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 ... 1answer 80 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 ... 0answers 55 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$mbe a ... 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}\... 0answers 51 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\... 0answers 36 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 ... 0answers 51 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 ... 0answers 36 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:$$... 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 ... 0answers 38 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 ... 3answers 33 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? 0answers 66 views ### Any faster algorithm to find the least common multiple? To find the least common multiple ofa,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 ... 0answers 72 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. ... 0answers 59 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 ... 1answer 124 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 ... 1answer 40 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$... 1answer 35 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 ... 1answer 84 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$...
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 ...
### 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!}{\...