Questions tagged [coprime]

Use this tag for questions related to integers such that the only positive integer that divides them is 1.

101 questions
733 views

If $2$ numbers are co-prime, does it imply that their difference is also prime to those numbers?

Let $q$ and $p$ be coprime. And without loss of generality, as $p$ and $q$ are interchangeable, let $p>q$, $p=q+d$. If $p$ and $q$ are coprime, the fraction cannot be simplified. Therefore, we can ...
100 views

Disprove: If $\gcd(n,2^n-1)=1$, then $2^n-1$ is squarefree.

Disprove: If $\gcd(n,2^n-1)=1$, then $2^n-1$ is squarefree. Equivalently, if $2^n-1$ is not squarefree, then $\gcd(n,2^n-1)\neq 1.$ Exercise, which I do,says to show that statement above is false. I ...
87 views

253 views

CoPrimes of Large Numbers

If I have Large Number, and I want to find all possible CoPrime numbers for it, including Large Numbers above it, inside a certain set...how do I do that? I can only seem to find ways to find ...
58 views

Relatively prime numbers are prime

The problem is to find all numbers $n$ such that all numbers $k>1$ smaller than $n$ and coprime with $n$ are prime.
82 views

Prove sum of numerators is coprime with denominator obtained by lcm

Say I have two rational numbers $a/b$ and $c/d$ where $a,b,c,d$ are integers and $a<b$ and $c<d$, and $a$ coprime with $b$, and $c$ coprime with $d$. Assume $b,d$ are free and not necessarily ...
98 views

Prove sum of numerators is coprime with denominator

Say I have two rational numbers $a/b$ and $c/d$ where $a,b,c,d$ are integers and $a<b$ and $c<d$, and $a$ coprime with $b$, and $c$ coprime with $d$. Assume $b,d$ are free and not necessarily ...
80 views

Probability that two positive integers are coprime given their congruence classes modulo $q$

Choose integers $q \ge 1$, $1 \le z_1,z_2 \le q$, and let $x_1,x_2$ be randomly chosen positive integers with the restriction that $x_1 \equiv z_1 \pmod q$ and $x_2 \equiv z_2 \pmod q$. What is the ...
51 views

Prove that if $P(a, b) = 1$ for any polynomial $P(a, b)$ with integer coefficients, then $\gcd(a, b) = 1$

Let $P(a, b)$, be a polynomial with monomials all degree $1$ or higher and integer coefficients (in other words, there are no constant terms). Prove that if $P(a, b) = 1$ (when replacing $a$ and $b$ ...
761 views

How many numbers less than $m$ and relatively prime to $n$, where $m>n$?

Let $m$ and $n$ be two integers such that $m>n$. Then find the number of integers less than $m$ and relatively prime to $n$. I had come across a problem of this type with specific values for $m$ ...
101 views

Show that for $x,y,z\in\mathbb{Z}$, if $x$ and $y$ are coprime, then $\exists n\in\mathbb{Z}$ such that $z$ and $y+xn$ are coprime.

Show that for $x,y,z\in\mathbb{Z}$, if $x$ and $y$ are coprime and $z$ is nonzero, then $\exists n\in\mathbb{Z}$ such that $z$ and $y+xn$ are coprime. Not sure where to start on this one. I ...
61 views

Let $a,b\in G$ for a group $G$ with $|a| = m$ and $|b| = n$. Prove that if $(m, n)=1$, then $\langle a\rangle\cap\langle b\rangle = \{e\}$.

Let $a$ and $b$ be elements of a group $G$ with $|a| = m$ and $|b| = n$. Prove that if $m$ and $n$ are relatively prime, then $\langle a\rangle\cap\langle b\rangle = \{e\}$.
Say I want to generate all coprime pairs ($a,b$) where no $a$ exceeds $A$ and no $b$ exceeds $B$. Is there an efficient way to do this?
If $(a,b)=1$ then prove $(a+b, ab)=1$.
Let $a$ and $b$ be two integers such that $\left(a,b\right) = 1$. Prove that $\left(a+b, ab\right) = 1$. $(a,b)=1$ means $a$ and $b$ have no prime factors in common $ab$ is simply the product of ...