The Stack Overflow podcast is back! Listen to an interview with our new CEO.

Questions tagged [coprime]

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

120 questions
Filter by
Sorted by
Tagged with
22 views

Given d = gcd(c,n), why there exists relatively prime integers r and s, such that c = rd and n = sd [duplicate]

Given $d = gcd(c,n)$, why there exist relatively prime integers r and s, such that $c = rd$ and $n = sd$?
35 views

How to find the number of coprime numbers to $100$?

Is there a way to find the number of coprime numbers ($2$ digit numbers) to $100$ without writing them?
41 views

Number Theory Question: If $m$ and $n$ are coprime, prove $m| (x-a)$ and $n | (x-b)$

I have this math problem I'm struggling to solve. If $m$ and $n$ are co-prime, prove $m|(x-a)$ and $n|(x-b)$ for some $x\in\mathbb{Z}$ and all $a ,b\in\mathbb{Z}$ Thank you!
30 views

By Fundamental Theorem of Arithmetic : Proof of coprime integers [duplicate]

I want to make use of the Fundamental Theorem of Arithmetic to show the following statement: If gcd$(a,b) = d \Rightarrow (a/d, b/d) = 1$. I already know how to show this differently, but I am still ...
32 views

relatively coprime numbers with a square product [duplicate]

How can I show if $x_1,x_2,x_3, ... \in \mathbb{Z}_{>0}$ are relatively coprime and their product is a square, that this implies that each $x_i$ is a square, too ? Thank you very much.
70 views

Find the thousandth number in the sequence of numbers relatively prime to $105$.

Suppose that all positive integers which are relatively prime to $105$ are arranged into a increasing sequence: $a_1 , a_2 , a_3, . . . .$ Evaluate $a_{1000}$ By inclusion exclusion principle I ...
34 views

Stuck on Consecutive Moduli Selection (Residue Number System)

I'm preparing for my final year project in school and i plan on working on the implementation of Residue Number System in Image Processing. I found this thesis online by Pallab Maji here: http://...
112 views

to find co-prime with 7 from [-10,10]

How many integers in [-10,10] are co-prime with 7? I find that prime belongs to N, so my answer is 9(1,2,3,4,5,6,8,9,10). can you give me advice?
49 views

Showing that $\frac{(m+n-1)!}{m!n!}\in\mathbb{Z}$, if $m,n$ coprime (homework problem) [duplicate]

My attempt: assume $m> n$. Since $\binom{x}{y}\in\mathbb{Z}$ for every $x\geq y$, we have that $$K:=\binom{m+n-1}{n}=\frac{(m+n-1)!}{(m-1)!n!}\in\mathbb{Z}$$ It remains to show that $m|K$. I know ...
33 views

On the co-primality of bracelet-type binary numbers

Let an integer N be the number of digits imprinted on a bracelet, which can come in two values, 1 and 0. You can produce a binary number by writing down the 1's and 0's on the bracelet from left to ...
76 views

Divisibility and number theory in terms of a and b

Are there infinitely many pairs of $(a, b)$ of relatively prime integers $a > 1$ and $b > 1$ such that $a^b+b^a$ is divisible by $a+b$? I've spent almost two hours on this question to no avail. ...
45 views