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).

-1
votes
3answers
47 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
0answers
57 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
40 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 \...
1
vote
0answers
19 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
26 views

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

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
51 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$....
0
votes
0answers
21 views

What will be the condition to maximize a%b? [closed]

Note:-"All numbers are integers" We are given 'a' as:- c1*k1+c2*k2+............+cn*kn. Where we know the values of :- c1,c2,c3....cn. And k1,k2...kn are the non-negative integers chosen by us to ...
1
vote
0answers
40 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
28 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] ...
-2
votes
1answer
74 views

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

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
59 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 ...
0
votes
0answers
55 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
13 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
46 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
59 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
33 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
60 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
79 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
58 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
80 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
37 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
29 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)&...
-2
votes
0answers
130 views

Is there any relation between GCD and modulo?? [duplicate]

Actually I am trying to solve a little tricky question where X is given in terms of GCD amd I am asked to find X mod 10. but due to my lack of knowledge in Number theory or you could say algebra ...
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
39 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
55 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
98 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$.
-4
votes
1answer
42 views

Prove $\gcd(2a,2b+1)=\gcd(a,2b+1)$

Let $a,b\in\Bbb Z$. $\gcd(2a,2b+1)=\gcd(a,2b+1)$ If $a\ge b,\gcd(2a+1, 2b+1) =\gcd(2a+1,2a-2b) =\gcd(2a+1,a-b)$ Please prove these two things.
3
votes
3answers
105 views

GCD of cubic polynomials

I would appreciate some help finding $GCD(a^3-3ab^2, b^3-3ba^2)$; $a,b \in \mathbb{Z}$. So far I've got here: if $GCD(a,b)=d$ then $\exists \alpha, \beta$ so that $GCD(\alpha, \beta)=1$ and $\alpha d=...
1
vote
3answers
40 views

Let $a, b$ and $n$ be natural numbers. Prove that if $a^n$ and $b^n$ are relatively prime, then $a$ and $b$ are relatively prime.

Let $a, b$ and $n$ be natural numbers. Prove that if $a^n$ and $b^n$ are relatively prime, then $a$ and $b$ are relatively prime. I have been able to prove the above statement by contrapositive in ...
-1
votes
1answer
182 views

What is $\gcd(61^{610}+1,61^{671}-1)$? [closed]

I implemented Extended Euclid Algorithm in c++ to solve this problem. Any approaches that you could it by hand. $\gcd(61^{610}+1,61^{671}-1)=\ ?$ Thanks in advance.
1
vote
0answers
14 views

Prove that there exists a $m×m$ lattice square in the $x-y$ plane such that none of its coordinates are visible [duplicate]

Call a lattice point 'visible' if the $gcd$ of its coordinates is 1. Then there exists a $m×m$ square in the $x-y$ plane such that none of its coordinates are visible. You can actually define such ...
2
votes
3answers
357 views

How to compute $\gcd(d^{\large 671}\! +\! 1, d^{\large 610}\! −\!1),\ d = \gcd(51^{\large 610}\! +\! 1, 51^{\large 671}\! −\!1)$

Let $(a,b)$ denote the greatest common divisor of $a$ and $b$. With $ \ d = (51^{\large 610}\! + 1,\, 51^{\large 671}\! −1)$ and $\ \ x \,=\, (d^{\large 671} + 1,\, \ d^{\large 610} −1 )$ find $\ ...
2
votes
2answers
100 views

Suppose that $T$ is the smallest positive integer satisfying $m^{T}\equiv \pmod {pq}$. Prove that $T\mid(p-1)(q-1)$.

Suppose that $p$ and $q$ are distinct primes and that $m$ is an integer satisfying $\gcd(m, pq) = 1$. Suppose that $T$ is the smallest positive integer satisfying $m^{T}\equiv \pmod {pq}$. Prove ...
0
votes
2answers
24 views

Is it possible to find a multiple knowing only: the count of its divisors, the upper limit and some of its divisors (more details)?

In other words, say I am looking for multiple X let: X < 1000005 let the fist 18 divisors of X be: 1 | 2 | 4 | 5 | 8 | 10 | 16 | 20 | 25 | 32 | 40 | 50 | 64 | 80 | 100 | 125 | 160 | 200 ...
0
votes
2answers
46 views

Prove that the sum is not an integer

Prove that if a / b and c / d are two irreducible rational numbers such that gcd (b, d) = 1 then the sum (a/b + c/d) is not an integer. I was thinking about the proof by contradiction, but then I ...
4
votes
2answers
82 views

About the limit $\lim_{n \to +\infty} \frac{1}{n^2} \sum_{1 \le a,b \le n} \frac{1}{ \mathrm{gcd} (a,b)} $

This is not homework. My question is: Prove or disprove: $$\lim_{n \to +\infty} \frac{1}{n^2} \sum_{a,b=1}^n \frac{1}{ \mathrm{gcd} (a,b)} = \frac{\zeta(3)}{\zeta(2)}$$ This would represent the ...
2
votes
1answer
43 views

How to derive the relation between $k$ and $l$ given $\langle g^k \rangle = \langle g^l \rangle$ in a cyclic group $C_n = \langle g \rangle$?

It is known that For a cyclic group $C_n = \langle g \rangle$ of order $n$, we have $\langle g^k \rangle = \langle g^{(k, n)} \rangle$, where $k \in \mathbb{Z}$. I am able to verify this result. ...
0
votes
1answer
21 views

$\gcd$ and $\text{lcm}$ of more than $2$ positive integers [duplicate]

For any two positive integers ${n_1,n_2}$, the relationship between their greatest common divisor and their least common multiple is given by $$\text{lcm}(n_1,n_2)=\frac{n_1 n_2}{\gcd(n_1,n_2)}$$ If ...
1
vote
0answers
28 views

How is the process of reducing the fraction down to zero almost exactly the same as finding the greatest common divisor?

Professor Sir Tom Davis in a note - Conway's Rational Tangles has said $$\\$$ If the students are a bit advanced, you can point out that the process of reducing the fraction down to zero is almost ...
0
votes
2answers
43 views

How does the Euclidean Algorithm apply on exponents m and n to show that $gcd(p^m-1, p^n-1) = p^{gcd(m,n)}-1$

No, this is not a duplicate of any thread. In fact, it is about a thread that I am still struggling to understand after all this time. I cannot comment on the thread because it was posted a very long ...
1
vote
1answer
58 views

A number theory question with calculus

Let $P(x)\in \mathbb{R}[x]$ Show there exists a non-constant polynomial $m(x)$ such that $m^2(x)|P(x)$ iff gcd$(P(x),P'(x))$ is not $1$. My attempt: if $m^2(x)|P(x)$ then $m(x)|gcd(P(x),P'(x))$. So ...
-1
votes
1answer
51 views

If $m\neq n$ what is $\mathrm{gcd}(a^{2n}+1,a^{2m}+1)?$ [closed]

If $m\neq n,$ compute $\mathrm{gcd}(a^{2n}+1,a^{2m}+1).$ In my question, $m$ , $n$ , and $a$ are positive integers.
0
votes
0answers
30 views

No gcd$\left(6, 3+3\sqrt{-5}\right)$ in $\mathbb{Z}[\sqrt{-5}]$ [duplicate]

Let $R$ be an integral domain, $a,b,d \in R$. We call $d$ a greatest common divisor of $a$ and $b$ (notation: $d = \text{gcd}(a,b)$) if we have I) $(a) + (b) \subseteq (d);$ II) $(\forall x\in R)((a)...
1
vote
1answer
46 views

Is there a method of proving that gcd(a, b) = c for values of a, b, and c that are not necessarily known?

For example, there is already a method of showing that gcd(a,b) = gcd (c,d) in general if you show that, say, gcd(a,b) being divisible by k is equivalent to gcd(c,d) being divisible by k. Why? Because ...
0
votes
2answers
30 views

$k$ is a divisor of $\ell m$. If $r$ = gcd($k$, $m$), prove that $k$/$r$ is a divisor of $\ell$.

I ran across this while reading through a matrix theory proof. I'm not sure how to show this. Any help would be much appreciated. My attempt: gcd($k$,$m$) = $r$ $\implies$ $kx + my = r$, for ...