Questions tagged [gcd-and-lcm]

The concepts of *greatest common divisor* (which is also known as *Highest Common Factor*) and *least common multiple* are closely related notions in the integers, and also make sense in certain other rings. The tag is intended to encompass all questions related to these notions.

321 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
10
votes
0answers
200 views

$\gcd(p_{n-1}, \ n^5 - n^3 + n^2 - n + 1) = 1$ where $p_n = n$th prime.

How can I prove in general that, for all $n\geq 2$: $$ \gcd(p_{n-1}, \ n^5 - n^3 + n^2 - n + 1) = 1 $$ Seems to always be true: ...
8
votes
0answers
221 views

The Greatest Common Divisor of All Numbers of the Form $n^a-n^b$

For fixed nonnegative integers $a$ and $b$ such that $a>b$, let $$g(a,b):=\underset{n\in\mathbb{Z}}{\gcd}\,\left(n^a-n^b\right)\,.$$ Here, $0^0$ is defined to be $1$. (Technically, we can also ...
8
votes
0answers
160 views

Generalisation of $\gcd\left(\frac{a^n-b^n}{a-b},a-b\right)=\gcd(n\gcd(a,b)^{n-1},a-b)$ to $\gcd\left(\frac{a^n-b^n}{a-b},a^m-b^m\right)$?

We have the identity $$\gcd\left(\frac{a^n-b^n}{a-b},a-b\right)=\gcd(n\gcd(a,b)^{n-1},a-b).$$ (see here) This appears to be a quite useful result with various applications. I wonder whether there is ...
7
votes
0answers
423 views

A combinatoric $gcd$ problem

Let $Q(L)$ be the number of pairs of numbers $m , n$ such that $gcd(m,n) = 1$ and $m$ and $n$ are of different pairity, where $m$ is even and $n$ is odd, and $m^2 + n^2$ $\le$ $ L$. $$Q(L) = \sum_{...
6
votes
0answers
157 views

The GCD of a Univariate Integer-Valued Polynomial over a Set

Let $\mathcal{I}[X]$ denote the subring of $\mathbb{Q}[X]$ consisting of all integer-valued polynomials (i.e., $f(X)\in \mathbb{Q}[X]$ such that $f(k)\in\mathbb{Z}$ for all $k\in\mathbb{Z}$). For $f(...
6
votes
0answers
198 views

From $\prod_{d\mid n}d=n^{\sigma_0(n)/2}$ to $n!=\operatorname{lcm}(1,\ldots,n)^{e(n)}$, where $\sigma_0(n)$ is the number of divisors

We know that $$\prod_{d\mid n}d=n^{\sigma_{0}(n)/2}$$ for every integer $n\geq 1$, where $\sigma_{0}(n)$ is the number of positive divisors of $n$, see for example [1] (exercise 10, page 47). And for ...
5
votes
0answers
101 views

Conjecture about primes and the greatest common divisor

Conjecture: Given $m,n\in\mathbb N^+$, one odd and one even, there are two primes $p,q$ such that $|mp-nq|=\gcd(m,n)$. I hope MSE can determine its validity. From time to time, when testing my ...
4
votes
0answers
31 views

Subgroup of multiples of $m$, $m$-torsion and $p$-subgroup of $\mathbb{Z}_n$

Disclaimer: this terminology might be different from what you're used to and this is why I'm writing down some definitions first. Let $A$ be an abelian group, $m \in \mathbb{N}^* := \mathbb{N} \...
4
votes
1answer
48 views

Infinite set of positive integers - choose infinitely many to be relative primes or not

Given a set of infinitely many positive integers. Is it always possible to find a subset of this set which contains infinitely many numbers such that any two numbers in this subset are relative primes ...
4
votes
0answers
43 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 $\...
4
votes
1answer
287 views

Is it possible to simplify this expression even further?

(Preamble: This question is tangentially related to this earlier one.) Let $\sigma(z)$ denote the sum of the divisors of $z \in \mathbb{N}$, the set of positive integers. Denote the deficiency of $...
4
votes
0answers
96 views

Labelling the edges of a graph

Let $G$ be a connected graph with $m$ edges. Prove that the edges can be labelled with the positive integers $1,2,…,m$ such that for each vertex with degree at least two, the greatest common divisors ...
4
votes
0answers
511 views

LCM of binomial coefficients and related functions

I know about the following identity: $$\displaystyle \text{lcm} \left( {n \choose 0}, {n \choose 1}, ... {n \choose n} \right) = \frac{\text{lcm}(1, 2, ... n+1)}{n+1}$$ 1) Is there any method to find $...
4
votes
1answer
122 views

When is $(12x+5)/(12y+2)$ not in lowest terms?

I am struggling to solve this problem and would appreciate any help: When is $\frac{12x+5}{12y+2}$ NOT in lowest terms? ($x$,$y$ are nonnegative integers) I have found that it is not in lowest ...
3
votes
0answers
82 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. ...
3
votes
0answers
76 views

Find all functions satisfying certain requirements

The requirements are: $f(x, y) = f(y, x)$ $f(x, x) = x$ $f(x, y) = f(x, x + y)$ f: $\mathbb{N}^2 \rightarrow \mathbb{N}$ I think $\gcd(x, y)$ works, but haven't found any other solutions nor have I ...
3
votes
0answers
112 views

GCD and the cycle decomposition of a permutation

Take a permutation $\sigma \in \mathcal{S}_n$. Its cycle decomposition is the (essentially) unique decomposition in disjoint cycles : $\sigma = c_1 c_2 \cdots c_k$. Write $p_i$ the length of each ...
3
votes
1answer
55 views

If $a\mid b$ and $a>0$ then $(a,b)=a$

Now let $d=(a,b)$. So $d=ax+by$. Since $a\mid b$ , so we have $aq=b. q \in \mathbb{Z}$. so we have $d=ax+aqy$. since a divides R.H.S , so it must divide L.H.S. So $a\mid d$ Also $d\mid a$ as its GCD ...
3
votes
0answers
176 views

How might I prove that LCM$(m) \geq 2^m$?

Denoting by LCM$(m)$ the lowest common multiple of the first $m$ numbers, can anyone suggest a way in which I might prove that, for $m \geq 7$, $$ \text{LCM}(m) \geq 2^m $$ I believe that a proof of ...
3
votes
0answers
121 views

Proof verification: $\gcd(a,n)=1$ iff $ab\equiv 1\pmod{n}$ for some integer $b$.

Proof verification: $\gcd(a,n)=1$ iff $ab\equiv 1\pmod{n}$ for some integer $b$. Can someone please verify whether my proof is logically correct? :) Proof: Let $\gcd(a,n)=1$. Then there exist ...
3
votes
0answers
41 views

Algorithm to check if first-order polynomial has any roots in region of the integers

I'm trying to implement a C++ function to check if an object that refers to a tensor has the so-called problem of aliasing. This seems to lead to the following mathematical problem: Assume you are ...
3
votes
0answers
80 views

Smallest approximate common multiples

$\newcommand{\l}{\operatorname{lcm}} \newcommand{\la}{\operatorname{lacm}} $ $$\l(\,\overbrace{101,\,103,\,107,\,109}^{\large\text{consecutive primes}}\,) =121{,}330{,}190 > 100{,}000{,}000.$$ $$ ...
3
votes
1answer
1k views

How do I solve this problem involving the LCM of 200 numbers?

Evaluate $x$ if: $$x\cdot\operatorname{lcm}{(102\ldots 200)}=\operatorname{lcm}{(1,2,\ldots 200)}$$ Here's what I have so far, LEMMA 1: In any set of $n$ consecutive positive integers, there must be ...
3
votes
0answers
373 views

Using Euclidean Algorithm to find GCD of polynomials in $\mathbb{Q}[x]$

I had to find the $\gcd$ of the following polynomials in $\mathbb{Q}[x]$ using the Euclidean algorithm, and I wanted to check that I had done so correctly, since my notes on the subject from class are ...
3
votes
0answers
48 views

Assume $d\mid n$ and $\gcd(a,d)=1$. Let $t$ be the product of prime numbers that divide $n$, but don’t divide $a$. Show: $\gcd(a+td,n)=1$.

Let $d,n\in\mathbb Z_{>0}$ with $d\mid n$. Let $a\in\mathbb Z$ such that $\gcd(a,d)=1$. Let $t$ be the product of prime numbers that divide $n$, but don’t divide $a$. Show: $\gcd(a+td,n)=1$. ...
3
votes
0answers
72 views

Distribution and expected value of a random infinite series $\sum_{n \geq 1} \frac{1}{(\text{lcm} (n,r_n))^2}$

Can we find the distribution and/or expected value of $$S=\sum_{n \geq 1} \frac{1}{(\text{lcm} (n,r_n))^2}$$ where $r_n$ is a uniformly distributed random integer, $r_n \in [1,n]$ and $\text{lcm}$...
3
votes
0answers
50 views

$\sup\left(\frac{\log(\mbox{ lcm }(1,2,\ldots,k))}{k}\right)$ for $k\in \Bbb{Z}, k>1$

In a previous question Asymptotic growth of l.c.m. of all integers below $k$, it was noted that using the Prime Number Theorem you can prove that $$ \log(\mbox{ lcm }(1,2,\ldots,k)) =k+\mbox{ o}(k)$$ ...
3
votes
0answers
61 views

Exploring congruences and identities involving Mersenne primes and the terms of Lucas-Lehmer test

When I was exploring congruences$\dagger$ involving the terms $S_k$ defined in Lucas-Lehmer test (this reference is the Wikipedia, but the main reference is Crandall and Pomerance, Prime Numbers: A ...
3
votes
0answers
118 views

Finding a summation involving gcd

I am trying to evaluate the following sum: $$b\sum_{i=a}^b\frac{i}{\gcd(i,b)}$$ I have solved the problem if $a=1$ but I am clueless for the case when $a$ is not $1$. For $a=1$, I used the fact that $...
3
votes
0answers
297 views

Greatest Common Divisors in columns and rows of Pascal Triangle

Let $n$ and $k$ be integers such that $n\ge3$ and $k\ge 2$ and $g(n)$ is the prime gap where $n$ lies $$k\le g(n)+2\implies \gcd\left(\binom{n+j}{k} , j\in \{ 1,k-1 \} \right)\gt1$$ $\binom{n+j}{k}...
3
votes
0answers
98 views

How can I show that $x \equiv b^{u} \pmod m$ is always a solution to $x^{k} \equiv \pmod m$, even if $\gcd(b,m) \gt 1$?

How can I show that $x \equiv b^{u} \pmod m$ is always a solution to $x^{k} \equiv \pmod m$, even if $\gcd(b,m) \gt 1$? Our method for solving something like $x^k \equiv b\pmod m$ is first to find ...
3
votes
0answers
144 views

$\gcd(f(x),g(x))\neq 1$ iff they share a root in some extension field

Let $f(x),g(x)\in F[x]$ . Then to prove that $(f,g)\neq 1$ iff there is a field $E$ containing both $F$ and a common root of $f(x)\ \ and\ \ g(x)$ Now if $$(f(x),g(x))=d(x)\neq ...
3
votes
1answer
612 views

LCM of Fibonacci numbers

$\newcommand{\lcm}{\operatorname{lcm}}$There is a nice property of Fibonacci numbers which says that: $$\gcd(F_{a_1}, \ldots, F_{a_n}) = F_{\gcd(a_1, \ldots, a_n)}$$ I am curious is there anything ...
3
votes
2answers
71 views

Upper bound for $\gcd(a,b)$ if $\frac{a+1}{b}+\frac{b+1}{a}\in\Bbb{N}$

Suppose that $a,b$ are two positive integers so that $\frac{a+1}{b}+\frac{b+1}{a}$ is also a positive integer.Find the best upper bound for $\gcd(a,b)$. My work: $\frac{a+1}{b}+\frac{b+1}{a}=\frac{...
2
votes
0answers
45 views

partition that maximizes lcm

Let $n$ be a natural number. How can I find a partition of $n$ such that its least common multiple is maximized? In other words, how can I find $a_1, a_2, \cdots a_m \in \mathbb{N}$ such that $$a_1 + ...
2
votes
1answer
27 views

Number of elements of a certain order of a direct product of finite cyclic groups.

Let $G_1$ and $G_2$ be cyclic finite groups. Suppose I wanted to find the number of elements in $G_1 \times G_2$ of order k. How would I do that? I've tried using the fact that if $g_1 \in G_1$ and $...
2
votes
1answer
140 views

Factor $x^p-y^p$

I would like to factor the polynomial $p(x,y)=x^p-y^p$ for some small prime $p$ $(p=3,5,\text{or } 7)$ and for all values of $p(x,y)$ with $1 < x < 1000$ and $1 < y < x$. There is a ...
2
votes
0answers
105 views

Condition for the sum of two fractions to be irreducible

Let $\frac{a}{b}$ and $\frac{e}{f}$ be two rationals where all parameters are positive integers and are in their lowest terms and let $\gcd(b,f) = g$. As an intermediate step in one of the problems I ...
2
votes
1answer
30 views

How to complete a primitive vector to a unimodular matrix

I would like to understand the following relation between unimodular matrices and its columns in some sense: if $x$ is a primitive vector (that is to say an integer column of $n$ rows whose entries ...
2
votes
0answers
44 views

Trying to count the number of integers $x \le n$ where gcd$\left(x(x+2),30\right)=1$ using the möbius function

Let: $x>0, n >0$ be integers gcd$(s,t)$ be the greatest common divisor of $s$ and $t$ $\mu(x)$ be the möbius function For $x \le n$ and gcd$(x,30)=1$, the count is: $$\sum_{i | 30}\left\...
2
votes
0answers
60 views

Find minimum GCD of a pair of elements in an array

Given an list of elements, I have to find the MINIMUM GCD possible between any two pairs of the array in least time complexity. Example Input list=[7,3,14,9,6] ...
2
votes
3answers
380 views

How to compute $\gcd(d^{\large 671}\! +\! 1, d^{\large 610}\! −\!1),\ d = \gcd(51^{\large 610}\! +\! 1, 51^{\large 671}\! −\!1)$

Let $(a,b)$ denote the greatest common divisor of $a$ and $b$. With $ \ d = (51^{\large 610}\! + 1,\, 51^{\large 671}\! −1)$ and $\ \ x \,=\, (d^{\large 671} + 1,\, \ d^{\large 610} −1 )$ find $\ ...
2
votes
0answers
40 views

Proof that this map is well-defined $ \phi(a \bmod{mn})= (a \bmod m, a \bmod n) $

As part of a proof of the Chinese-remainder equivalent of groups, I want to show that: $$ \phi(a \bmod mn)= (a \bmod m, a \bmod n) $$ is a well-defined map Note that $\gcd(m,n)=1$ so they are ...
2
votes
0answers
46 views

Removable singularities for rational functions with floating point coefficients

Suppose I have given a rational function $r(x)=p(x)/q(x)$ where $p$ is a degree $m$ polynomial and $q$ is a degree $n$ polynomial, both over the real numbers, and the coefficients of $p$ and $q$ are ...
2
votes
1answer
96 views

How can I find $\gcd(n^a-1,m^a-1)$?

From Prove that $\gcd(a^n - 1, a^m - 1) = a^{\gcd(n, m)} - 1$ , we have $$\gcd(a^n-1,a^m-1)=a^{\gcd(n,m)}-1$$ for every positive integers $a,n,m$. I reversed $a$ with $n,m$, and I had this question: ...
2
votes
2answers
146 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$ ...
2
votes
2answers
106 views

$\gcd(a,b)=1 \iff \gcd(a+b,ab)=1$.

If $a,b\in \mathbb{Z}$ then: $$\gcd(a,b)=1 \iff \gcd(a+b,ab)=1$$ Let $p$ be a prime number. Let $\gcd(a,b)=1$, and $p | a+b,p|ab$. $p|ab \implies p|a \ \text{or}\ p|b$. WLOG let $p|a$, then $p|a+b$...
2
votes
0answers
126 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) ...