Questions tagged [coprime]

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

17 questions
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'...
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$ ...
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$?
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}$...
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$. ...
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 ...
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 ...
32 views

17 views

25 views