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,512 questions
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 ...
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
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 ...
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 ...
66 views

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?
46 views

29 views

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