Questions tagged [coprime]

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

5
votes
1answer
96 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'...
1
vote
1answer
761 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$ ...
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
1answer
32 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} $...
5
votes
0answers
81 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$. ...
3
votes
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 ...
2
votes
0answers
97 views

Prime Labeling of Caterpillars

Does a prime labeling exist for all caterpillars, which are trees with every vertex being at most distance 1 from a central path? By a prime labeling, we mean a way to label the n vertices with the ...
1
vote
0answers
32 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
0answers
38 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\...
1
vote
0answers
17 views

Equivalent Sets of Complex Exponentials

For integers $L$ and $M$ greater than $1,$ prove that the following sets are equivalent if and only if $L$ and $M$ are coprime. $$\bigg\{\large e^{\big(\tfrac{-i\text{ }2\pi \text{ }k}{L}\big)}\bigg\...
1
vote
0answers
41 views

Coprime sum triplets

a+b+c=20 If a,b,c are coprime natural numbers to each other find number of triplets (a,b,c) ? Apart from manual counting what formula can we derive for such problem ?
0
votes
0answers
27 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) = \...
0
votes
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 $...
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^...
0
votes
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 $$...
0
votes
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$...
0
votes
0answers
253 views

CoPrimes of Large Numbers

If I have Large Number, and I want to find all possible CoPrime numbers for it, including Large Numbers above it, inside a certain set...how do I do that? I can only seem to find ways to find ...