# 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
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: ...
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 ...
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 ...
0answers
421 views

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 ...
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 ...
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$. ...
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}$...
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)$$ ...
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 ...
0answers
117 views

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 ...
0answers
142 views

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] ...
3answers
376 views

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