Questions tagged [gcd-and-lcm]

Greatest common divisor 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 those questions.

316 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
10
votes
0answers
198 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
219 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
152 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
421 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
155 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
197 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
1answer
44 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
286 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
510 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
106 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
169 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
92 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
78 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
350 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
48 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
117 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
287 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
95 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
142 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
606 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
70 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
1answer
137 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
102 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
43 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
52 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
376 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
44 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
129 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
102 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) ...
2
votes
0answers
58 views

Are there any other squares $n^2$ for which $\gcd(n^2, \sigma(n^2)) = 2n^2 - \sigma(n^2)$?

Let $\sigma(x)$ denote the sum of the divisors of the positive integer $x$. Denote the deficiency of $x$ by $$D(x)=2x-\sigma(x).$$ I am interested in solutions to the equation $$\gcd(n^2, \sigma(n^2)...
2
votes
0answers
38 views

When the algebraic degree of the ring containing the GCD is not obvious

Most of the time we subconsciously determine the ring a GCD computation is to take place in purely from context. For example, $\gcd(28, 63)$ is clearly a GCD computation in $\textbf Z$, while $\gcd(28,...
2
votes
0answers
86 views

Least Common Multiple and exponential constant $e$

$$S(n)=S(n-1)+\operatorname{lcm}[n,S(n-1)]-1$$ Given the initial $S(1)=1$. Where $n\ge2$ and $\operatorname{lcm}$ is the Least Common Multiple As an example the $\operatorname{lcm}(6,8)=24$. Let ...