# Questions tagged [coprime]

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

108 questions
Filter by
Sorted by
Tagged with
162 views

### How to prove the following expression

Prove that if it takes you 5 minutes to solve any Sudoku puzzle and 14 minutes to solve a word search, you can completely occupy yourself on any flight of 52 minutes or longer provided that you have a ...
56 views

63 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 ...
77 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 39 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 ... 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 ... 2answers 320 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 ... 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) = \... 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}$$2answers 98 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? 1answer 97 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'... 1answer 42 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, ... 1answer 853 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 ... 3answers 42 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 ... 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 ... 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 ... 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? 2answers 128 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 ... 2answers 61 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 ... 2answers 81 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 ... 4answers 110 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 ... 3answers 112 views ### Proving that the elements of a sequence will always be co-prime to each other. We are given the sequence kn = 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(km,kn) = 1. I have proved ... 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 ... 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(... 1answer 46 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: \... 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 \... 14answers 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 ... 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 𝑔𝑐𝑑(𝑘... 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 ... 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 ... 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 ... 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^... 2answers 326 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 ... 2answers 200 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 ... 1answer 203 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 ... 3answers 131 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? 3answers 136 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 ... 2answers 82 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]. ... 1answer 54 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 ... 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$$... 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\}$. 2answers 85 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$...
The problem is to find all numbers $n$ such that all numbers $k>1$ smaller than $n$ and coprime with $n$ are prime.