Episode #125 of the Stack Overflow podcast is here. We talk Tilde Club and mechanical keyboards. Listen now

Questions tagged [coprime]

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

Filter by
Sorted by
Tagged with
14
votes
3answers
210 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}$$ ...
11
votes
2answers
9k views

How many numbers in a given range are coprime to $N$?

Is there a good algorithm for counting the numbers $x$ between $A$ and $B$ with $x$ and $N$ coprime? This is just like this question except for the range. The factorization of $N$ is known. I ...
10
votes
14answers
6k 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 ...
10
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?
7
votes
2answers
90 views

Find all $n$ such that $\gcd(3n-4, n^2+1)=1$

I need to find all $n\in\mathbb{Z}$ so that $3n-4$ and $n^2+1$ would be coprime numbers. I was thinking about using Euclidean algorithm - if two numbers $a$ and $b$ are coprime, then exist integers $...
7
votes
2answers
128 views

Relation between primeness and co-primeness of integers

I wonder what this stunning formal analogy between the definitions of being co-prime (for two integers) and being prime (for one integer) might reveal – and how: $\alpha, \beta$ are co-prime ...
6
votes
2answers
756 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 ...
5
votes
4answers
95 views

Proving that $5^n+6^n$ and $5^{n+1}+6^{n+1}$ are coprime for all $n \in \mathbb{N}^*$

I need to prove, using Bézout's identity, that $5^n+6^n$ and $5^{n+1}+6^{n+1}$ are coprime for all $n \in \mathbb{N}^*$. I know that if they are coprime there exist $u,v \in \mathbb{Z}$ such that: $u(...
5
votes
2answers
76 views

Divisibility and number theory in terms of a and b

Are there infinitely many pairs of $(a, b)$ of relatively prime integers $a > 1$ and $b > 1$ such that $a^b+b^a$ is divisible by $a+b$? I've spent almost two hours on this question to no avail. ...
5
votes
2answers
71 views

Find the thousandth number in the sequence of numbers relatively prime to $105$.

Suppose that all positive integers which are relatively prime to $105$ are arranged into a increasing sequence: $a_1 , a_2 , a_3, . . . .$ Evaluate $a_{1000}$ By inclusion exclusion principle I ...
5
votes
1answer
97 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 ...
5
votes
3answers
143 views

Prove that for all $n$ $\gcd(n, x_n)=1$, given $x_{n+1}=2(x_n)^2-1$ and $x_1=2$

I have a sequence $x_{n+1} = 2(x_n)^2-1$; first values are $2, 7, 97, 18817,\dots$ I noticed that if prime $p$ divides $x_n$, then $x_{n+1} \equiv -1\pmod p$ and for all $k>n+1$, $x_k\equiv 1\pmod ...
5
votes
2answers
83 views

Calculate the sum of fractionals

Let $n \gt 1$ an integer. Calculate the sum: $$\sum_{1 \le p \lt q \le n} \frac 1 {pq} $$ where $p, q$ are co-prime such that $p + q > n$. Calculating the sum for several small $n$ value I found ...
5
votes
1answer
104 views

Power of coprime numbers

I would like to prove that $\gcd(a,b) = 1$ implies that for any $i,j$ in N, $\gcd(a^{i},b^{i}) = 1$, without using the factorization in prime numbers. With the factorization it is very easy (you don'...
5
votes
0answers
84 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$. ...
4
votes
5answers
88 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}...
4
votes
2answers
332 views

Prove two numbers are coprime

I encountered some other problem and I found a beautiful proof here Write $1/1 + 1/2 + ...1/ (p-1)=a/b$ with $(a,b)=1$. Show that $p^2 \mid a$ if $p\geq 5$. (see Thomas Andrew's post) But I thought ...
4
votes
2answers
106 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 ...
4
votes
4answers
145 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 ...
4
votes
1answer
58 views

What is the probability that 2 integers have a greatest common factor of 2?

If we pick any two positive integers at random, what is the probability that their greatest common factor is 2? I have been wondering about this problem for a while and done some work on it. I started ...
4
votes
1answer
116 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 ...
4
votes
1answer
94 views

Stapled sequences- set of consecutive positive integers such that no one of them is relatively prime with all of the others

A stapled sequence is defined as a set of consecutive positive integers such that no one of them is relatively prime with all of the others. When I first came across this definition, I thought it ...
4
votes
2answers
340 views

$\frac{7x+1}2, \frac{7x+2}3, \frac{7x+3}4, \ldots ,\frac{7x+2016}{2017}$ are reduced fractions for integers $x\in(0,301)$. [closed]

BdMO 2017 junior catagory Question 7. $$\dfrac{7x+1}2, \dfrac{7x+2}3, \dfrac{7x+3}4, \ldots ,\dfrac{7x+2016}{2017}$$ Here $x$ is a positive integer and $x < 301$. For some values of $x$ it is ...
3
votes
2answers
115 views

Count Integers Not Greater Than $a$ Coprime To $b$

I'd like to ask how to count $f(a,b)$, the number of integers not greater than $a$ which are coprime to a given number $b$. Can $f$ be expressed using Euler's totient function?
3
votes
2answers
89 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=...
3
votes
1answer
316 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 ...
3
votes
1answer
86 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 ...
3
votes
1answer
67 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 ...
3
votes
1answer
44 views

Solving coupled modular equations over the integers with general coefficients

I have encountered a problem in my research that requires solving two coupled modular equations for integers x,y for general integral coefficients. As someone without much experience in discrete math, ...
3
votes
5answers
173 views

Greatest number that divides $x$ and is coprime with $y$

Given two numbers $x \gt 0$ and $y \gt 0$, find the greatest number $a$ such that $a\mid x$, and $a$ and $y$ are $coprimes$. A possible solution is given here. The idea is to divide $x$ with $\gcd(x,...
3
votes
0answers
40 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 ...
2
votes
3answers
115 views

Proving that the elements of a sequence will always be co-prime to each other.

We are given the sequence $k$n = 6$^{{({2}^n)}}$ + 1. We must prove that the elements of this sequence are pairwise co-prime, i.e prove that if m $\neq$ n then $gcd$($k$m,$k$n) = $1$. I have proved ...
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 ...
2
votes
1answer
232 views

Proving That Consecutive Fibonacci Numbers are Relatively Prime

The Problem: Prove that consecutive Fibonacci numbers are relatively prime. I have seen proofs where people use induction and show that if $\gcd(F_n, F_{n+1})=1$, then $\gcd(F_{n+1}, F_{n+2})=1$ ...
2
votes
2answers
87 views

Cycle structure of the permutation $x \mapsto p·x\operatorname{mod}q$ for coprime $p,q$

Let $[q] = \{0,\dots,q-1\}$, $p < q$. Consider the function $\mathbf{p}: [q] \rightarrow [q]$ which sends $x \mapsto p·x\operatorname{mod}q$, i.e. the multiplication by $p$ modulo $q$ on $[q]$. ...
2
votes
1answer
994 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$ ...
2
votes
1answer
97 views

Showing that two binomials are relatively prime for all positive integers (Euclidean ?)

Show that $3x+11$ and $5x+18$ are relatively prime for all positive integers $x$. Hi everyone I've looked around a lot and found similar questions like this here but when trying some of the tips I ...
2
votes
3answers
29 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 & ...
2
votes
0answers
34 views

Stuck on Consecutive Moduli Selection (Residue Number System)

I'm preparing for my final year project in school and i plan on working on the implementation of Residue Number System in Image Processing. I found this thesis online by Pallab Maji here: http://...
2
votes
0answers
92 views

Minimum size of a maximal set of coprime numbers in a finite sequence of consecutive integers

Given any positive integers $n$ and $k$, consider the finite sequence of consecutive integers $n, n+1, \dotsc, n+k-1$, denoted by the interval $[n,n+k-1]$. We would like to find a maximal subset $\{...
2
votes
4answers
83 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 + ...
2
votes
0answers
103 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
2answers
49 views

Showing that $\frac{(m+n-1)!}{m!n!}\in\mathbb{Z}$, if $m,n$ coprime (homework problem) [duplicate]

My attempt: assume $m> n$. Since $\binom{x}{y}\in\mathbb{Z}$ for every $x\geq y$, we have that $$K:=\binom{m+n-1}{n}=\frac{(m+n-1)!}{(m-1)!n!}\in\mathbb{Z}$$ It remains to show that $m|K$. I know ...
1
vote
1answer
62 views

If $x^3, y^3$ commute for all $x, y\in G$, show that $H=\{h\in G|(|h|,3)=1\}$ is an abelian subgroup of $G$. What happens if $3\mapsto n\in\Bbb N$?

If this question is too broad, then I'm sorry. This appears to be new to MSE. I'm reading "Contemporary Abstract Algebra," by Gallian. This is Exercise 44 of the supplementary exercises for ...
1
vote
2answers
55 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, $...
1
vote
1answer
60 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
2answers
41 views

Extension on my one of previous questions about each element in a sequence being coprime. [duplicate]

So my previous question states that: We are given the sequence $𝑘_{n}= 6^{({2}^n)} + 1$. We must prove that the elements of this sequence are pairwise co-prime, i.e prove that if m ≠ n then $𝑔𝑐𝑑(𝑘...
1
vote
2answers
211 views

Sequence of N numbers

We are given a number $N$ such that $3 \leq N \leq 50000,$ and we have to find a sequence consisting of $N$ numbers, where: All numbers are distinct; All numbers lie between $1$ to $10^{19}$; Two ...
1
vote
1answer
62 views

Is there at least one pair from $a, b, c$ that is coprime?

I have encountered a question asked by my friend, which is stated as follows: Suppose there exists integers a, b, c, k, l, m such that $ka+lb+mc=1$, then, is the following statement true? "There ...
1
vote
1answer
33 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,...