Questions tagged [gcd-and-lcm]
For questions related to gcd (greatest common divisor, also known as the hcf, the highest common factor), lcm (least common multiple), and related concepts from integer and ring theory.
2,709
questions
-2
votes
0
answers
52
views
$x=\frac{(2^a)(z)-(3^b)(w)}{(2^a)-(3^b)}$ does any natural odd number value of x >1 staisfy this equation [closed]
here z and w are integer and a and b and x are natural number
i forget to mention
$w = x-(2^a)$
$z = x-(3^b)$
which make gcd(z,w)=1
i know a set of solution for x = 1 which is
w = -3
z = -8
a = 2
b = ...
2
votes
1
answer
115
views
Find the greatest common divisor of the numbers: $2^{2^{2019}}-1, 2^{2^{2021}}-4$. [duplicate]
Problem
Find the greatest common divisor of the numbers: $2^{2^{2019}}-1, 2^{2^{2021}}-4$.
My Idea
To be honest, I didn't know how to start so I let $d$ be the greatest common divisor of those numbers
...
- 748
0
votes
2
answers
51
views
How to find the largest set of coprimes between two numbers M and N?
First, consider this simpler problem:
Given a number $N$, find the maximum set of co-primes $A$ (i.e. $\forall a, b \in A\implies \text{GCD}(a, b) == 1$) such that each number $a\in A$ is $a < N$.
...
- 13
0
votes
0
answers
23
views
Does the following GCD divisibility constraint imply that $\sigma(m^2)/p^k \mid m$, if $p^k m^2$ is an odd perfect number with special prime $p$?
The topic of odd perfect numbers likely needs no introduction.
In what follows, denote the classical sum of divisors of the positive integer $x$ by $$\sigma(x)=\sigma_1(x).$$
Let $p^k m^2$ be an odd ...
- 8,010
3
votes
2
answers
235
views
Interesting NT Question With AP and GCD.
Find the number of prime triplets $(p, q,r)$ such that $p(p + 1), q(q + 1),r(r + 1)$ form a strictly increasing arithmetic progression, where GCD $(r − p, 2p + 1)=1$.
What I tried:
$r(r+1)-p(p+1)=2d$ ...
- 113
1
vote
0
answers
96
views
What $n$ would make $ \gcd _{k\ge1 }\left\{\dbinom{m+(k-1)\cdot n}{k}\right\}=1 \ \forall m \in \mathbb{N}$
This is a generalisation of this question.
Construct the sequence $a_n$
$$ a_n =
\begin{cases}
0, & \gcd _{k\ge1 }\left\{\dbinom{m+(k-1)\cdot n}{k}\right\}=1 \ \forall m \in \mathbb{N} \\
\min{m ...
- 6,620
1
vote
0
answers
27
views
Conventional notation for gcd and principal ideal in the context of Bezout domain [duplicate]
Background
Definition 1: Let $R$ be a commutative ring with identity, $c\in R$ and let $I$ be the set of all multiples of $c$ in $R$, that is, $I=\{rc\mid r\in R\}$. Set $I$ is an ideal and is ...
- 3,683
0
votes
0
answers
29
views
Slope and GCD points
given a slope in the form $y=ax+b$
My question is to know if there are (and if yes how to find them) points $(x,y)$ where :
$gcd(x,y)>1$ (to be more precise, the $gcd$ is made between the $x$ and ...
- 37
4
votes
1
answer
122
views
On Prime, Lcm and Divisibility
Let $d_n= \text{lcm} \{1,2,3..., n \}$ then prove that for any prime $p$ $$ \left(\frac{1}{p^5-1}\right)\left(\frac{d_{p}}{p}\right)^5 \text{is not an integer}$$
Clearly $$\frac{d_p}{p}\in\mathbb{Z},...
- 910
1
vote
2
answers
73
views
Expected number of factors of $LCM(1,…,n)$ (particularly, potentially, when $n=8t$)
I’m trying to prove something regarding $8t$-powersmooth numbers (a $k$-powersmooth number $n$ is one for which all prime powers $p^m$ such that $p^m|n$ are such that $p^m\le k$). Essentially, I have ...
- 1,789
0
votes
3
answers
114
views
$\gcd(\text{multiples}(a,b))= \text{lcm}(a, b)$?
I am exploring whether the following assertion holds true in integral domains: $\gcd(\text{multiples}(a,b))= \text{lcm}(a, b)$. Let us make this formal below.
Consider two elements $a$ and $b$ in an ...
- 1,139
0
votes
1
answer
21
views
$f((x,y))=(x*gcd(x,y),y) $is injective and surjective?
The function $f:\mathbb{N^+}\times\mathbb{N^+} \rightarrow \mathbb{N^+}\times\mathbb{N^+} $ definide as $f((x,y))=(x*gcd(x,y),y) $is injective and surjective?
Let $(a,b)\in\mathbb{N^+}\times\mathbb{N^+...
2
votes
1
answer
102
views
Question on LCM and divisibility
Let $d_n= \text{lcm} \{1,2,3..., n \}$ then for which natural numbers $n$ is $$\frac{24 d_n^5}{(n+1)^5} \text{not an integer?}$$
We know that $$ \text{lcm}\{1,2,3,...,n\}.\text{gcd}\{1,2,3,...,n\}=n!$...
- 910
0
votes
2
answers
37
views
Velleman 6.4.17 - Stuck with proof involving GCD and divisibility
Level and context: I'm a first-year undergraduate self-studying proof writing from Velleman's How to Prove It (second edition).
Exercise 17 (a). Suppose $a$, $b$, and $p$ are positive integers and $p$ ...
0
votes
0
answers
42
views
In $\Bbb Z[i]$ find $\gcd(2-7i,2+11i).$ Also find $x,y\in \Bbb Z[i]$ such that $(2-7i)x+(2+11i)y=\gcd(2-7i,2+11i).$ [duplicate]
In $\Bbb Z[i]$ find $\gcd(2-7i,2+11i).$ Also find $x,y\in \Bbb Z[i]$ such that $(2-7i)x+(2+11i)y=\gcd(2-7i,2+11i).$
I tried solving the problem as follows:
Let $d=\gcd(2-7i,2+11i).$ So, $$d|2-7i,d|2+...
- 3,065