Questions tagged [coprime]
Use this tag for questions related to integers such that the only positive integer that divides them is 1.
2
votes
2answers
45 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?
2
votes
3answers
31 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
41 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
22 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
45 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$?
0
votes
2answers
44 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
76 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 ...
1
vote
1answer
29 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
93 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
29 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
31 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 \...
-1
votes
2answers
46 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 $𝑔𝑐𝑑(𝑘...
2
votes
3answers
104 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
60 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
89 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
12 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
188 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
155 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
137 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
77 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
129 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 ...
0
votes
1answer
49 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 ...
2
votes
2answers
72 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
0answers
25 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
$$...
7
votes
2answers
77 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
0answers
31 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
30 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
25 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
15 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
64 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 ...
7
votes
2answers
124 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
1answer
31 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
34 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
79 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 ...
1
vote
1answer
38 views
Partitioning a number into set of coprimes such that their product is maximum and sum of partition is the number itself [duplicate]
Example 1)
Let the number be 7. Then we have a set {3,4}, so the product of the numbers is 10 and the numbers are mutually coprime.
Example 2)
for n=12, coprimes set = {3,4,5}, where product is 60 ...
0
votes
1answer
22 views
Probability that $n$ integers sampled from $\{0,1,\dotsc,p-1\}$ are coprime is at least $1-p/2^n$.
I'm trying to prove the following:
Given the set of integers $S = \{0,1,\dotsc,p-1\}$, where $p\ge2$. If $n$ integers are sampled uniformly at random from $S$, then the set of sampled integers is ...
0
votes
1answer
28 views
Can i find largest sequence of multiples of given n positive greater than 1 integers?
Suppose i have $n$ positive $q_i>1, i\in\{1,2\dots n\}$ integers. The multiples of these $q_i>1$ integers form sequences on number line with length $l\geqslant1$. My question is: Is it possible, ...
4
votes
1answer
40 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'...
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}...
-1
votes
2answers
46 views
The expected value of $C$ is equal to $\frac{a}{b}$ for coprime positive integers $a$ and $b.$ What is $a+b?$
A fair, $6$-sided die is rolled $20$ times, and the sequence of the rolls is recorded.
$C$ is the number of times in the 20-number sequence that a subsequence (of any length from one to six) of rolls ...
1
vote
5answers
60 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,...
6
votes
2answers
714 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
94 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
84 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
93 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
78 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 ...
