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
42 views

Number of integers $n$ between 1 and 1000 such that the HCF of $n$ and $36$ is 1

How many integers $n$ are there such that $1< n < 1000$ and the highest common factor of $n$ and $36$ is $1$? I have tried counting the prime numbers up to $1000$ using the prime-counting ...
-2
votes
0answers
27 views

Highest Common Factor with an unknown number [on hold]

The highest common factor of n is less than 36, what are the possible values of n
0
votes
1answer
37 views

Number of nonnegative solutions of equation ax+by=n

If $a,b$ are natural numbers and $\gcd(a,b) = 1$ then number of nonnegative solutions of equation $ax+by=n$ is equal to $\lfloor $$\frac{n}{ab}$$ \rfloor$ or $\lfloor $$\frac{n}{ab}$$ \rfloor$ + 1 ...
1
vote
1answer
29 views

Confusion: Man crossing a stream without current and with current.

I have two seemingly contradictory lines in my book regarding crossing a stream. Point IV below says the time to cross over to the other side doesn't change if there is a current as the increased ...
2
votes
4answers
66 views

$a, b, c, d$ are fixed positive integers. If $(ad - bc) \mid a$ and $(ad - bc) \mid c$, show that $\gcd(an + b, cn + d)= 1$ for any $n \in \mathbb{N}$

I've tried a couple of things trying to solve this problem but I get no answer. These are one of the few things I know about “Gcd” and division: If $a\mid b$ and $a \mid c$, then $a \mid b \cdot x + ...
0
votes
1answer
20 views

In $\mathbb Z_n$ prove that $\langle h,k\rangle = \langle\gcd(h,k,n)\rangle$

In $\mathbb Z_n$ prove that $$\langle h,k\rangle = \langle\gcd(h,k,n)\rangle$$ where $h,k \in \mathbb Z_n$. I can prove that in $\mathbb Z$,$$\langle h,k\rangle = \langle\gcd(h,k)\rangle$$ using ...
1
vote
2answers
218 views

Numbers which cannot be formed

We are given two numbers $a,b$ such that $a<b$. Now we have a set $\{a,a+1,a+2,\ldots, b\}$ (all number between a and b including them). Then, we have to find how many numbers cannot be formed from ...
-1
votes
0answers
36 views

What is the proof of Bezout's identity. [duplicate]

Bezout's theorem is stated as- Let $a$ and $b$ be integers with greatest common divisor $d$. Then, there exist integers $x$ and $y$ such that $ax + by = d$.
2
votes
0answers
100 views

Condition for the sum of two fractions to be irreducible

Let $\frac{a}{b}$ and $\frac{e}{f}$ be two rationals where all parameters are positive integers and are in their lowest terms and let $\gcd(b,f) = g$. As an intermediate step in one of the problems I ...
-1
votes
1answer
32 views

Using GCD to find unknown value

Given the equation: $ k = a(b-f) - ag$ If : a, b and f is unknown k is known ag is known a(b-f) is known Can we find what a is?
3
votes
3answers
112 views

Greatest common divisor proof attempt

I am trying to prove the following assertion: "If $a$ and $b$ are odd, then $(2a,2b)=(a+b, a-b)$". $(x,y)$ denotes the greatest common divisor of $x$ and $y$. I am trying to prove it by showing ...
0
votes
0answers
28 views

Find the inverse using fast exponential algorithm or Extended Euclidean Algorithm

How to find the inverse of 35721 mod 1823 which one should do first fast exponential algorithm or Extended Euclidean Algorithm?? How do get started?? Which value should use for fast exponential ...
2
votes
1answer
20 views

How to complete a primitive vector to a unimodular matrix

I would like to understand the following relation between unimodular matrices and its columns in some sense: if $x$ is a primitive vector (that is to say an integer column of $n$ rows whose entries ...
0
votes
1answer
18 views

Number of functions satisfying $lcm(f(n), n) - hcf(f(n), n)<5$? [duplicate]

How many functions f:N→N satisfy - $$lcm(f(n), n) - hcf(f(n), n)<5?$$ $Attempt$ At first I tried to use the property that → LCM*HCF=Product of the two numbers Hence I got $$lcm.hcf=n.f(n)$$ ...
1
vote
1answer
31 views

Prove that if $a,m,n \in \mathbb{Z}^+$ and $m \ne n$ then $\gcd(a^{2^m}+1,a^{2^n}+1)$ is 1 if a is even and 2 if a is odd. [duplicate]

I know that if a pime q|a^2^m+1 and q divides a^2^n+1 then q divides their sum and difference but i don't know how to proceed further. please help
2
votes
1answer
23 views

Old bell rang problem with different starting time

Suppose two bells rang at particular intervals but starting from a different time. First time when it will ring together is ? e.g., First bell starts at 3, and repeats at regular interval of 5. Second ...
-2
votes
1answer
47 views

If gcd$(a,b)=$1 and $p$ is a odd prime then show that gcd$\left(a+b,\frac{a^p+b^p}{a+b}\right)=1$ [closed]

I only know the expansion of $a^p+b^p=(a+b)(a^p-1 -a^p-2×b^1......b^p-1)$ but I don't know how to proceed furthur.thankhs in advance.
5
votes
1answer
84 views

Frequency of integers $x, x+2$ such that gcd$\left(x(x+2),p\right)=1$

Let: $p\ge 5$ be a prime. $p\#$ be the primorial of $p$. $0 < x < p\#$ be an integer. gcd$(a,b)$ be the greatest common divisor of $a$ and $b$. It is straight forward to show that there are $\...
0
votes
0answers
32 views

GCD of two ring elements in $\mathbb{Z}[\sqrt{d}]$

Having found a gcd, $d=\gcd(a,b)$ of two ring elements, $a$ and $b$, in $\mathbb{Z}[\sqrt{d}]$, what is the process to express the gcd, $d$ as $d=ax+by$, where $x, y$ are also ring elements?
1
vote
1answer
46 views

Is maximizing an LCM equivalent to minimizing a GCD?

I'm working on a programming problem here: https://codeforces.com/problemset/problem/235/A Find an algorithm to solve the question: Given $1\leq n\leq 10^6,$ return the largest value of $\...
1
vote
2answers
24 views

Greatest common factors and least common multiples GCSE exam question

Amber wants to tile her bathroom. It measures 1.2m by 2.16m. She finds square tiles with side length 10cm, 12cm or 18cm. Which of these tiles will fit the wall exactly? How can I use GCF and LCM to ...
1
vote
1answer
30 views

For relatively prime integers x and y, what are all possible values for gcd(7x−y, x+ 2y)?

I would like some help on the problem above, it is a part of a school problem set but I'm having a bit of trouble with the explanation for it. The question is as follows: Suppose x and y are ...
1
vote
1answer
48 views

Find the $\gcd(x^m+ a^m,x^n+a^n) $

I really need help with this problem. I think I should take first $d=\gcd(m,n)$ But I don't know how to use this fact. I would really appreciate some help
1
vote
2answers
41 views

How to compute gcd of two polynomials efficiently

I have two polynomials $A=x^4+x^2+1$ And $B=x^4-x^2-2x-1$ I need to compute the gcd of $A$ and $B$ but when I do the regular Euclidean way I get fractions and it gets confusing, are you somehow able ...
0
votes
1answer
34 views

Without using the Euclidean algorithm, show that in $\mathbb{Z}[i]$ for $x,y \in \mathbb{Z}$ s.t $x^2+9 = y^3$, $x+3i$ and $x-3i$ are relative prime.

I began by assuming there is a $d \in \mathbb{Z}[i]$ (with the goal that $d$ must be a unit) such that: $d|x+3i$ , $d|x-3i$. Which gives, $x+3i = \lambda d, (\lambda \in \mathbb{Z}[i]) $ $x-3i = ...
1
vote
2answers
29 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 $\...
1
vote
2answers
32 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
14 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
38 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
44 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
29 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
16 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
24 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
29 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
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
40 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
44 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
69 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
35 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
49 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
47 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
74 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
43 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
25 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
53 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
98 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
41 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 ...