Stack Exchange Network

Stack Exchange network consists of 175 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Questions tagged [greatest-common-divisor]

The greatest common divisor of two or more integers is the largest integer that divides all of them (if it exists).

2
votes
2answers
22 views

GCD of $f=X^3 +9X^2 +10X +3$ and $g= X^2 -X -2$ in $\mathbb{Z}/5\mathbb{Z}$.

I have to calculate the gcd of $f=X^3 +9X^2 +10X +3$ and $g= X^2 -X -2$ in $\mathbb{Q}[X]$ and $\mathbb{Z}/5\mathbb{Z}$. In $\mathbb{Q}[X]$ I got that $X+1$ is a gcd and therefore $r(X+1)$ since $\...
0
votes
2answers
26 views

Unknown number x, 45•G.C.F(125, x) = L.C.M (125, x)

The least common multiple of 125 and an unknown number x is 45 times their greatest common divisor. Here is what I've tried: Let $\gcd(125,x) = G$ and $\mathrm{lcm}(125,x)=L$. We know $$ 125 \...
0
votes
0answers
12 views

Simplifying $\gcd((7n+3)a, 2a-b)$, where $a$ and $b$ are perfect powers

As the question states, I want to find $\gcd((7n+3)a, 2a-b)$. Here $a = c^{n-2}$, $b = d^{n-2}$, where $c, d$ are relatively prime and $c > d$, and $n$ is a positive integer greater than 2. Let $x =...
1
vote
2answers
33 views

GCD and LCM mix question

Suppose $A,B$,and $C$ are integers greater than or equal to $2$. If $\gcd(A,B)=12, \text{lcm}(A,B)=396$ and $\gcd(B,C)= 33$, what is the $\gcd(11A,B)$?
0
votes
2answers
42 views

Prove that : $2k+1$ and $9k+4$ are relatively prime [closed]

Let k be an integer Prove that : $2k+1$ and $9k+4$ are relativly prime Find in terms of $k$ the greatest common divisor of $2k-1$ , $9k+4$
0
votes
1answer
28 views

Greatest common divisor of a, 2b

Let $a$ and $b$ be positive integers where $a$ is even and such that $\gcd(2a, 2b) = 70$. Find $\gcd(a, 2b)$.
0
votes
0answers
14 views

Periodicity of $\exp(jm(2\pi / N)n)$.

Problem: Show that the fundamental period of the discrete-time signal ($n, m, N \in \mathbb{N}$) $$x[n] = e^{jm(2\pi / N)n}$$ is $$N_0 = \frac{N}{\gcd(m, N)}$$ Attempt: Let $N_x \in \mathbb{N}$, $$x[...
-2
votes
1answer
22 views

Let (x+a) be the HCF of $x^2+px+q$ and $x^2+mx+n$. Show that $a=(q-n)/(p-m)$ [closed]

Let $(x+a)$ be the HCF of $x^2+px+q$ and $x^2+mx+n$. Show that $a=(q-n)/(p-m)$.
0
votes
1answer
26 views

How do i find the lcm [duplicate]

Qn: If the product of two integers is $2^7 \cdot 3^8 \cdot 5^2 \cdot 7^{11}$ and their greatest common divisor is $2^3 \cdot 3^4 \cdot 5$, what is their least common multiple? I have issue with this ...
-1
votes
0answers
57 views

Have I proven the GCD of three polynomials is $(2m-1)^2,m\in \mathbb{N}$?

I have $3$ functions of $n$ and $k$ where $GCD(x,y,z)$ is the square of an odd number but I don't know if I have proven it. Example, if $f(n,k)=(x,y,z)$, then $$GCD(f(2,1))=1$$ $$GCD(f(2,2))=1$$ $$...
1
vote
1answer
33 views

Find a linear representation of the greatest common divisor in terms of the polynomials $f(x)$ and $g(x)$

There are two functions: $$ f(x)=x^5+x^4-x^3-2x-1,\\ g(x)=3x^4-2x^3+x^2-2x-2 $$ And I've already found that their GCD equals $r_2=\frac{-9x^2}{4}-\frac{9}{4}$. Here are some other calculations ...
2
votes
0answers
38 views

Trying to count the number of integers $x \le n$ where gcd$\left(x(x+2),30\right)=1$ using the möbius function

Let: $x>0, n >0$ be integers gcd$(s,t)$ be the greatest common divisor of $s$ and $t$ $\mu(x)$ be the möbius function For $x \le n$ and gcd$(x,30)=1$, the count is: $$\sum_{i | 30}\left\...
0
votes
0answers
23 views

Greatest common factor of $ p^4-1$ [duplicate]

I was asked to find the greatest common factor of $p^4-1$ for all primes > 5, First I got the value of $7^4 - 1$ which has divisors of $2^4* 3 *5*2$ and $11^4 - 1$ which has divisors $2^4 *3 * 5*61$ ...
0
votes
1answer
38 views

How do you generate for a given solution for a linear diophantine equation more solutions

How can I generate for a given solution of a linear diophantine equation all solutions? For example let $21x+12y+9z=9$. I found one solution to be $(-3+3t,6-6t,t),t\in\mathbb Z$. How can I generate ...
1
vote
2answers
54 views

Proof that gcd(a,b)*lcm(a,b) = ab (solve only by Bézout's identity)

Hello all and good evening. As part of the course's assignments, we received a task to prove the following sentence using only Bézout identity: gcd$(a, b)$*lcm$(a, b)$ = ab Although I have found ...
1
vote
2answers
33 views

If $gcd(m,n) = gcd(m,k) = gcd(n,l) =1$ show that $gcd(kn+lm, mn) = 1$

I started by showing that $gcd(kn, m) = gcd(lm, n) = 1$, and with Bezout's lemma I wrote $knx + my = 1$ and $lmx' + ny' = 1$. Then I solved for my and $ny'$ and multiplied them together to get: $$ ...
2
votes
1answer
46 views

Error in Apostol's properties of Ramanujan's sums?

Reading through Tom Apostol's "Introduction to Analytic Number Theory, page 162. One finds the following theorem: Let $s_k(n) = \sum_{d | (n,k)} f(d) g(\frac k d)$ where $f$ and $g$ are ...
1
vote
2answers
44 views

Prove that $\gcd(m+m', n+n') = 1$

I'm stuck trying to solve this problem: "Given positive integers $m, n, m', n'$ such as $m/n < m'/n'$ and $m'n - mn' = 1$, we define $$a/b = (m+m')/(n+n').$$ Check that $m/n < a/b < m'/n'$ ...
4
votes
1answer
68 views

Finding minimum value of x such that GCD(A+x,B+x) = C where A , B ,C are given

I need to add Minimum non-negative Integer such that I can get the desired GCD(a+x,b+x) Let say A=12 & B=26 For GCD(12+x,26+x) = 1 , x should be 1 For GCD(12+x,26+x) = 2 , x should be 0 For ...
0
votes
3answers
38 views

How do we find greatest common divisor of 24 and 6?

How do we find that $GCD(24,6) = 6$ ? When i tried to use the "Euclidean algorithm" I got $24 = 6*4 + 0$
0
votes
1answer
23 views

Proving that if coprime $\alpha_{i}\in R$ divide b, then $\alpha_{1}…\alpha_{n}$ divide b.

Let $R$ be a principal ideal domain and let $\alpha_{1},...,\alpha_{n}\in R$ be such that $(\gcd(\alpha_{i},\alpha_{j}))=(1)$. Let $b\in R$ such that each $\alpha_{i}|b$. I want to show that $\...
-1
votes
3answers
52 views

Prove: $\gcd(b,a) = \gcd(b,c)$ if $c \equiv a \pmod{b}$ [duplicate]

$b$ is an integer where $b > 1$ and $a, c$ are integers. Prove: $\gcd(b,a) = \gcd(b,c)$ if $c \equiv a \pmod{b}$ I am completely stumped on where to start. Any help is appreciated.
2
votes
1answer
64 views

(Strong) Duality for the integer programming for $\text{gcd}(c_1, c_2, \ldots, c_n)$

It is known that (quoted from CLRS, 3rd edition) If $a$ and $b$ are any integers, not both zero, then $\text{gcd}(a, b)$ is the smallest positive element of the set $\{ax + by: x, y \in \mathbb{Z}\}...
1
vote
1answer
41 views

Is there a commonly used term for a number divided by its greatest common divisor?

Does the expression $\frac{a}{\gcd(a, b)}$ have a common name? This type of expression occurs frequently in a program I'm writing. Since $ \forall a,b \in \mathbb{N^{*}}: \frac{a}{\gcd(a, b)} \perp \...
3
votes
1answer
96 views

Sums of the form $\sum\limits_{a_1=1}^n\sum\limits_{a_2=1}^{a_1}\cdots \sum\limits_{a_r=1}^{a_{r-1}}{[\gcd(a_1,a_2,\dots ,a_r)=1]}$

Background: Consider sums of the form $$\sum_{a_1=1}^n\sum_{a_2=1}^{a_1}\cdots \sum_{a_r=1}^{a_{r-1}}{[\gcd(a_1,a_2,\dots ,a_r)=1]},$$ with $[\gcd(a_1,a_2,\dots ,a_r)=1]$ being equal to $1$ if the ...
1
vote
2answers
28 views

Finding all pairs of integers satisfying gcd(a,b) = 6 and lcm(a,b)=540 [duplicate]

Given that $$a\cdot b=gcd(a,b)\cdot lcm(a,b)$$ How can we find all the integer solutions $(a,b)$ if $gcd(a,b)=6$ and $lcm(a,b)=540$? The first thing I did was factorizing using the fundamental ...
2
votes
2answers
76 views

Non-Separable Polynomials and their Derivatives

We say that a polynomial $f(x) ∈ F[x]$ is inseparable if it has a repeated root in some field extension. Otherwise we say that $f(x)$ is separable. Prove that $f(x)$ is separable $\iff\gcd(f, Df) = 1$....
1
vote
0answers
41 views

If $(m, n) = 1$, then $\dfrac{\mathbb Z \times \mathbb Z}{\langle (m,n)\rangle}\cong\mathbb Z$

How to show that If $(m, n) = 1$, then $\dfrac{\mathbb Z \times \mathbb Z}{\langle (m,n)\rangle}\cong\mathbb Z$. (Note: We consider this in group theory.) I know that $(m, n) = 1$ means that ...
2
votes
0answers
32 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] ...
-3
votes
1answer
82 views

How to calculate the gcd of (3^{100!}-1,116)? [closed]

I have to find out the result of $$(3^{100!}-1,116)$$ This is an exercise after the chapter of integer factorization and now I need help.
2
votes
1answer
60 views

Niho APN prove that $gcd(d − 1, 2^n − 1)$ , where d is exponent

in a finite field $F_{2^n}$ where $ d = \begin{cases} 2^t + 2^{t/2}-1 & \text{t even}\\ 2^t + 2^{(3t+1)/2}-1 & \text{t odd} \end{cases} $ and $n=2t+1$ How do you prove ...
1
vote
0answers
63 views

Proof by induction $\gcd(2^n-1,2^m-1)=2^{\gcd(n,m)}-1$

It is asked to perform a proof by induction over a variable $k$, which is $k=m+n$ and to use a given equation: $\gcd(a,b)=\gcd(a+b,b)=\gcd(ac+b,a)$, which might help throughout the proof-writing. ...
1
vote
0answers
17 views

Induction proof for gcd(a,b), and s, t

Show that if a ≥ b > 0, and gcd(a,b)=d, and as+bt=d, then the values s and t satisfy: |s| ≤ b/d and |t| ≤ a/d Hint: prove by induction on b: be careful, you have to stop the induction before b gets to ...
0
votes
0answers
47 views

If $\gcd(a,b)=1$ then $\gcd(a^n,b^n)=1$ [duplicate]

I wanted to use mathematical induction. So if $n=1$ then $\gcd(a^1,b^1)=1=\gcd(a,b)$ is true. Then I assumed $n=k$ then $\gcd(a^k,b^k)=1$ is true. At this part I need to show that $n=k+1$ is also true,...
0
votes
1answer
65 views

How many marbles?

One dozen of big marbles and small marbles is 132 gram. If one big marbles is 3 gram heavier than one small marbles, then specify the possibilities of how many are the big marbles and the small ...
-2
votes
2answers
37 views

gcd between powers of two co-prime numbers [duplicate]

Is it true that $\forall x,y,n\in \mathbb{Z}$, if $\gcd(x,y)=1$ then $\gcd(x^n, y)=1$? If not, is there a counterexample?
0
votes
1answer
32 views

Pirate and Bags of Coin

A pirate captain has 63 bags of coin with the same amount of coin inside each of the bags. If he wants to divided the coins to his 23 henchman evenly, he has to add 7 more coins. How many coins inside ...
1
vote
1answer
63 views

Find all triplets $(a,b,c)$ less than or equal to 50 such that $a + b +c$ be divisible by $a$ and $b$ and $c$.

Find all triplets $(a,b,c)$ less than or equal to 50 such that $a + b +c$ be divisible by $a$ and $b$ and $c$.(i.e $a|a+b+c~~,~~b|a+b+c~~,~~c|a+b+c$) for example $(10,20,30)$ is a good triplet. ($10|...
0
votes
0answers
7 views

How to prove that the the number of buckets a hash function will fill is equal to n/gcf(n,k)

This question comes from computer science but its formality makes it inappropriate for asking in a programming environment. I've been rated down for asking non "programming-only" questions on there so ...
1
vote
1answer
81 views

Prove if there exists $[b]\in{Z}_{pq}$ such that $[b]^2=[a]$ in ${Z}_{pq}$, then there are exactly four distinct $[x]\in{Z}_{pq}$

Let $p$ and $q$ be distinct odd primes. Let $a\in{Z}$ with $gcd(a,pq)=1$. Prove that if there exists $[b]\in{Z}_{pq}$ such that $[b]^2=[a]$ in ${Z}_{pq}$, then there are exactly four distinct $[x]\in{...
-1
votes
1answer
59 views

Is it true that (k,n+k)=d if and only if (k,n)=d? [duplicate]

Is it true that (k,n+k)=d if and only if (k,n)=d? I solved "Prove that (k,n+k)=1 if and only if (k,n)=1" but I cannot solve "Is it true that (k,n+k)=d if and only if (k,n)=d?" I think it is False ...
1
vote
1answer
82 views

Question about Modular Arithmetic

Let $q$ be an integer number. Consider an integer number $N$ such that $\gcd(q-1,N) = 1$. Question: How to show that if $q^d = 1 \pmod{N}$ for some positive integer $d$, then we get $$ 1 + q + q^2 + ...
0
votes
2answers
38 views

Minimum no of bits to represent X [duplicate]

It took me much time to reach the solution where I find the value of X as 2 but still not sure whether this is correct or not. please help me with the solution
1
vote
0answers
30 views

Find the gcd$((a^{2^n})+1,(a^{2^m})+1)$ where $m,n$ are two distinct positive integers. [duplicate]

Let gcd$((a^{2^n})+1,(a^{2^m})+1)=d$. Then $d|(a^{2^n})+1$ and $d|(a^{2^m})+1$. So, $(a^{2^n})$ congruent to $(-1)$ (mod $d)$ and $(a^{2^m})$ congruent to $(-1)$ (mod $d).$ Let $m>n$ then $(m-n)&...
0
votes
3answers
51 views

Triangular numbers and gcd

For all positive integers $n$, the $n$th triangular number $T_n$ is defined as $T_n = 1+2+3+ \cdots + n$. What is the greatest possible value of the greatest common divisor of $4T_n$ and $n-1$? Can ...
0
votes
1answer
40 views

Sum on GCD and prime numbers

I was studying gcd then I encountered this sum $(1).$ A conjecture: If $(1)=1$ for any values of $N\ge3$, then N is a prime number. Let: $$f(N)=\frac{1}{N^{1-s}(N-1)}\sum_{j=1}^{N}(-1)^jj^s\frac{{...
1
vote
2answers
61 views

Prove that if there are integers $m$ and $n$ such that $am +bn =1$ then $a$ and $b$ are coprime.

Suppose $a,b \in \mathbb{N}$. Prove that if there are integers $m$ and $n$ such that $am +bn =1$ then $a$ and $b$ are coprime. I came up with the following proof, but I am sure a shorter argument ...
1
vote
1answer
40 views

How to prove that if $(ab,n)=1$ then, $(r,n)=1$? [duplicate]

Let $ab=nq+r$ where all variables represent integers with $0\leq r<n$. If $(ab,n)=1$ then how to prove that $(r,n)=1$? I need to prove this to help me understand the proof of Euler's theorem better....
5
votes
0answers
99 views

Conjecture about primes and the greatest common divisor

Conjecture: Given $m,n\in\mathbb N^+$, one odd and one even, there are two primes $p,q$ such that $|mp-nq|=\gcd(m,n)$. I hope MSE can determine its validity. From time to time, when testing my ...
-2
votes
1answer
73 views

Prove gcd(n, n+m) divides m [closed]

The question asks me to use mathematical language to prove that: $\gcd(n, n+m)$ divides $m$.