Questions tagged [coprime]

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

Filter by
Sorted by
Tagged with
10
votes
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 ...
14
votes
3answers
210 views

Is there any similar solutions including $\pi$ like $1-\frac{1}{2}+\frac{1}{4}-\frac{1}{5}+\cdots=\frac{\pi}{3\sqrt{3}}$?

First equation is very popular - there are only odd numbers. Other words, numbers, which are coprime with $2$. $$1-\frac{1}{3}+\frac{1}{5}-\frac{1}{7}+\frac{1}{9}-\frac{1}{7}+\cdots=\frac{\pi}{4}$$ ...
7
votes
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 ...
2
votes
2answers
80 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]$. ...
2
votes
3answers
111 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 ...
5
votes
3answers
132 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 ...
3
votes
2answers
97 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
2answers
192 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 ...
1
vote
1answer
84 views

Prove sum of numerators is coprime with denominator obtained by lcm

Say I have two rational numbers $a/b$ and $c/d$ where $a,b,c,d$ are integers and $a<b$ and $c<d$, and $a$ coprime with $b$, and $c$ coprime with $d$. Assume $b,d$ are free and not necessarily ...
0
votes
2answers
112 views

$C_m \times C_n$ isomorphic to $C_{mn}$

Let $m, \, n$ be coprime integers. (a) Let $G$ be an abelian group containing elements of orders $m$ and $n$. Prove that $G$ contains an element of order $mn$. (b) Deduce from part (a) that the ...