Questions tagged [gcd-and-lcm]
Use for questions related to gcd (greatest common divisor), lcm (least common multiple), and related concepts from integer and ring theory.
2,298
questions
1
vote
0answers
14 views
The ideal of polynomials in $\mathbb{Z}[x]$ that have local roots is principal. Same for several variables?
Property 1: Let $g_{1}(x), ... , g_{k}(x) \in\mathbb{Z}[x]$ such that given any $m\in\mathbb{N}$ , one has a $x_{0}\in\mathbb{Z}$ such that $g_{i}(x_{0}) \equiv 0$ (mod $m)$ for every $i = 1, ... , ...
1
vote
1answer
43 views
Let $S$ be the set of all integers $k$, $1\leq k\leq n$, such that $\gcd(k,n)=1$. What is the arithmetic mean of the integers in $S$?
QUESTION: Let $S$ be the set of all integers $k$, $1\leq k\leq n$, such that $\gcd(k,n)=1$. What is the arithmetic mean of the integers in $S$?
MY APPROACH: According to the question, every number in ...
-2
votes
1answer
44 views
Lcm problem and array [closed]
Let $a = [1,2,3,\ldots, n]$. In one second we can take any two elements $a_i,a_j$ and replace them with ${\rm lcm}(a_i,a_j)$. We have to find the minimum time to make all elements of the array equal. ...
0
votes
0answers
69 views
Product of positive integers on a circle [closed]
$2015$ positive integers are arranged on a circle. The difference
between any two adjacent numbers equals their greatest common divisor.
Determine the maximal value of $N$ which divides the product of ...
2
votes
4answers
86 views
$LCM(a,b) ≤ ab$ for positive integers $a,b$?
Let $a,b\in\mathbb{N}$ be nonzero. Does $LCM(a,b)\leq ab$?
I don't see how it can fail. So I believe it is correct. Can you give me any feedback?
2
votes
5answers
86 views
GCD with two big large numbers
How to find the $\gcd(2020^{1830} +2, 2020^{1830} -2)$? I can't seem to find the gcd because of the large numbers.
0
votes
0answers
76 views
show that $\gcd(p!-1,q!-1)<p^{\frac{p}{3}}$ [closed]
let $p,q$be prime number, and $p>q$
show that
$$\gcd(p!-1,q!-1)<p^{\frac{p}{3}}$$
Maybe this question is a research question, but this question comes from a test, I want use $p|(p-1)!+1$,and I ...
-1
votes
1answer
28 views
GCD( LCM(a,b) , LCM(a,c) ) = LCM(a, GCD(b,c)) , How? [duplicate]
I actually asked this question already once here, but I marked it answered by mistake and it was also titled wrong. I wanted to ask where I went wrong in the following lines and what should be the ...
1
vote
0answers
27 views
GCD( LCM(a,b) , LCM(a,c) ) = LCM(b, GCD(b,c)) , why? [duplicate]
I was doing this problem on codeforces, and as I was trying to simplify the formula, I arrived at the above conclusion. But now that I think of it, I actually arrived at that conclusion by mistake. ...
1
vote
1answer
44 views
Least common multiple in Euclidean algorithm
I want to prove that in last step of Euclidean algorithm we have lcm representation
(by last step I mean the step with zero representation as $0 = x * E_0 + y * E_1$, where we apply euclidean ...
0
votes
1answer
24 views
Frame rate repeat and judder calculation
When we display a 24 fps movie over a 60 Hz display, from what I know that judder occurs because the unevenness to display every odd frame twice and even frame thrice (11 222 33 444 55 666 ...).
I am ...
0
votes
1answer
40 views
How to find $n$, such that $\gcd(a, b+nc)\ne1$
Given three polynomials $a(x)$, $b(x)$, and $c(x)$ over the integers, one needs to find an integer $n$, such that $\gcd(a(x), b(x) + n\cdot c(x)) \ne 1$.
Is there a general way to find such an $n$ or ...
1
vote
3answers
43 views
pairwise relatively prime pairs
Let m be divisible by $1,2, ... , n$.
Show that the numbers $1+m(1+i)$ where $i = 0,1,2, ... , n$ are pairwise relatively prime.
My proof was as following let us have two different numbers $1+m(1+i)$...
0
votes
1answer
32 views
writing proof for greatest common divisor and least common multiple of fractions
I know that LCM of fractions is equal to (LCM of numerator / GCD of denominator) and GCD of fractions is equal to ( GCD of numerator / LCM of denominator).
However , I wonder that why these formulas ...
3
votes
1answer
38 views
Theorem on GCD of polynomials
Let
$F$ be a field and suppose that
$d(x)$ is a greatest common divisor of two polynomials $p(x)$ and $q(x)$ in $F[x]$. Then there exist polynomials $r(x)$ and $s(x)$ such that $d(x)=r(x)p(x)+s(x)q(x)...
3
votes
0answers
34 views
The ideal generated by $x^m-1$ and $x^n-1$ in $\mathbb{Z}[X]$ is principal. [duplicate]
I can show that $(x^m-1, x^n-1) \subseteq (x^{(m,n)} - 1)$, but I am stuck with the other inclusion. i.e. showing there exist polynomials $p, q \in \mathbb{Z}[X]$ such that $p(x)(x^m-1) + q(x)(x^n-1) =...
2
votes
1answer
37 views
Not knowing the $\mathrm{gcd}$ and $\mathrm{lcm}$ and knowing $\mathrm{gcd+lcm}$, how to find $a$ and $b$ in $\mathrm{gcd}(a,b)$?
Here's what we have:
$\mathrm{gcd}(a,b)=d$ ; $\mathrm{lcm}(a,b)=m$ ; $a+b=30$ ; $m+d=42$ ; $b>a$.
What I tried:
if $d$ divides $a$ and $b$ so it divides $a+b$ so $d$ divides $30$.
And with $\mathrm{...
3
votes
0answers
43 views
How to find $n$ on equations that look like $\mathrm{gcd}(n, x)=y$.
How to find the $n$ in equations like $\gcd(n, x)= y$ for some random $x,y$?
For example, I want to find $n$ if $B=n+3$ and $\gcd(B,10)=5$.
What I know is that $5$ divides $B$ and $10$ so it divides $...
3
votes
5answers
90 views
Number of $(\lambda_1,\cdots,\lambda_n)$ such that $\operatorname{lcm}(\lambda_1,\cdots,\lambda_n)=160$
Recently, I have found this problem:
Find the number of $n$-tuples of integers $(\lambda_1,\cdots\lambda_n)$ with $n\neq1$, $\lambda_i\neq\lambda_k \;\forall i,k\leq n$ and $\lambda_i\neq1$ such that:...
2
votes
0answers
157 views
Domain satisfying ACCP and GCD property [duplicate]
If $R$ is a domain satisfying ACCP and for all $a,b \in R$, $\gcd(a,b)$ exists, then $R$ is a UFD.
Now my strategy is to prove all irreducible elements in $R$ are also prime. So take an irreducible ...
2
votes
3answers
79 views
Proving $\gcd(a_1,\ldots,a_m)\gcd(b_1,\ldots,b_n)=\gcd(\text{all products $a_ib_j$})$
Prove that
$$\gcd(a_1,\ldots,a_m)\gcd(b_1,\ldots,b_n)=\gcd(a_1b_1,a_2b_2,\ldots,a_mb_n)$$
where the parentheses on the right include all $mn$ products $a_ib_j$, $i=1,\dots,m$, $j=1,\ldots,n$
My ...
1
vote
2answers
60 views
Find the values of $k$ that satisfy $\gcd(a,b)=5$
Let $a$,$b$ and $k$ be integers such that
$$a=6k+4$$
$$b=11k+4$$
Find $k$ values that satisfy $\gcd(a,b)=5$
Note: $(a,b)$ are solutions to the equation : $11a-6b=20$
My try :
$\gcd(6k+4,11k+4)=\gcd(k-...
0
votes
1answer
14 views
Question involving ratios and Greatest Common Divisors
Consider 6 variables $a,b,c,x,y,z\in\mathbb Z$. We have two ratios, $a:b:c=1:2:3$ and $x:y:z=1:2:3$. We also have that $\gcd(a,x)=2$. What is $\gcd(a+b+c,x+y+z)$? I know that $\gcd(a,x)=2$, which ...
2
votes
1answer
60 views
How do I find the value of $\operatorname{LCM} (a_1^k,a_2^k, \ldots ,a_n^k) \pmod {m}$?
LCM can be upto or greater than $10^{50}$.
$k$ and $m$ are upto $10^9$.
My current approach is
Finding the LCM .
(LCM % m)^k=A.
A % m.
This is working but takes a long time in finding LCM using GCD.
...
4
votes
1answer
68 views
Prove that $\gcd(2^{2^{22}}+1,2^{2^{222}}+1)=1$
The great common divisor (gcd) of $2^{2^{22}}+1$ and $2^{{2}^{222}}+1$ is
My work,
\begin{align}
F_{n}-2&= 2^{2^{n}}+1-2 \\
&=(2^{2^{n-1}}+1)(2^{2^{n-2}}+1)(2^{2^{n-2}}-1)\\
&=(2^{2^{m}}+1)...
4
votes
2answers
96 views
if the lcm is simply the product, then the integers are pairwise prime
I am trying to prove that
let $n_1,\ldots,n_k \in \Bbb Z\setminus\{0\}$. then $\gcd(n_i,n_j)=1 \forall i\neq j$ iff $\operatorname{lcm}(n_1,\ldots,n_k)=n_1\cdots n_k$
I can prove "$\Rightarrow$&...
-1
votes
1answer
67 views
LCM relation for $n$ numbers? [closed]
I just want to know:
Is $(\operatorname{LCM}(a_1, a_2, a_3, \ldots, a_n))^k = \operatorname{LCM}\left(a_1^k, a_2^k, a_3^k, \ldots, a_n^k\right)$?
Here $1 \leq a_i \leq 10^7$ and $1 \leq k \leq 10^9$ ...
1
vote
1answer
38 views
How $\{am + pn : m, n \in \mathbb{Z}\}=\langle 1 \rangle$?
I don't understand how $\{am + pn : m, n \in \mathbb{Z}\}$ is equal $\langle 1 \rangle$, doesn't $\langle 1 \rangle$ contains all integer of $\mathbb{Z}$? the passage I got it from -
Prime ideal ...
3
votes
4answers
96 views
How many unordered pairs of positive integers $(a,b)$ are there such that $\operatorname{lcm}(a,b) = 126000$?
How many unordered pairs of positive integers $(a,b)$ are there such that $\operatorname{lcm}(a,b) = 126000$?
Attempt:
Let $h= \gcd(A,B)$ so $A=hr$ and $B=hp$, and $$phr=\operatorname{lcm}(A,B)=3^2\...
0
votes
2answers
58 views
Gaps in the proof finite subgroup of the multiplicative group of a field must be cyclic
I am trying to prove that a finite subgroup of the multiplicative group of a field must be cyclic. I got a proof in one of the textbook for Algebra(attached below).
But I cannot see how the last step ...
0
votes
2answers
92 views
Bipartite-Graph GCD question
Let $G$ be a bipartite graph with bipartition $(A, B)$. Suppose every vertex in $A$ has degree $k_a$, and every vertex in $B$ has degree $k_b$. Prove that if $G$ has a bridge, then $\operatorname{gcd}(...
0
votes
2answers
38 views
Solvability condition for congruences systems
I know that a congruence system certainly has a solution if $gcd(m_1, m_2) = 1$
$$
\begin{cases}
a_1x \equiv b_1\pmod{m_1}\\
a_2x \equiv b_2\pmod{m_2}\\
\end{cases}
$$
but there are some systems ...
0
votes
1answer
31 views
Extension of claim regarding polynomials yielding composite (as opposed to prime) values
It is easy to prove that, if $p$ is any nonconstant polynomial with integer coefficients, then there is some positive integer $n$ such that $p(n)$ is composite. Is it also known to be true that there ...
-1
votes
2answers
74 views
If $ a-b \mid ax-by$, then $\gcd(x,y) \ne1$? [closed]
So is this true for positive integers $a,b,x,y>1$ with $a>b$ and $x>y$?
0
votes
2answers
31 views
How to find 2 numbers with given sum and minimum LCM? [closed]
How to find 2 numbers with given sum and minimum LCM?
for example if sum = 9 then two numbers are 3 and 6 since 3 + 6 = 9 and LCM(3, 6) = miniminum possible.
0
votes
0answers
14 views
Count number of valid sequences that satisfy pairwise LCM
Suppose there is a sequence of $n$ positive integer numbers, e.g., for $n = 3, A_1, A_2, A_3$.
We are given pairwise LCM (prime factorization of LCM, to be specific) of some pairs of them, e.g.,
$LCM(...
1
vote
2answers
34 views
LCM: Counting number of digits
If the least common multiple of two 6-digit integers has 10 digits, then their greatest common divisor has at most how many digits?
I can not figure out a way to solve this. I thought that the answer ...
0
votes
1answer
23 views
Determination of the value of $n$ in $\mathbb{Z}_n$ subject to $x+y=2$ and $2x-3y=3$
$\mathbf{Question}$: Determine the integers $n$ for which $\mathbb{Z}_n$, the set of integers modulo $n$, contains elements $x,y$ so that $x+y=2$, $2x-3y=3$.
$\mathbf{Attempt}$: Let us put $x=n\alpha+...
2
votes
2answers
91 views
If $ \gcd(a,b) = 1$ prove that $ \gcd(2a+b, a+2b) = 1$ or $3$?
I have seen this question, some other related questions and answers for solving this problem. However, I tried to solve it using a different approach.
Let, $ \gcd(2a+b, a+2b) = d$
Assume $2a+b = qd\...
0
votes
0answers
27 views
Is there a property relating gcd(a, b) % c and gcd(a %c, b%c) % c. Here all a,b,c are natural numbers i.e.>0 and '%' represents modulo operator.
I have been facing some difficulty solving problems relating the gcd and modulo operator.
If I use the Euclidean algorithm then it works fine when either a or b is small because in one step itself a ...
2
votes
1answer
67 views
Find smallest $x$ such that $\gcd(a + x, b + x) = c$.
I need to find the smallest $x$ such that
$$\gcd(a + x, b + x) = c$$
where $a, b, c, x$ are positive integers and $a \le b$. I was able to rewrite it as
$$\gcd(a + x, b - a) = c$$
This shows that $c$ ...
1
vote
0answers
39 views
GCD of Ideal: How we get $\gcd(I, J) = I + J $?
Take any two non-zero ideals $I$ and $J$ in $R$. Since we know that ideals in a Dedekind domain factors uniquely into prime ideals
$$I = \prod_i P_i^{m_i}, J = \prod_i P_i^{n_i}$$
where $P_i$’s are ...
2
votes
2answers
73 views
A question regarding the proof of $\gcd(a^m-1, a^n-1) = a^{\gcd(m,n)}-1$
I have a problem trying to understand the proof:
Theorem $\boldsymbol{1.1.5.}$ For natural numbers $a,m,n$, $\gcd\left(a^m-1,a^n-1\right)=a^{\gcd(m,n)}-1$
Outline. Note that by the Euclidean ...
2
votes
1answer
44 views
Proof verification of a number theory problem involving sequences.
$\textbf{Question:}$Does there exist an infinite sequence of integers
$a_1, a_2, . . . $ such that $gcd(a_m, a_n) = 1 $ if and only if $|m - n| = 1$?
$\textbf{My solution:}$Suppose we have a $n$ ...
0
votes
2answers
32 views
Let $a,b \in \mathbb{Z}$ and let $d = gcd(a,b)$. Show that $\{ ka + lb: k,l \in \mathbb{Z}\} = \{md : m \in \mathbb{Z} \}$
I know that given $d = gcd(a,b)$ that this also means $xa + yb = d$. Using this we get (showing from left to right side)
$$xa + yb = d$$ $$m(xa + yb) = md$$ $$xma + ymb = md$$
Now I am unsure how to ...
0
votes
2answers
42 views
Given that $a,b \in \mathbb{Z}$ and are nonzero. Why is it that $\frac{a}{\gcd(a,b)}$ and $\frac{b}{\gcd(a,b)}$ are coprime? [duplicate]
I understand the definition of coprime, which is $\gcd(\frac{a}{\gcd(a,b)},\frac{b}{\gcd(a,b)}) = 1$ or $x(\frac{a}{\gcd(a,b)}) + y(\frac{b}{\gcd(a,b)}) = 1$.
I am pretty sure that I have to use the ...
0
votes
0answers
11 views
Checking that U(n) is a set that is closed under multiplication modulo n [duplicate]
In Joseph Gallian's Contemporary Abstract Algebra, example 11 of chapter 2, the author leaves it to the reader to check closure for U(n), so I am trying to figure out if my solution is correct, or ...
0
votes
2answers
29 views
Prove $\gcd (2^n- 1 ;2^m-1) = (2^d-1)$ [duplicate]
Looking for a high school level proof of
$\gcd (2^n-1 ; 2^m-1)=(2^d-1)$
Where $d= \gcd(m;n)$
1
vote
1answer
47 views
Prove that the set of all positive integers less than $n$ and relatively prime to n form a group under multiplication modulo n
I came across the problem
Prove that the set of all positive integers less than $n$ and relatively prime to n form a group under multiplication modulo n.
Proving the associativity of multiplication ...
1
vote
1answer
44 views
Is it true that $HCF(HCF(a,b),c)=HCF(a,HCF(b,c))$
If $a,b,c$ are any three positive integers, Is it true that $HCF(HCF(a,b),c)=HCF(a,HCF(b,c))$
My try:
Case $1.$ if atleast one of $a,b,c$ is equal to ONE , then the claim is True.
case $2.$ If every ...
