Questions tagged [coprime]

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

6
votes
2answers
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 ...
4
votes
2answers
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 ...
3
votes
2answers
87 views

Numbers that add to generate any other number

Here I would like to state about the numbers $3$ and $5$,which by the help of addition(any number of times) can generate any number from $8(=5+3)$ on-wards. For example: $9 = 3 + 3 +3$ $10 = 5+5$ $11=...
0
votes
2answers
131 views

Extended Euclidean Algorithm to find 2 POSITIVE Coefficients?

There's a problem I ran into that said: "At a certain casino, blue poker chips are worth 9 dollars and white poker chips are worth 14 dollars. How many chips can Hank buy to spend exactly 206 dollars?...
0
votes
1answer
22 views

Condition for preserving the order of an element in quotient group

Lets say we have a finite group $G$ of order $m = m_{1} \cdot m_{2}$. Suppose we have elements $g_1, g_2 \in G$ such that $o(g_1) = m_1$ and $o(g_2) = m_2$. Let $N = \langle g_1 \rangle$ be a normal ...
1
vote
1answer
32 views

Prove that $(m,n) = (s,n) = 1$ if and only if $(ms,n)=1$

About the notation: Denotes $(a,b)$ the greatest common divisor between $a$ and $b$. Now, about the exercise, what I did was the following: Since $(m, n) = (s, n) = 1$, $ma + nb = sc + nd = 1$ then,...
4
votes
1answer
94 views

Probability of k random integers being coprimes

In this section of the Wikipedia article on coprime integers, it is stated that: More generally, the probability of $k$ randomly chosen integers being coprime is $1/\zeta(k)$. where $\zeta$ is the ...
-1
votes
3answers
2k views

Is the sum of two coprime natural numbers prime?

I am just getting started with some basic number theory and I was wondering: given two coprime natural numbers $a$ and $b$, is it true that $a+b$ is a prime number? My intuition says yes, because two ...
0
votes
1answer
32 views

Abstract solving congruence system when modules are not coprime

The following system is given $X \equiv a_1$ $mod$ $m_1$ $X \equiv a_2$ $mod$ $m_2$ such that $m_1, m_2 \in \mathbb{N} _{>1}$ and $m_1, m_2$ are not coprime. For which $a_1, a_2 \in \mathbb{Z} $...
1
vote
1answer
67 views

What is the probability for which :$\gcd ((\phi(n),n-1)=1 ) $ for integers?

let $n$ be an integer and $\phi$ is The Euler's Totient function. I want to know the probability for which $$\gcd ((\phi(n),n-1)=1 ) $$ I only know if $n$ is a prime number then the probability is 0 ...
0
votes
1answer
48 views

Suppose that $n = p_1p_2 \cdots p_k$, where $p_1, p_2, .\ldots, p_k$ are distinct odd primes. Show that $a^{φ(n)+1} ≡ a\pmod n$

Question: Suppose that $n = p_1p_2 \cdots p_k$, where $p_1, p_2, \ldots , p_k$ are distinct odd primes. Show that $a^{φ(n)+1} ≡ a\pmod n$ So I assume since n contains a bunch of distinct odd primes, ...
0
votes
2answers
47 views

If $ax + by =$ prime, are then $a$ and $b$ relative prime?

I'm stuck on the following question: For $a, b \in \Bbb Z$, assume that $ax + by = 4$ and $as + bt = 7$ for $x, y, s, t \in \Bbb Z$. Show that then $a$ and $b$ are relative prime. The following ...
1
vote
1answer
11 views

The coprimality of 2 integers that are divisors of 2 larger coprimes?

Given an example with $(a,b)=1$ where $a=ux$ and $b=vy$ (with all variables being integers), obviously $(ux,vy) = 1$ directly, but does $(u,v) = 1$ as well? I am pretty sure it should but I am unsure ...
0
votes
2answers
39 views

Problem with discrepancy of results, one of which is close to $\sqrt{\frac{\varphi^5}{5}}$

My simple problem relates with my question about sign-alternating sums of numbers, which opposite to coprime with $m$. $$1-\frac{1}{3}+\frac{1}{7}-\frac{1}{9}+\frac{1}{11}-\frac{1}{13}+\cdots=\frac{\...
5
votes
0answers
81 views

Inequality involving power to fractional part of integer multiples of logarithm of integer to coprime base.

For $x \in \mathbb{R}^+$, let $\{x\} = x - \lfloor x \rfloor$ denote the fractional part of $x$. Let $k \in \mathbb{N}$. Show that $2^{\{k \log_2(3)\}} < \dfrac{2}{1 + 2^{-k}}$ for $k > 1$. ...
2
votes
1answer
22 views

Does $\exists b \in F_n(b^p=a)$ and $\exists c \in F_n(c^q=a)$ imply $\exists d \in F_n(d^{pq}=a)$?

Suppose $F_n$ is a free group of rank $n$, and $a$ is an element of $F_n$, such that $\exists b \in F_n(b^p=a)$ and $\exists c \in F_n(c^q=a)$, where $p$ and $q$ are coprime integers. Does there ...
1
vote
2answers
39 views

Prove co-prime exist [closed]

Firstly: $[a]_m$ means $a \pmod m$ $m$ is co-prime with $n$, $\gcd(m,n)=1$ $[a_1]_{m}$ is coprime with $m$, $\gcd(a_1,m)=1$ $[a_2]_{n}$ is coprime with $n$, $\gcd(a_2,n)=1$ I find $x$ so that $[x]...
0
votes
2answers
112 views

$C_m \times C_n$ isomorphic to $C_{mn}$

Let $m, \, n$ be coprime integers. (a) Let $G$ be an abelian group containing elements of orders $m$ and $n$. Prove that $G$ contains an element of order $mn$. (b) Deduce from part (a) that the ...
1
vote
2answers
3k views

Definition of Coprime

What is the exact definition of coprime? I know that it basically means that there are no common factors, and one is not a multiple of the other. However, i recently learned that 1 is coprime to any ...
-2
votes
4answers
235 views

Show that 5n + 3 and 7n + 4 are relatively prime for any n 2 N. Show that s and t are not unique. [closed]

I know that s = 7 and t = -5, but I'm having trouble showing that they are not unique. I've been just guess and checking, is there a better way to compute this?
3
votes
0answers
39 views

Is there an elegant Stern Brocot like way to generate all coprime triples?

As one might know, the Stern Brocot tree elegantly and compactly models all rational numbers. I am now left wondering if a process like this tree modeling could be done not only for pairs but for ...
0
votes
2answers
79 views

Kernel and image of coprime factors of the minimal polynomial

Let given an operator $T$ with minimum polynomial $m(x)=p(x)q(x)$ such that $\gcd(p(x),q(x))=1$, then $\ker(p(T))= \text{Im}(q(T))$ So far I got $\exists r(x),s(x)$ such that $r(x)p(x)+s(x)q(x)=1$ ...
-1
votes
2answers
999 views

Squares of two coprime numbers [duplicate]

If there are two coprime numbers a and b, then are a^2 and b^2 also coprime ?
1
vote
1answer
38 views

How can we prove $\sum\limits_{n=1}^{k}\frac{f(m,n)}{n}\approx\frac{\varphi(m)}{m}(\ln(k\prod\limits_{p|m}p^{\frac{1}{p-1}})+\gamma)$?

First we need to create a function $$f(m,n)=\begin{cases} 1&\text{if $m,n$ - coprime}\\ 0&\text{otherwise}\\ \end{cases}$$ Then we can be sure, that for large $k$ and $|\mu(m)|=1$ $$\sum\...
14
votes
3answers
209 views

Is there any similar solutions including $\pi$ like $1-\frac{1}{2}+\frac{1}{4}-\frac{1}{5}+\cdots=\frac{\pi}{3\sqrt{3}}$?

First equation is very popular - there are only odd numbers. Other words, numbers, which are coprime with $2$. $$1-\frac{1}{3}+\frac{1}{5}-\frac{1}{7}+\frac{1}{9}-\frac{1}{7}+\cdots=\frac{\pi}{4}$$ ...
1
vote
0answers
17 views

Equivalent Sets of Complex Exponentials

For integers $L$ and $M$ greater than $1,$ prove that the following sets are equivalent if and only if $L$ and $M$ are coprime. $$\bigg\{\large e^{\big(\tfrac{-i\text{ }2\pi \text{ }k}{L}\big)}\bigg\...
0
votes
3answers
46 views

Prove that for any natural $a$ there is a natural $b$ so that $a$ and $b$ are coprime and $a+b^2$ is not a prime

Is there a simple proof of the following statement? For any $a \in N$ exists such $b \in N$ that $a \perp b$ and $a + b^2$ is a composite number.
1
vote
1answer
182 views

number of coprime divisors of n with their difference divisible by 3

For an integer n, how many pairs (a, b) [suppose a is smaller than b] of coprime divisors of n exist such that (b-a) is divisible by 3 ? Advanced version of this question: Let F(n) denote the number ...
1
vote
1answer
45 views

Proof for $gcd(a^x,b^y)=gcd(a,b)^z$ for a,b,x and y positive integers

I noticed that $\gcd(a^x,b^y)=\gcd(a,b)^z$ for a, b, x, y and z positive integers, My question is how to prove that? Additionally assuming the above is correct, when a and b are relatively prime (co-...
2
votes
0answers
97 views

Prime Labeling of Caterpillars

Does a prime labeling exist for all caterpillars, which are trees with every vertex being at most distance 1 from a central path? By a prime labeling, we mean a way to label the n vertices with the ...
1
vote
1answer
530 views

Product of coprimes less than n

I observed that if $n$ has a primitive root then $c_1 \cdot c_2 ... \cdot c_{\phi(n)} \equiv -1 \ mod \ n$ otherwise, $c_1 \cdot c_2 ... \cdot c_{\phi(n)} \equiv 1 \ mod \ n$ where $c_i$'s are ...
0
votes
2answers
76 views

Number Theory - Prove $n^2$ and $n-1$ are coprime

In my foundations of math class we have just finished our section on number theory. I am having a really hard time with the questions involving co-primality, gcd's, and Bezout's identity. The ...
1
vote
0answers
41 views

Coprime sum triplets

a+b+c=20 If a,b,c are coprime natural numbers to each other find number of triplets (a,b,c) ? Apart from manual counting what formula can we derive for such problem ?
0
votes
3answers
215 views

How to show that ab and c are coprime when $(a,c)=(b,c)=1$?

Let $a$, $b$ and $c$ be non-zero integers. Suppose $a$ and $c$ are coprime. And suppose $b$ and $c$ are coprime. How can I then show that $ab$ and $c$ are coprime? From what I know so far this means ...
3
votes
1answer
65 views

If $\cos p\alpha$ and $\cos q\alpha$ are rational with $p,q$ relatively prime, then $\cos \alpha$ is rational, or $\alpha$ is a multiple of $\pi / 6$.

Would you please help me solve Exercise 2, which I repeat here: Suppose that $p$ and $q$ are relatively-prime positive integers. Show that if $\cos p \alpha$ and $\cos q \alpha$ are rational, then ...
1
vote
2answers
52 views

Goldbach Partition - Why Co-Primality?

Any even number $2n$ can be written as the sum of two primes, $p_{a}$ and $p_{b}$. For $n \geq 2$ this is the Goldbach Conjecture. $$ p_{a} + p_{b} = 2n $$ Why are $p_a$ and $2n$ co-prime? That is, $...
5
votes
1answer
95 views

How many numbers $2^n-k$ are prime?

We are all familiar with the Mersenne primes $$M_n = 2^n-1$$ and we indeed know that there are some $M_n$ that are prime. However, it is still open whether there are infinitly many $M_n$ that are ...
3
votes
1answer
235 views

Finding a coprime of a general magnitude.

I have an arbitrary number $x$. I would like to compute a number that is coprime to $x$ that's close(ish) to the square root of $x$. I don't need to find them all, and factoring $x$ is expensive. I ...
2
votes
3answers
28 views

For $x: (1 \to b)$ where $a$ & $b$ are co prime, why is $ax \bmod b$ distinct

So, out of curiosity, I was wondering why $x (1 \to b)$ where $a$ & $b$ are co prime, why is $ax \bmod b$ distinct. For example, let $a = 5$, and $b= 8$: $\begin{array}{c|c|c} x & 5x & ...
0
votes
0answers
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 ...
1
vote
1answer
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.
1
vote
1answer
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 ...
0
votes
1answer
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 ...
3
votes
1answer
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 ...
0
votes
1answer
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$ ...
1
vote
1answer
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$ ...
4
votes
4answers
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 ...
0
votes
2answers
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\}$.
9
votes
2answers
6k views

Generating all coprime pairs within limits

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?
10
votes
14answers
5k views

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