Questions tagged [coprime]
Use this tag for questions related to integers such that the only positive integer that divides them is 1.
0
votes
0answers
10 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^...
3
votes
2answers
122 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
146 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
56 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
43 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
124 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
46 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 ...
1
vote
2answers
66 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
24 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
28 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
26 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
22 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
58 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
1answer
106 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
29 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
30 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
56 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 ...
0
votes
1answer
32 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
21 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
87 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
45 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
57 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
700 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
84 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
82 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
60 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
31 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
74 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 ...
0
votes
3answers
1k 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
28 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
59 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
42 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
42 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 ...
0
votes
0answers
32 views
Miller-Rabin nonwitnesses are relatively prime to n
Let n be odd. Write $n-1=2^{e}k$. Let $a\in\{1,...,n-1\}$ be a Miller-Rabin nonwitness: that is, $a^{k}\equiv1\,(mod\,n) $ or $a^{2^{i}k}\equiv-1\,(mod\,n)$ for some $i\in\{0,...,e-1\}$.
Can I ...
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
74 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
38 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
91 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
2k 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
137 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
30 views
Is there an elegant Stern Brocot like way to generate all coprime triples?
As one might know, the Stern Brocot tree elegantly as well as 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 ...
0
votes
2answers
43 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$
...
0
votes
0answers
51 views
Coprime Polynomials
I would like to know if there is a nice way to show that the following two polynomials are coprime:
$$
f_{n-1}(x)=\sum_{q=0}^{n-1}\sum_{m=0}^{q}{n-1 \choose 2q+1}{q \choose m}x^{n-2-2m}(-4)^m\\
f_{n-...
