Stack Exchange Network

Stack Exchange network consists of 174 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).

3
votes
5answers
50 views

Let $a|bc $ then prove or disprove $a|(a,b)c$

Prove or disprove: Let $a|bc$ then $a|(a,b)c$ Here is my approach, but I am not sure if I am doing this correctly or efficiently. Let $a|bc$. It follows that either $1. a|b$ Proof: $b=ar, a|bc =&...
0
votes
2answers
22 views

With $a,\ b,\ m,\ n\in \mathbb{Z}$. Show that if ${\rm gcd}(m,n)=1$, then ${\rm gcd}(ma+nb,mn)={\rm gcd}(a,n){\rm gcd}(b,m)$

I don't really know how to prove this, i suppose it must have something to do with the definition of greatest common divisor and Bézout's identity. I looked at some other questions here and thought ...
0
votes
3answers
30 views

Find all possible values of $(7a+12,3a+5)$.

If $a$ is an integer. Find all possible values of $(7a+12,3a+5)$. I started with: Let $d$=$gcd(7a+12, 3a+5)$. Then $d|7a+12$ and $d|3a+5$. I am not sure what to do after this. I have seen online ...
1
vote
0answers
14 views

Extended GCD of two zero polynomials over finite field

Extended GCD of two polynomials $a$ and $b$ results in two polynomials $s$ and $t$ so that $as + bt = \text{gcd}(a, b)$. What convention makes most sense when both $a$ and $b$ are zero? I found that ...
1
vote
2answers
29 views

Gcd of two elements

Consider the ring $\mathbb{Z}[\sqrt{2}]$. I need to find $\gcd(4, 6)$. My try Let $N$ be norm function defined on $\mathbb{Z}[\sqrt{2}]$ and $d$ be proper divisor of $4$ and $6$ then $d$ can't be ...
1
vote
2answers
29 views

Euclidean GCD calculation and mod

Calculate $6/87 \pmod{137}$ I do not understand the Euclidean GCD algorithm. If someone can please explain the overall logic of this it would be much appreciated.I have posted what the solution is ...
1
vote
1answer
26 views

How many number of integer coordinates exists between a line segment, including the end points?

There is a line segment say $AB$ with coordinates of end-points as $A=(x_1, y_1)$ and $B=(x_2, y_2)$. $x_1, y_1, x_2, y_2$ are integers. I need to find the number of integer coordinates which lie on ...
1
vote
3answers
74 views

Prove that gcd$(n^2+1, (n+1)^2+1)$ is either 1 or 5

My try to solve this question goes as follows: $g=gcd(n^2+1, (n+1^2)+1) = gcd(n^2+1, 2n+1) = gcd(n^2-2n, 2n+1)$. By long division: $$n^2-2n = -2n(2n+1) + 5n^2$$ Since $g$ divides $n^2-2n$ and $g$ ...
0
votes
0answers
20 views

If $(x,y)=1 $ then $ (tx+y,n)=1$ [duplicate]

Prove that if $(x,y)=1$ than for all $n \in N$ exist $t \in N $ such that $$(tx+y,n)=1$$ I think this result is true because it follows from Dirichlet's theorem, although there must be an elementary ...
0
votes
0answers
24 views

$\gcd(x,y)=1$ then $\gcd(c \cdot x, c \cdot y)=c$ for polynomials

As a part of a proof I want to use that for polynomials $c, x,y$ it is the case that $\gcd(x,y)=1$ then $\gcd(c \cdot x, c \cdot y)=c$. Is this always true?
1
vote
2answers
31 views

For polynomials $f, g$ and $\gcd(f(X),g(X))=d(X)$ then $\gcd(f(X+a),g(X+a))=d(X+a)$

Suppose for polynomials f, g in $\mathbb{Q}[X]$ it holds that $$\gcd(f(X),g(X))=d(X)$$ What we also want to now prove is that for $a \in \mathbb{Q}$: $$\gcd(f(X+a),g(X+a))=d(X+a)$$ So the ...
-2
votes
0answers
21 views

Proof of a lemma used in Wilson's Theorem.

I have a presentation over Wilson's Theorem and I was trying to prove a lemma that is used. For any {$x∈N|x>3$}: gcd$((x−1)!,x)>1 =⇒(x−1)!\not≡_x−1$ All I have so far is that x must be ...
0
votes
1answer
72 views
+50

Prove subgroups of cyclic groups are cyclic without division algorithm, rings, homomorphisms or $\gcd$ of infinite numbers?

I have found a lot of proofs on this site, on proofwiki and elsewhere. I thought of my own which was unlike all I found except for 1 proof (I have linked it below.) and was wondering if I could get ...
1
vote
1answer
35 views

$h\mid (3a + 5b)$, prove $h\mid a$ and $h\mid b$ [duplicate]

I have this homework question. "For any integer $a$ and $b$, prove that $\gcd(a,b) = \gcd(3a+5b,11a+18b)$." I know that if $ g = \gcd(a,b)$ and $h = \gcd(3a+5b,11a+18b)$ then $g = h$ iff $...
-1
votes
0answers
24 views

what is the greatest number of baskets that can be made if there is a even amount of stuff in each between 24 36 and 60

If I have 24 apples, 36 bananas, and 60 cherries, how many baskets can I create using all of this fruit such that all fruit is used and each basket contains the same contents.
0
votes
1answer
27 views

Problems with finding inverse by using gcd

I´ve tried to solve this problem, but i think i need some help from you guys. In my textbook it is written that the inverse of 35 mod 3 is 2, i get that the inverse is 2, but how do you find it by ...
1
vote
0answers
20 views

Sequence of consecutive integers [duplicate]

I want to prove the following: Let $m_0,...m_r$ be pairwise coprime integers . Show that there exists a sequence of consecutive integers $s, s+1,...,s+r$ such that $m_i\vert s+i, i =0,...,r$ I know ...
6
votes
4answers
65 views

GCD in arbitrary domain

Is there a domain where computing GCD of two elements is not trivial (i.e. Euclid's algorithm will not work)? AFAIK we can always use the Euclid's algorithm in a Euclidean Domain.
0
votes
2answers
29 views

If $m > 0$, fix a reduced residue system $r_{1}, r_2, \dotsc, r_{\varphi(m)} $ mod $ m$. Let $x=r_1+r_2+\dotsb+r_{\varphi(m)}$. What is $x$ mod $m$? [duplicate]

Given $m > 0$, fix a reduced residue system (RRS) $r_{1}, r_2,\dotsc , r_{\varphi(m)} $ mod $ m$. Let $x$ denote the sum $r_1 + r_2 + \dotsb + r_{\varphi(m)}$. What is $x$ mod $m$? The problem is ...
1
vote
2answers
50 views

Derive the identity elements of lcm and gcd

Find the identity element of the binary operations $*,*'$ on $\mathbb{N}$ given by $a*b = lcm(a,b)$ and $a*'b = \gcd(a,b)$, where $\mathbb{N}=\{1,2,3...\}$ I know the identity element for lcm is $1$ ...
0
votes
5answers
47 views

Prove that if $\gcd(m,n)=d$, then $\frac{n}{d}$ is the minimum $x$ such that $mx$ is divisible by $n$

I am looking for the proof in the title because I am trying to prove that if $G$ is a cyclic group of order n with generator $a$, then the subgroup generated by $a^m$ has order $n/(m,n)$. I already ...
0
votes
3answers
56 views

Prove that $\gcd(a,0)=|a|$

I wish to prove a property of the $\gcd$, namely: $\gcd(a,0)=|a|$. Notice that for some $x,y$ we know that $\gcd(a,0)= ax+ 0 \cdot y$ such that $\gcd(a,0)$ is a multiple of $a$. How do we make the ...
0
votes
2answers
26 views

$\gcd(a,b)=\gcd(a, b- k \cdot a )$

We wish to prove that $\gcd(a,b)=\gcd(a, b- k \cdot a )$, where $a,b, k$ are integers. For any divisor $d|a$ and $d|b$ then we also have that for all integers $x,y$ we have $d|(ax+by)$ now let $x=-k$ ...
2
votes
3answers
66 views

$18a$ and $25a$ both integers, then so is $a$

Let $a\in \mathbb{Q}$ such that $18a$ and $25a$ are integers, then we wish to prove that $a$ must be an integer itself. What that means is that $a=\frac{p}{1}$ where $p \in \mathbb{Z}$. What we do ...
0
votes
1answer
49 views

Compute $\sum_{i=1}^n\frac i{\gcd(i,n)}$

Compute $$\sum_{i=1}^n\frac i{\gcd(i,n)}$$ The actual problem description is as follows : $$\sum_{i=1}^{15}\frac i{\gcd(i,{15})}$$ But I'd like a formula which could be used for large $n$.
4
votes
2answers
52 views

How to find GCD and LCM of a factorial and a large number?

So I was given this question: $n = 2^{16}3^{19}17^{12}$ Find $\gcd(n, 40!)$ and $\operatorname{lcm}(n, 40!)$. I understand how to find the GCD and LCM when its two really large numbers (given ...
-1
votes
3answers
79 views

What will be 6th number in this series? [closed]

An ascending series of numbers satisfied the following conditions When divided by 3, 4, 5 and 6 the number leaves the remainder of 2. When divided by 11, The number leaves no reminder. The 6th ...
8
votes
3answers
99 views

Query on a Solution to the Problem: $\gcd(5a+2,7a+3)=1$ for all integer $a$.

I wish to show that the numbers $5a+2$ and $7a+3$ are relatively prime for all positive integer $a$. Here are my solutions. Solution 1. I proceed with Euclidean Algorithm. Note that, for all $a$, $|...
1
vote
1answer
45 views

Greatest Common Divisor in a Diophantine Equation

Problem: Question: How did the author derive $$gcd(p-1,d)=1$$? how it is true? Reference: Page 33 of An Introduction to Diophantine Equations by Titu Andreescu, Dorin Andrica, Ion Cucurezeanu
1
vote
3answers
53 views

Let $ab=cd$ and $\gcd(a,c)=1$. Then $a | d$ and $c | b$.

Let $ab=cd$ and $\gcd(a,c)=1$. Then $a | d$ and $c | b$. $ab=cd \implies a|cd,$ but $\gcd(a,c)=1 \implies a \nmid c$, so $a | d$. $ab=cd \implies c|ab,$ but $\gcd(a,c)=1 \implies c \nmid a$, so $c | ...
1
vote
1answer
46 views

GCD as integral operator

Kind of weird question, but is there something like an integral operator which returns $1$ if $\gcd(a, b) = 1$ and $0$ otherwise, meaning $$ \int_{D} K(a, b, t) \, {\rm d}t = \begin{cases} 1 \qquad \...
4
votes
5answers
83 views

Consider the equation $a_n +b_n\sqrt{2} = (1+\sqrt{2})^n$ where $a_n, b_n \in \mathbb{Z} \ge 1$. Prove that $\gcd(a_n, b_n) = 1$.

Consider the equation $a_n +b_n\sqrt{2} = (1+\sqrt{2})^n$ where $a_n, b_n \in \mathbb{Z} \ge 1$. Prove that $\gcd(a_n, b_n) = 1$. I know that $(1+2\sqrt{3}) = 1^3 + 3(1)^2(\sqrt{2})^2 + 3(1)(\sqrt{2}...
1
vote
1answer
42 views

Prove that if $\\gcd(a,b)=1$ then $a\mathbb{N}\cap b\mathbb{N}=(ab)\mathbb{N}.$

Prove that if $\\gcd(a,b)=1$ then $a\mathbb{N}\cap b\mathbb{N}=(ab)\mathbb{N}.$ We have $1=\gcd(a,b)\implies au+bv=1$ for some $u,v\in \mathbb{Z}.$ Is it the correct way to prove the above result? ...
0
votes
1answer
46 views

Finding the correct $x$ to $ax - by = 1$

I want to find the modular inverse of $5 \pmod {13}$ such that : $$ 5x - 13y = 1$$ I tried to use the Euclidean alogritm for the GCD and use the extension(Extended Euclidean Algorithm) to solve for x....
-2
votes
3answers
39 views

Find the value of a if A divisable by 3 [closed]

$A=0.\overline{a}+0.\overline{aa}+0.\overline{aaa}\: \\ \text{If A is divisable by 3, }\: \text{find the value of} \: a\: $
3
votes
2answers
49 views

GCD of successive terms

I was solving this question, and I'm hitting a wall. $a_n=20+n^2\;\;\forall n\in\Bbb N,\quad d_n=\gcd(a_n,a_{n+1})$. Find with proof all values taken by $d_n$, and show by example when these values ...
0
votes
2answers
62 views

Prove that $\gcd(a+s,b+s)=1$ for infinitely many numbers $s$

Prove that for every natural numbers $a$ and $b$, there are infinitely many numbers $s$, such $\gcd(a+s,b+s)=1$ and $a\neq b$ I tried to use Bezout's theorem but I can't get to the result
1
vote
2answers
47 views

Prove that $gcd \left(2^{x}-1, 2^{y}-1\right) = 2^{gcd(x,y)}-1$

My attempt: 1) Try to use normal definition of gcd: $(a,b)=d\Rightarrow as_1+bs_2=d$ for some $s_1,s_2\in \mathbb Z \tag1$ So $\left(2^{x}-1, 2^{y}-1\right)=s_1(2^x-1)+s_2(2^y-1),\quad s_i\in\...
1
vote
2answers
79 views

Modular inverse of Gaussian Integers

Let $f_0$ and $f_1$ be Gaussian Integers such that $f_0 = a + i$ and $f_1 = b + i$. How can I compute $f_0^{-1} mod f_1$ and $f_1^{-1} mod f_0$? I've been trying to apply the Extended Euclidean ...
2
votes
3answers
67 views

Determine the greatest common divisor of polynomials $x^2+1$ and $x^3+1$ in $\Bbb Q[X]$.

Exercise: Determine a gcd of the polynomials $x^2+1$ and $x^3+1$ in $\Bbb Q[X]$.. Write the gcd as a combination of the given polynomials. Is it correct that I keep using long division until the ...
1
vote
2answers
82 views

$\gcd(a,b)=1 \iff \gcd(a+b,ab)=1$.

If $a,b\in \mathbb{Z}$ then: $$\gcd(a,b)=1 \iff \gcd(a+b,ab)=1$$ Let $p$ be a prime number. Let $\gcd(a,b)=1$, and $p | a+b,p|ab$. $p|ab \implies p|a \ \text{or}\ p|b$. WLOG let $p|a$, then $p|a+b$...
0
votes
0answers
27 views

Number Theory: Divisibilty

Q: Prove that if a and b are positive integers satisfying (a,b)=[a,b}, then a=b. My approach (with ans): (a,b) means gcd, and I let g=(a,b) since g is the gcd, then I get these two: g|a and g|b, ...
0
votes
1answer
25 views

Organizing objects in a near-square pattern

I don't have any fixed constraints but just a general idea. This probably a well known problem too - yet I can't seem to find any literature on it. Given n identical 2D objects, what is an algorithm ...
0
votes
0answers
19 views

GCD algorithm with approximative factors

I am looking for an algorithm that allows to compute an approximative GCD, as below. Suppose we have two numbers $N_1, N_2\in \mathbb N$ such that there are $a,b,c,\varepsilon\in\mathbb N$ with $$ \...
0
votes
1answer
35 views

Finding GCD of recursive sequence

I need help with this exercise, I don't know how to aproach it. Find $\gcd(a_n,a_{n+1})$ for each $n \in \mathbb{N}$ $(a_n)_{n\in\mathbb{N}} :\left\{\begin{matrix} a_1 = 2 \\ a_2 = 4 \\ a_{n+2} = ...
3
votes
0answers
45 views

Are there any other squares $n^2$ for which $\gcd(n^2, \sigma(n^2)) = 2n^2 - \sigma(n^2)$?

Let $\sigma(x)$ denote the sum of the divisors of the positive integer $x$. Denote the deficiency of $x$ by $$D(x)=2x-\sigma(x).$$ I am interested in solutions to the equation $$\gcd(n^2, \sigma(n^2)...
0
votes
2answers
27 views

Show that $\exists a, b$ where $\gcd(a,b) = d$ and $\operatorname{lcm}(a,b) = e$ iff $d \mid e$

I want to show, given the natural numbers $d$ and $e$: $$\exists a, b \in \mathbb{N}$$ such that $$ \gcd(a, b) = d$$ and $$\operatorname{lcm}(a, b) = e$$ if and only if $$d \mid e$$ I think I have ...
1
vote
1answer
104 views

GCD of 3 numbers, finding s, t, u

I have to find the values s, u, t from GCD(88,99,111) = 88s + 99t + 111u I know the GCD of this equation is 1 but I dont understand what it means by finding the values of s, t and u. Can someone ...
1
vote
1answer
69 views

3 proofs: If an integer divides both $a$ and $b$, then it also divides $\text{gcd}(a,b)$.

Algebra by Michael Artin Prop $2.3.5$ $1.$ Please check my understanding of the $2$ proofs of $(b)$ (If an integer $e$ divides both $a$ and $b$, it also divides $d$.) presented Proof $1$: (I ...
1
vote
1answer
96 views

Prove $\mathbb Z \gcd(a,b)=\mathbb Z a + \mathbb Z b$ without conclusion of Bézout's identity to define $\gcd$ similar to $\text{lcm}$

Algebra by Michael Artin Prop 2.3.5, on $\gcd(a,b)$ I previously attempted to prove the converse of Prop 2.3.8, where Prop 2.3.8 is the analogue of Prop 2.3.5 for $\text{lcm}(a,b)$. Now, I ...