# Questions tagged [coprime]

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

104 questions
Filter by
Sorted by
Tagged with
30 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 ...
51 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 ...
60 views

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 ...
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 ...
317 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 ...
28 views

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 81 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 ... 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. 0answers 39 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\... 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... 3answers 28 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 ... 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 ...
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 ...