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
0
votes
2answers
27 views

GCD and LCM number theory problem

I am having some trouble finishing a solution to this problem, so I thought I might ask you all for help. The problem goes as follows: Find all natural numbers $a,b>0$ for which holds: $$lcm(x,y)-...
0
votes
1answer
25 views

Inverse number using gcd [duplicate]

If I want to find the inverse number of $5$ $mod448$ using $gcd$. I try to do like that: $448=89\cdot5+3$ $gcd(5,448)=gcd(89,3)$ $89=3\cdot29+2$ $gcd(89,3)=gcd(29,2)$ $1=29-2\cdot14$ $1=29-14\cdot(89-...
0
votes
3answers
35 views

Proving a and b are perfect squares if and only if $\gcd(a,b)$ and $\operatorname{lcm}(a,b)$ are perfect squares

Let $a$, $b$ be two positive integers. Prove that $a$ and $b$ are both perfect squares if and only if both $\gcd(a,b)$ and $\operatorname{lcm}(a,b)$ are perfect squares. I believe the proof is based ...
0
votes
0answers
28 views

I don't understand how a certain step has been reached.

I have found the $\gcd(408,126) = 6$. Now I am using Bézout's identity to find the coefficients. a) $408 = 3 * 126 + 30$ b) $126 = 4 * 30 + 6$ Now $6 = 126 – (4 ·30)$ (1) $ = 126 – 4 ·(408 – 3 ·...
-2
votes
1answer
25 views

Writing code in GAP

I want to write some GAP code that prints finite abelian groups that are the direct product of two cyclic groups. However, I want the order of the cyclic groups to have the condition that the gcd(𝑛,6)...
-2
votes
4answers
41 views

Number theory (Fermats Little Theorem ) I will be thankful if you answer this question [closed]

If $\gcd(n , 7) = 1$, then prove that $7 | (n^{12}-1)$.
3
votes
3answers
38 views

How to formally prove that $\gcd(a,1) = 1$ when $a \in Z$ [duplicate]

I was trying to prove that $$\gcd(2a+1,9a+4) = 1 , a\in Z$$ My proof went like this: $$ (9a+4) = 4(2a+1) + a$$ $$ (2a+1) = 2(a) + 1 $$ $$ \Rightarrow \gcd(9a+4,2a+1) = \gcd(2a+1,a)=\gcd(a,1) = 1$$ The ...
1
vote
1answer
71 views

Prove $gcd(4,10)≠1$

I am trying to write a proof that shows that $gcd(4,10)≠1$ using only the definition of gcd below. $gcd(a,b)$ = min({k∈N : $k = ax + by$ for some $x,y∈Z$}) Here is what I have so far: By the ...
1
vote
3answers
89 views

$ x_n = 1 + 2a + 3a ^ 2 + \cdots + na ^ {n-1}$ has any three consecutive terms coprime

Let $ a \in \mathbb N $. For $ n \in \mathbb N $, let $$ x_n = 1 + 2a + 3a ^ 2 + \cdots + na ^ {n-1}. $$ $ x_1 = 1, x_2 = 1 + 2a, \ldots $. For $ n \in \mathbb N $, show that $ \gcd (x_n, x_ {n + 1}, ...
-1
votes
1answer
45 views

For what $k$ are the numbers $4n+1, kn+1$ coprime? [closed]

Already knowing the answer gives me sort of a hint ($k=\pm2^m+4 : m \in \mathbb{N} \cup \{0\}$), but I can't really find a way through it. Bonus question: how about a generalisation of this problem? ...
0
votes
1answer
37 views

For $\gcd(p,q) = 1$ and $\gcd(r,s) = 1$ show $\gcd(ps,rq) = 1$. [duplicate]

For $\gcd(p.q)=1$ and $\gcd(r,s)=1$ show $\gcd(ps,rq)=1$. I tried via contradiction. Let $\gcd(ps,rq) \neq 1$, so let $d > 1$ a common divisor of $ps$ and $rq$, i.e. $ps = dx$ and $rq = dy$ for ...
0
votes
0answers
13 views

Example of a ring satisfying Euclid's lemma, but with no gcd and/or lcm. [duplicate]

I am looking for an example of ring $A$, where the Euclid lemma is true. But, the ring A contains two elements $a$ and $b$ with non gcd, and lcm. I know that a notherian ring is factorial iff the ...
0
votes
0answers
40 views

Proving that $aR + bR = \gcd(a, b)R.$ [duplicate]

How can I prove this: In a Euclidean domain $R,$ we have that $aR + bR = \gcd(a, b)R$? Here are my thoughts: I know that if $d = \gcd(a, b),$ then it can be written as a linear combination of $a,b$ ...
1
vote
0answers
30 views

Find $d(x) = \gcd(f(x), g(x))$ and write $d(x)$ as a polynomial combination of both $f(x)$ and $g(x)$

Let $f(x) = x^4 + x^3 + x + 1$ and $\,g(x) = x + 1$ be two polynomials in $\mathbb{Z_2[x]}$ Find $d(x) = \gcd(f(x), g(x))$ and write $d(x)$ as a polynomial combination of both $f(x)$ and $\:g(x)$. My ...
1
vote
2answers
27 views

How to find the number of trousers sold by a merchant on a specific day of the month?

The problem is as follows: The owner of a bazaar in Daegu obtained for the sale of pants of the same price, $6804$ usd in September, $10800$ usd in October and $7938$ usd in December. If the price of ...
0
votes
1answer
14 views

How to find the greatest amount of savings from two people when it is related with a division?

The problem is as follows: A bank manager calculates the greatest common divisor of the numbers that represent the amounts of money in usd that Jenny and Gwen have, using Euclid's algorithm, the ...
4
votes
2answers
56 views

Proof $gcd(2^{2x},2x)=2gcd(2^{x},x)$

How do I proof $\operatorname{gcd}(2^{2x},2x)=2\operatorname{gcd}(2^{x},x)$ , I have managed to proof $\operatorname{gcd}(2^{2x},2x)=2\operatorname{gcd}(2^{2x-1},x)$ but haven't managed to get ...
0
votes
0answers
45 views

Prove that the elements of a sequence are pairwise co-prime [duplicate]

Hi I need help on this question: Consider the sequence of positive integers an, for $n ≥ 1$, defined by $a_n = 6^{2^n} + 1$. (a) Prove that the elements of this sequence are pairwise co-prime, i.e. ...
1
vote
1answer
55 views

Euclidean GCD and why does it work? [duplicate]

By the dupe, the table implies $\,(14441,3565) = (3565,189) = \ldots = (28,21) = (21,7) = (7,0) = 7\ \ $ I understand that Euclid's algorithm on GCD is based on doing division via subtraction $x = qy +...
-3
votes
0answers
21 views

how to prove this problem? [duplicate]

if gcd(a,b)=1, then show this gcd((a+b)^m,(a-b)^m)≦2^m
0
votes
2answers
27 views

Given $a, b$ positive integers, such that $\gcd(a, b) = 2$, $\gcd(a, 5) = 1$ and $a|5b$, show $a = 2$

Given $a, b$ positive integers, such that $\gcd(a, b) = 2$, $\gcd(a, 5) = 1$ and $a|5b$, show $a = 2$. My solution: Once for $d = gcd(a, b) \implies d|a$ and $d|b$, therefore for $\gcd(a, b) = 2$, $2|...
-1
votes
0answers
30 views

gcd proof question [duplicate]

Trying to show that for all a,b,c in N, gcd(a,bc) equals 1 is equivalent to gcd(a,b) = 1 and gcd(x,c) = 1). This makes sense but I am struggling with how to properly show this, I am not asking for a ...
1
vote
3answers
41 views

Is $GCD(2^n,(x^2+1)^{n-1})=1$ [duplicate]

Let $x>1,n>2$ be positive integers. I come across the following problem: Is $$GCD(2^n,(x^2+1)^{n-1})=1$$ or $2^n$ is relatively prime to $(x^2+1)^{n-1}$ ? Is $$GCD(x^{2n},(x^2+1)^{n-1})=1$$ ? NB:...
0
votes
0answers
21 views

Polynomial Long Division Algorithm: question on wiki examples [duplicate]

I was told the algorithm on Wiki for polynomial long division works for $\mathbb{Q}, \mathbb{R}, \mathbb{Z}$. Using this algorithm on Wiki I now understand it over $\mathbb{Q}, \mathbb{R}$, however ...
0
votes
1answer
36 views

find a upper bound of a product of gcd

Let $n,k \in \mathbb{N}$. Find a upper bound for $\gcd(n,2^n) \gcd(n+1, 2^{n+1}) \cdots \gcd(n+2^k, 2^{n+2^k})$. Note that in the upper bound, there should be no $n$, but having $k$ is fine. Attempt: $...
0
votes
1answer
59 views

Find the GCD Product of a number and its power

Let $n, k \in \mathbb{N}$. Find $\gcd(n, 2^n)\cdot\gcd(n+1, 2^{n+1}) \cdots \gcd(n+k, 2^{n+k-1})$. I've been thinking about this for a while. I tried to plug in $n=1$, but didn't find patterns. The ...
1
vote
2answers
55 views

Suppose $n \geq a_1>a_2>…>a_k\geq1$ and $lcm(a_i,a_j) \leq n$ for $i,j=1,2,…,k$. Show that $ia_i \leq n$.

Could I receive some hints on the problem. I do not know how to touch it since index $i$ seems like it does not depend on any of the other conditions.
0
votes
1answer
71 views

Split output from one conveyor belt equally to five other conveyor belts.

I was asked a question about the game "Satisfactory" and how to split an output into $5$ equal parts using "splitters" with one input and 2-3 outputs and mergers that accept 2-3 ...
0
votes
2answers
60 views

Find n where $GCD(a_{n}, 14) = 7$

The question was: Find $n$ where $GCD(a_{n}, 14) = 7$ where $n$ is natural if you knew that $a_{n} = n + 3$ The book solved it by saying that means $a_{n}$ is a multiple of $7$ but not $14$ so $a_{n}...
0
votes
0answers
18 views

attempting to show Bézout's identity for more than 3 integers [duplicate]

I am trying to prove that given $n_1, \dots ,n_s \in \mathbb Z$ and $d=gcd(n_1,\dots,n_s)$ there exist integers $m_1,\dots,m_n$ such that $n_1m_1 + \dots + n_sm_s = d$ here is what I have so far: let ...
-1
votes
3answers
59 views

There are $2^{\omega(a)}$ pairs $(b,c)$ such that $a=bc$ and $\gcd(b,c)=1$

It looks as there are $2^{\omega(a)}$ ordered pairs $(b,c)$ such that $a=bc$ and $\gcd(b,c)=1$, where $\omega(a)$ is the number of different prime factors of $a$. Proof? It's also true that there are ...
0
votes
1answer
27 views

Can we deduce that $x$ is a common divisor of $y$, $z$ and $u$

Let us consider the following relations between integers: $x$ divides $yw$ $x$ divides $zt$ $x$ divides $uq$ and $x$ is not a common divisor of $w$, $t$ and $q$. Here $w$, $t$ and $q$ are composite. ...
-1
votes
1answer
31 views

What is the greatest number of baskets that Mikayla can make if she wants to put the same amount in each? [closed]

She had 60 apples and 72 pears and we want to split them equally into baskets. I'm kinda confused because I'm in third grade and I'm learning this.
0
votes
1answer
23 views

lemma to the primitive divisor theorem.

I want to prove a lemma to the primitive divisor theorem. Where the theorem is given as: For each pair of coprime integers $a$ and $b$, $u_{n} = a^{n} - b^{n}$ has a primitive prime factor for $n > ...
0
votes
1answer
45 views

Proving Least Common Multiple [duplicate]

So I completed the first part of the proof where I prove $\frac{xy}{gcd(x,y)}$ is a multiple of $x$ and $y$. Now I need to prove for the second part that for any integer $m$ such that $x | m$ and $y | ...
2
votes
1answer
15 views

Finding $(a,b)$ in some given subset of $\mathbb{Z}^2$ with a specific gcd.

Given the subset of $\mathbb{Z}\times\mathbb{Z}\supset S=\{(9(k+3),4k), k\in \mathbb{Z}\}$ I’m trying to find $(x,y)\in S$ such that $\mathrm{gcd(x,y)}=18$. The set $S$ arises as the set of solutions ...
0
votes
1answer
47 views

$\operatorname{lcm}(a, b, c) = 100$ What are all the triads $a, b, c $ that happen? lcm-least common multiple

$$\operatorname{lcm}(a, b, c) = 100$$ What are all the triads $a, b, c $ that happen? How many answers are there? We've the canonical form $100=2^2 \cdot 5^2$ therefore $\tau(100)=9$ Assuming $a,b,c $ ...
0
votes
2answers
57 views

Need Greatest common divisor explaination

In the book the problem says: What is the GCD of two natural numbers m and n if after increasing the number m by 6 the GCD of two numbers increased 9 times. And the solution it gives is 2,3 or 6. Can ...
0
votes
0answers
39 views

How to find GCD using Hilbert's Nullstellensatz

I want to know if Hilbert's Nullstellensatz can be used to compute the greatest common divisor/factor (GCD) with a known degree for a set of polynomials without common zeros. The following is the ...
2
votes
1answer
39 views

Find a gcd of two polynomials from $\mathbb{Z}[i]$

I'm trying to solve this problem from my abstract algebra course: Being $z_1=39-8i$ and $z_2=7+i$ elements from the ring of Gauss integers, $\mathbb{Z}[i]=\{a+bi \mid a,b\in\mathbb{Z}\}$. Find a ...
1
vote
0answers
10 views

Rabin's test for irreducibility of deg 3 poly in $\mathbb F_{3}[X]$

My lecture notes says: Consider the polynomial $X^3-X+1$ in $\mathbb F_{3}[X]$. We can test irreducibility of $X^3-X+1$ by doing two gcd computations, namely $gcd(X^3-X, X^3-X+1)$ and $gcd(X^{3^2}-X, ...
0
votes
2answers
68 views

Number of integers $a$ that satisfy $a^n \equiv a \pmod{b}$, where $b = pq$?

Prove that the number of $a$ which satisfy: $$ a^n \equiv a \pmod{b}, $$where $b = pq$, $\quad$$p,q$ primes. is $[\text{gcd}(n-1,p-1)+1] \cdot [\text{gcd}(n-1,q-1)+1]$ Attempt: Since $p,q$ are coprime,...
3
votes
2answers
32 views

Showing that gcd(a,b) = gcd(c,d) in this case [duplicate]

We have a $2\times2$ matrix with $\mathbb{Z}$ entries, $$M =\begin{bmatrix}i&j\\k&l\end{bmatrix}$$ with $\det(M) = 1$. If $(c\; d) = (a\; b)M$ then how do we show that $\gcd(a,b) = \gcd(c,d)$ ...
0
votes
1answer
42 views

Given integers $a$ and $b$ prove that if there exist integers $x$ and $y$ for which $ax + by = (a, b)$, then $(x, y) = 1$. [duplicate]

I know that the answer involves Bezout's theorem in some way. I tried this: Let $(a, b) = d$ Let $a = dk_1 and b = dk_2$ So, $ax + by = d$ becomes $dk_1x + dk_2x = d$ Dividing by d, we get: $k_1x + ...
2
votes
0answers
337 views

GCD of odd and even polynomial proof elaboration

From my understanding of the Routh table, we are using Euclidean division of the odd and even parts of the characteristic equation to find the number of sign changes. When the whole row is zero, we ...
0
votes
3answers
39 views

Proving that $\gcd(a,ak+c)=\gcd(a,c)$ [duplicate]

I'm having some trouble proving the following proposition: Let $a,c \in \mathbb Z\setminus\{0\} $ and $k \in \mathbb Z$, then:$$\gcd(a,ak+c)=\gcd(a,c)$$ If $D_a$ and $D_c$ are the set of all numbers ...
1
vote
2answers
31 views

Additive order of modular product ring elements

Let $$ R = \mathbb{Z}_m\times\cdots\times\mathbb{Z}_m = \times_{i=1}^\ell\mathbb{Z}_m $$ I'm trying to find the additive order of elements of $R$. The additive order $\text{ord}(a)$ of $a\in\mathbb{Z}...
2
votes
0answers
73 views

Is $\mathbb{Z}[i,\varphi]$ a Euclidean domain?

Here $\varphi=\frac{1+\sqrt{5}}{2}$. It's true that $\mathbb{Z}[\varphi]=\mathcal{O}_{\mathbb{Q}(\sqrt{5})}$ is Euclidean since $\mathbb{Q}(\sqrt{5})$ is norm Euclidean, and I've read that $A=\mathbb{...
2
votes
0answers
60 views

A more mathematical way to solve the first problem in the project Euler archives.

Okay so the problem itself is really simple, If we list all the natural numbers below 10 that are multiples of 3 or 5, we get 3, 5, 6 and 9. The sum of these multiples is 23. Find the sum of all the ...
1
vote
1answer
25 views

Disclude a number in a sequence so that the greatest divisor common of all the others at most. Find that GCD and the position of that discluded one.

Problem. Disclude a number in a sequence so that the greatest divisor common of all the others at most. By programming, find that GCD and the position of that discluded one. My code in the ...

1
2 3 4 5
50