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.

121 questions
Filter by
Sorted by
Tagged with
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}$$ ...
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 ...
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 ...
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?
90 views

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

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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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?
89 views

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 ...
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 ...
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 ...
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$ ...
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]$. ...
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$ ...
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 ...
29 views

83 views

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 + ... 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 ... 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 ... 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 ... 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,$...
The problem is to find all numbers $n$ such that all numbers $k>1$ smaller than $n$ and coprime with $n$ are prime.