Stack Exchange Network

Stack Exchange network consists of 175 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).

1
vote
2answers
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 ...
2
votes
4answers
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 ...
0
votes
1answer
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 ...
0
votes
1answer
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 ...
5
votes
2answers
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 @...
5
votes
1answer
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$ ...
0
votes
1answer
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 ...
1
vote
0answers
93 views

$\gcd \cdot \mathrm{lcm}$ for cyclic rings

A cyclic ring is a ring (or rng) whose additive group is cyclic. Two elements of a commutative ring are associates $(\sim)$ iff they divide each other. An element $d$ of a commutative ring is a $\...
0
votes
0answers
23 views

Sums with a specially defined sequence

Define $\text{negcm}(\pm x, \pm y)$ to be the least nonzero common multiple of two integers, regardless of sign. For example, $\text{negcm}(-5, 10)$ would simply be $-10$. Define $\Upsilon_{n=1}^...
1
vote
0answers
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 ...
2
votes
1answer
74 views

An isomorphism between $\mathbb Z_n \times \mathbb Z_m$ and $ \mathbb Z_{mn}$

I am reading these lecture notes and they suggest the following generalisation of a specific example for $\mathbb Z_2 \times \mathbb Z_3 \cong Z_6 $: There exists an isomorphism between $\mathbb ...
4
votes
3answers
136 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
51 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
45 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
50 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
38 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
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 ...
0
votes
4answers
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 ...
-1
votes
2answers
134 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
27 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 ...
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
39 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
42 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
40 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
63 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
45 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
27 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
109 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
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 ...
2
votes
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 ...
0
votes
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 $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
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\...
0
votes
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 ...
0
votes
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 ...
0
votes
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: $$...
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
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 ...
0
votes
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?
0
votes
0answers
66 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
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. ...
0
votes
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 ...
6
votes
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 ...
0
votes
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$...
1
vote
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 ...
3
votes
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 $...
1
vote
0answers
77 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
66 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!}{\...