Stack Exchange Network

Stack Exchange network consists of 175 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Questions tagged [coprime]

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

2
votes
4answers
66 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 + ...
3
votes
0answers
36 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
1answer
36 views

Show that a positive integer $n \in N$ can be written as a sum of positive coprime integers with $gcd(a,b)=1 $

My idea was to show this via 3 cases. In case one n is even n=2k, k is odd In case two n is even with n=2k, k is odd In case three n is odd so n=2k+1 Then I have to show that for $n<7$ not every ...
4
votes
2answers
311 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 ...
0
votes
0answers
27 views

The number of coprime integers at most $m$ and $n$

I am trying to estimate the asymptotics of the number $N(m,n)$ of coprime integers where one of the integers is at most $m$ and the other is at most $n$. What I obtained looks as follows: $$ N(m,n) = \...
1
vote
1answer
48 views

Two integers $a$ and $b$ are coprime, is it possible that $a \mid b$?

Let $a$ and $b$ be coprime integers. Is it possible that $a \mid b$? My thinking is that if $a \mid b$ then $a$ and $b$ share a factor besides $\pm 1$ ($a$ itself) and so are not coprime. Thus, $a \...
1
vote
4answers
26 views

Find $X, Y \in \mathbb{Z}$ such that $2^a X + (2^b - 1) Y = 1$ (coprimality)

I've been wrecking my brain trying to solve this exercise. Is this answer wrong? $$X= (2^{a})^{b-1}, Y= (-1) (2^b +1) \ [(2^b -1)(2^b +1)]^{a-1}$$
3
votes
2answers
97 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?
5
votes
1answer
96 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'...
3
votes
1answer
41 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, ...
1
vote
1answer
753 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$ ...
1
vote
3answers
41 views

Let $a, b$ and $n$ be natural numbers. Prove that if $a^n$ and $b^n$ are relatively prime, then $a$ and $b$ are relatively prime.

Let $a, b$ and $n$ be natural numbers. Prove that if $a^n$ and $b^n$ are relatively prime, then $a$ and $b$ are relatively prime. I have been able to prove the above statement by contrapositive in ...
0
votes
1answer
45 views

Sum of the number of relatively prime integers up to $x$, $x-1$, $\ldots$, $1$

If there is a number $x$, and we want to find the sum of the number of relatively prime integers up to $x$, $x-1$, $\dots$ until $1$, is there a formula for this or any way to solve it? Like if the ...
0
votes
0answers
25 views

Complexity of finding a common coprime element

Let $n_1,\ldots,n_u$ denote $u$ positive integers, all of which are bounded above by some integer $N$. Question: 1. How hard is it to find an integer $m$ $(1 < m < N)$ that is coprime to $...
0
votes
1answer
47 views

What happens to $n^{\phi(p)} \equiv 1$ when $n$ and $p$ are not co-prime?

We know $n^{\phi(p)} \equiv 1$ in the case $n$ and $p$ are co-prime i.e. $ gcd(n,p) = 1$. What is the case when they are not co-prime? What happens to $n^{\phi(p)} \equiv 1$?
7
votes
2answers
127 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 ...
0
votes
2answers
58 views

coprime divisibility: is $ax-1$ divisible by $n$? [duplicate]

Suppose that $a,n \in \Bbb Z$ are coprime. Show that there is an integer $x$ such that $ax−1$ is divisible by $n$. I know that $\gcd(a,n)=1$ and feel like that will be used in the proof of this, but ...
5
votes
2answers
80 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 ...
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 ...
2
votes
3answers
109 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 ...
1
vote
1answer
30 views

A not very obvious question about $\{h+tk\}$ sequence.

Let $h$ and $k$ be positive integers such that $\gcd(h,k)=1$. Let $A(h,k)$ be the sequence $$A(h,k)=\{h+kx|x=0,1,2,3,\cdots\}.$$ Let $S$ be a infinite subset of $A(h,k)$, prove that for each positive ...
5
votes
4answers
94 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(...
1
vote
1answer
34 views

Number of integers coprime to a given integer $q$ in some range $[x, x+y]$

I am asked to show that for $1 \leq x,y$ and an integer $q$, we have: $S(x,x+y,q) = |\{x < n \leq x + y \mid n \text{ is comprime to } q\}| = \frac{\phi(q)y}{q} + O(2^{\omega(q)})$, where: $\...
1
vote
0answers
32 views

Show that there exist $a,b \in K [X_1,X_2,\cdots,X_n]$ and $d \in K[X_1,X_2,\cdots,X_{n-1}]$ such that $aF+bG = d.$

Let $K$ be a field. Let $F,G \in K [X_1,X_2,\cdots,X_n]$ be two polynomials which are relatively prime to each other. Show that there exist polynomials $a,b \in K [X_1,X_2,\cdots,X_n]$ and $0 \neq d \...
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 ...
-1
votes
2answers
48 views

How i show this :let $x, y$ are positive integers such that $(x,y)=1$ then $x+y$ and $xy$ are coprime? [duplicate]

I have tried to find any counter example of this claim but i didn't get such one and I have used Gausse Theorem and Bezout to show it but i didn't suceed Is this claim true and how i can show it : ...
1
vote
2answers
39 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
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 ...
4
votes
1answer
93 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 ...
0
votes
2answers
73 views

Let $n\in \mathbb{N}, n > 1$ Show that some numbers are coprimes.

Let $n\in \mathbb{N}, n > 1$. Show that $$\{a^2+a-1,a^3+a^2-1,...\}$$ contains an infinite subset $S$ s. t. every $2$ distinct elements are coprimes. I don't know how to even approach ...
0
votes
0answers
14 views

Average Error as Number of Samples Increases

I made a very simple program that approximates $\pi$ in r, by finding the probability that 2 random generated numbers are coprime for n trials. The result of this probability approaches $\frac{6}{\pi^...
4
votes
2answers
303 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 ...
1
vote
2answers
180 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 ...
2
votes
1answer
191 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$ ...
-1
votes
3answers
109 views

How many positive integers $\le 1260$ are relatively prime to $1260$? [duplicate]

I have no idea how to solve this problem. Is there a general formula to compute the quantity of such numbers?
5
votes
3answers
131 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 ...
2
votes
2answers
77 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]$. ...
0
votes
1answer
51 views

How can I prove that a function $p(n)$ is multiplicative but not completely multiplicative?

How can I prove that a function $p(n)$ is multiplicative but not completely multiplicative? A function $f\colon\mathbb N\to\mathbb C$ is called multiplicative if $f(1)=1$ and $$\gcd(a,b)=1 \implies ...
0
votes
0answers
29 views

Formula for product of sums of pairs of coprime divisors of $n$.

Can we develop a formula for $$ r(n)=\prod_{ \begin{array}{c} x,y\mid n \\ (x,y)=1 \end{array}} (x+y) $$ In words this is the product of sums of all coprime pairs of divisors of $n$. For example $$...
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\}$.
7
votes
2answers
79 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 $...
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
0answers
38 views

Best error term in $\sum_{(n,q)=1}\frac{1}{n}$ (harmonic series with coprimality condition)

It is very well known and not difficult to prove that $\displaystyle\sum_{\substack{0<n\leq X\\ \\(n,q)=1}}\frac{1}{n}=\left(\log(X)+\gamma+\sum_{p|q}\frac{\log(p)}{p-1}\right)\frac{\phi(q)}{q}+O\...
0
votes
0answers
31 views

Defining a set of all possible non-congruent integer values

"Say Peter has discovered that $82$ and $723$ are coprime. He now believes that the equation below has a solution for all possible integer values of $q$. $$82p ≡ q\pmod {723},$$ where $p∈$ $\Bbb Z$...
0
votes
3answers
26 views

Relation $ab=cd$ in $\mathbb{Z}$(UFD) with $a$ and $c$ coprime.

Why if $15x=-19y$ where $x$ and $y$ are integers, this means that there is an integer t such that x=-19t and y=15t. I think it has something to do with the fact that $\mathbb{Z}$ is a UFD, but I can't ...
0
votes
0answers
16 views

Prove that if $a$ and $b$ are coprime and the product $ab$ is some $m$-th power ($m\ge2$), then $a$ and $b$ have to be $m$-th powers. [duplicate]

i.e $ab=c^m$ for some $c\in\mathbb{Z}$, $m\in\mathbb{N}$. So far I have Let $p_1,\dots,p_n,q_1,\dots, q_k$ be primes $$a=p_1^{x_1}\cdot p_2^{x_2}\cdot ... \cdot p_n^{x_n}$$ $$b=q_1^{y_1}\cdot ...
2
votes
1answer
76 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 ...
0
votes
1answer
34 views

If 1 can be a linear integer combination of 3 non zero integers then Is at least one of the three possible pairs coprime?

If a,b and c are non zero integers and that 1 can be written as a linear integer combination of them such that k, m and n are integers and: Ka + mb +nc = 1 then surely by bezouts identity, atleast ...
1
vote
1answer
42 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 ...
0
votes
2answers
115 views

Prove that if $n>1$, the sum of positive integers less than $n$ and coprime to $n$ is $(1/2)na(n)$ where $a(n)$ is the number of such integers. [duplicate]

Question 12(iii) Could anyone explain this part of the question to me. What i tried co-prime means that the two integers a and b are said to be relatively prime, mutually prime, or coprime (also ...