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
1answer
847 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$ ...
2
votes
2answers
81 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
112 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
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 ...
4
votes
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 ...
3
votes
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?
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 ...
1
vote
2answers
199 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 ...
0
votes
3answers
29 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 ...
0
votes
2answers
113 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 ...