Questions tagged [coprime]
Use this tag for questions related to integers such that the only positive integer that divides them is 1.
120
questions
-1
votes
2answers
22 views
Given d = gcd(c,n), why there exists relatively prime integers r and s, such that c = rd and n = sd [duplicate]
Given $d = gcd(c,n)$, why there exist relatively prime integers r and s, such that $c = rd$ and $n = sd$?
-1
votes
2answers
35 views
How to find the number of coprime numbers to $100$?
Is there a way to find the number of coprime numbers ($2$ digit numbers) to $100$ without writing them?
0
votes
0answers
41 views
Number Theory Question: If $m$ and $n$ are coprime, prove $m| (x-a)$ and $n | (x-b)$
I have this math problem I'm struggling to solve.
If $m$ and $n$ are co-prime, prove $m|(x-a)$ and $n|(x-b)$ for some $x\in\mathbb{Z}$ and all $a ,b\in\mathbb{Z}$
Thank you!
0
votes
1answer
30 views
By Fundamental Theorem of Arithmetic : Proof of coprime integers [duplicate]
I want to make use of the Fundamental Theorem of Arithmetic to show the following statement:
If gcd$(a,b) = d \Rightarrow (a/d, b/d) = 1$.
I already know how to show this differently, but I am still ...
0
votes
1answer
32 views
relatively coprime numbers with a square product [duplicate]
How can I show if $x_1,x_2,x_3, ... \in \mathbb{Z}_{>0} $ are relatively coprime and their product is a square, that this implies that each $x_i$ is a square, too ?
Thank you very much.
5
votes
2answers
70 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 ...
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://...
0
votes
0answers
112 views
to find co-prime with 7 from [-10,10]
How many integers in [-10,10] are co-prime with 7?
I find that prime belongs to N, so my answer is 9(1,2,3,4,5,6,8,9,10).
can you give me advice?
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 ...
0
votes
1answer
33 views
On the co-primality of bracelet-type binary numbers
Let an integer N be the number of digits imprinted on a bracelet, which can come in two values, 1 and 0.
You can produce a binary number by writing down the 1's and 0's on the bracelet from left to ...
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. ...
0
votes
1answer
45 views
Are there positive integers $s$ and $t$ such that $a^t - b^s = \pm 1$?
Let $a$, $b$ two coprimes positive integers. The question is: are there positive integers $s$ and $t$ such that
$a^t - b^s = \pm 1$?
Equivalently, if we define $d(a,b) = \min_{t,s > 0}( | a^t - b^...
1
vote
1answer
18 views
Is this condition on three polynomials sufficient for them not being coprime.
Lemma: Let $R$ be an integral domain, $f,g\in R[X]$. The following is a necessary and sufficient condition for $f$ and $g$ not to be coprime: There exist $s,t\in R[X]$ such that $1\le \deg s<\deg g$...
0
votes
0answers
18 views
Given coprime $a$ and $b$, and natural $x$ and $y$, show that the maximum value not attained by $xa+yb$ is $ab-a-b$. [duplicate]
$a$ and $b$ are coprime integers. $x$ and $y$ are natural numbers.
Prove that the maximum value that $xa + yb$ cannot hold is
$ab - a - b$.
0
votes
2answers
53 views
How co prime numbers can be used to form any number beyond a number [duplicate]
Suppose we have two co prime numbers a and b. Then it is always possible to form any number greater than or equal to a*b - a - b +1 by using the given co primes only that is
ax + by
where x and y ...
0
votes
2answers
34 views
Suppose two integers $a,N$, where N is prime, is there a difference between requiring $gcd(a,N)=1$ and $N \not\mid \!\!\;a $?
This is probably painfully obvious but I wanted to confirm if there's any difference between requiring that the $gcd(a,N)=1$ or $N \not\mid \!\!\;a $ if N is prime? That is, could you use either ...
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 ...
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 $\{...
0
votes
1answer
84 views
General formula for the gcd.
It seems there is no closed form for the greatest common divisor of any two given integers.
Why is there no such formula?
Does the only way to compute the gcd is essentially to recursively apply the ...
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 + ...
0
votes
1answer
37 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
331 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
28 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
57 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
28 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
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
2answers
113 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?
1
vote
3answers
47 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
48 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
26 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$?
0
votes
2answers
77 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
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 ...
1
vote
1answer
31 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
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(...
1
vote
1answer
57 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
33 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
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 $𝑔𝑐𝑑(𝑘...
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 ...
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
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 ...
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
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 ...
1
vote
2answers
210 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
230 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
173 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
142 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
58 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
86 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]$.
...
