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.

Filter by
Sorted by
Tagged with
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 ...

1
2 3 4 5
46