Questions tagged [coprime]
Use this tag for questions related to integers such that the only positive integer that divides them is 1.
233
questions
0
votes
2
answers
187
views
Infinite numbers of coprime pairs $k(6k-1)$.
This question leads to the following consideration.
Are there infinite number of pairs of the form $\big(j(6j-1),\, k(6k−1)\big)$ where $j<k$ such that $j(6j-1)$ and $k(6k−1)$ are coprime? One ...
0
votes
2
answers
23
views
Equivalent integral quadratic forms properly represent the same integers
Definitions:
An integral quadratic form (IQF) is some instance of $f(x,y)=ax^2+bxy+cy^2$, where $a,b,c \in \mathbb{Z}$.
Let $f(x,y),g(x,y)$ denote IQFs. We say $f(x,y)$ and $g(x,y)$ are properly ...
1
vote
1
answer
74
views
PHI function to list relative primes
I am using a website called dcode to input numbers into the PHI function, and then receive an output of numbers relatively prime with my input.
The website, unfortunately, limits output to just 500 ...
0
votes
0
answers
41
views
Expressing any even natural number as a sum of primorials with coefficients
I'm having a hard time trying to solve the following problem:
Given any random even natural number, $x$, prove that it can or cannot be written as the product of some integer, $b$, times the primorial ...
1
vote
1
answer
134
views
Show $\gcd(n, 2^{2^n}+1)=1$ [duplicate]
I am trying to show that $n$ and $2^{2^n}+1$ are coprime for all $n \in \mathbb{N}$. My intuition tells me induction is a good method.
When $n=1$, $\gcd(1, 2^{2^1}+1)=\gcd(1, 5)=1$. Now suppose $\gcd(...
2
votes
2
answers
132
views
Conjecture: Every $n \geq 20 \in \mathbb{N}$ can be written as a sum of three integers $(\geq 2)$ that are pairwise coprime
This question on the sum of pairwise prime numbers piqued my interest, and I started looking at what numbers can be written as the sum of three pairwise coprime numbers (excluding $1$):
$$
\begin{...
0
votes
3
answers
92
views
No infinite arithmetic progression exists with prime numbers
I am trying to prove there is no infinite arithmetic progression involving only prime numbers. (In other words, I want to prove that if $a, b \in \mathbb{N}$, then there exists some $n$ such that $a + ...
0
votes
1
answer
65
views
Show that for all $n$, If $n$ is a multiple of $58$, then $n+7$ and $n^{2}+9$ are coprime.
How do I approach this question? I am unsure of how to use Euclid's algorithm and simultaneously incorporate that $n$ is a multiple of $58$. Thanks!
1
vote
1
answer
58
views
How to prove that the number 6𝑘+2 can be represented as the sum of two coprime numbers? [closed]
$k$ is a natural number. How can I prove that the number $6k+2$ can be represented as a sum of two coprime numbers?
The greatest common divisor of two coprime numbers is $1$:
For integers $m,n$, $\gcd(...
1
vote
0
answers
29
views
Lower bound on number of integers in interval which are coprime to every other integer on interval
Given a set $X = \{x | L \leq x \leq R\ \land\ x \in \mathbb{N}\}$ (and $L\leq R$) I need to find an approximate lower bound on number of integers $a \in X$ such that they are relatively coprime to ...
0
votes
0
answers
89
views
If $a$ and $b$ are coprime then $a+b$ and $ab$ are coprime [duplicate]
Let $(A,+,\cdot)$ be a UFD ring, if $a$,$b$ are coprime then $a+b$ and $ab$ are coprime? [Yes/No]
My attempt:
I thought about it for a while and I guessed it had to be true, to prove it I did it this ...
0
votes
0
answers
24
views
Prove that the set $A(d)=\{m\in\mathbb{Z}|1\leq m\leq n\quad\&\quad gcd(m,n)=d\}$ are pairwise disjoint
Let $n\in\mathbb{Z}_+$ then $n=\sum_{d|n} \phi(d)$, where $\sum_{d|n} $ denotes the sum over all of the divisors of $n$ and $\phi(d)$ is the Euler phi function which gives the number of integers less ...
0
votes
1
answer
41
views
Find the smallest natural number k such that between k different and in pairs relatively prime natural numbers less than 2021 there's a prime number
Find the smallest natural number $k$ such that between $k$ different and in pairs relatively prime natural numbers less than $2021$ there's a prime number.
Honestly have no idea how to start here so ...
0
votes
0
answers
34
views
Property of coprime integer.
I am trying to prove the following elementary property (which I guess should be true):
Given 2 coprime positive integers $a, b$, we have $a\mathbb Z/b\mathbb Z = \mathbb Z/b\mathbb Z.$
Is the ...
2
votes
1
answer
59
views
Rank of a pair of coprime integers
Let's say two pairs of coprime integers $(a, b)$ and $(c, d)$ are connected if $ac + bd = 1$.
A connected chain, or just a chain, is a sequence of coprime pairs in which every two consecutive pairs ...
4
votes
1
answer
113
views
Find the smallest natural number $n$ such that every $n$-element subset of $S=\{1,2,\dots,280\}$ contains $5$ pairwise relatively prime numbers
A friend gave me the following question to solve-
Let $S=\{1,2,\dots ,280\}$. Find the smallest natural number $n$ such that every $n$-element subset of $S$ contains $5$ pairwise relatively prime ...
2
votes
1
answer
62
views
Approximation of a real number via a fraction of coprimes.
I'm reading a paper on number theory (which is not my field at all) stating, without any proof, a claim which can be rephrased as
Fix a positive integer $M$. Then, given any real number $\alpha$, ...
3
votes
0
answers
93
views
The Frobenius Coin Problem (constructive proof)
I am trying to prove the following:
Given $a, b \geq 1$ with gcd$(a,b)=1$. Denote $A:= \{ma+nb$ | $m,n\geq
0\}$. Prove that there exists a largest integer, as a function of
$a,b$, such that it ...
0
votes
0
answers
31
views
Using algebraic expressions to uniquely represent all pairs of coprime nonnegative integers
After a bit of experimentation, I thought of an interesting sequence of algebraic expressions defined recursively as follows:
$F_0 = 0$
$F_1 = 1$
For all integer $n \geq 2$,
$F_n = a_{n-2} F_{n-1} + ...
-1
votes
2
answers
67
views
Intuition Of Bézout's Theorem [duplicate]
I've been wondering for a while now for the intuition of Bézout's theorem.
$ax+by=\gcd(a,b)=d$
$dpx+dqy=d(px+qy)$
Now why there exists pairs of $x$ and $y$ such that $px+qy$ is $1$ ($p$ and $q$ are co-...
-2
votes
2
answers
58
views
Chinese Remainder Theorem when n values are not coprime? [duplicate]
$$ x\equiv 2 \mod 20 $$
$$ x\equiv 7 \mod 15 $$
setting $a \equiv b \mod n$
how would you approach this as the two $n$ values are not coprime?
I've broken down the $ 7\bmod15 $ into $x\equiv 7\mod3$ ...
0
votes
3
answers
46
views
Proving any two elements in recursive sequence are coprime.
A sequence $x_0, x_1, x_2, \ldots$ is defined recursively as follows:
$$x_0 = 3 \\ x_n = 2 + (x_0 \cdot x_1\cdot x_2\cdots x_{n-1})$$
I'm stuck at trying to prove that for any two different elements ...
0
votes
0
answers
18
views
GCD, Coprime and Linear Combination Proof Verification
Can someone please verify the proof below? It seems a bit handwavy. I want to be more formal and explain my reasoning a bit better, but I'm not entirely sure how to do so.
Consider $x,y,z,w \in \...
0
votes
0
answers
30
views
How would I go about solving $11^{112114} \equiv x\pmod {113}$ [duplicate]
I'm studying for an exam, and this is one of the practice questions:
For what number $x \in \{0, 1, 2, ... 112\}$ is the following statement true:
$$11^{112114} \equiv x \pmod{113} $$
I have no ...
0
votes
0
answers
26
views
Infinite set of mutually coprime numbers of the form $P(k)$, $P$ polynomial
Given a polynomial $P$, are there known theorems about the existence of an infinite set of mutually coprime numbers of the form $P(k)$ (with $k \in \mathbb N$), assuming, of course, that $P$ satisfy ...
0
votes
2
answers
137
views
If $\gcd(a,b)\sim 1$, $\gcd(a,c)\sim1$, then $\gcd(a,bc)\sim1$?
In integral domains, prove or give a counterexample:
If $(a,b)\sim 1$, $(a,c)\sim1$, then $(a,bc)\sim1$.
That is to say, if $a,\,b$ are relatively prime and $a,\,c$ are relatively prime, then $a,\,...
4
votes
2
answers
145
views
Reformulation of Fundamental Theorem of Arithmetic
My book claims the following.
The fact that for coprime numbers $a$ and $b$ there exists integers $x$ and $y$ such that $ax-by=1$ is called the fundamental theorem of arithmetic.
Obviously, this is ...
2
votes
1
answer
68
views
Proving formula about the least number $n$ such that $a|n$ and $b|(n+1)$, $a,b$ coprime.
I have been looking for theorems that say something about relations of factors between consecutive numbers. With Bezout's identity it can be proved that if
$\gcd(a,b)=1$ there is always a number $n$ ...
0
votes
0
answers
25
views
Coprime transfer functions
This in an old problem from a past exam. It states that if N,M are in the set of Q
={ all stable, proper, real-rational functions} , they are coprime and NM^(-1) is also in Q then M^-1 is in Q. I cant ...
0
votes
0
answers
59
views
Let $G$ be a non-abelian finite group. If $a\in G$ has order $2$ and $b\in G$ has order $3$, what can we say about the order of $ab$? [duplicate]
Let $G$ be a non-abelian finite group. If $a\in G$ has order $2$ and $b\in G$ has order $3$, what can we say about the order of $ab$?
I know that, in the abelian case, $o(ab)=6$. In the non-abelian ...
1
vote
0
answers
52
views
RSA Problem : Encrypt the letter J in ASCII (decimal) with public key RSA (n=147, e=7) ...
Encrypt the letter J in ASCII (decimal) with public key RSA (n=147, e=7), then compute the private key and decrypt the result confirming that the message has been sent.
First part
J = 74 (ASCII), $n =...
2
votes
0
answers
25
views
Does this graph of non-coprime pairs of numbers have any interesting properties?
I guess it looks nice but aside from that what else could I say about this graph? What sorts of statements about this could I make and try to prove? ...Later, I will try coloring based on the g.c.f. ...
9
votes
1
answer
126
views
Given an integer sequence $a_{n+1}=a_{n}^{2}-a_{n}-1$, prove that $\forall n\in \mathbb{Z}$, $a_{n+1}$ and $2n+1$ are coprime
This is a very interesting infinite integer sequence problem I came across. The crux of the matter lies in comparing the values and the indices - we are supposed to check whether $a_{n+1}$ and $2n+1$ ...
0
votes
1
answer
137
views
Definition of a powersmooth number
I understand the basic definition of a smooth & powersmooth number.
Let $B$ be an integer. An integer $N$ is called $B$-smooth if every prime factor $p$ of $N$ is less than $B$
$N = 2^{78} · 3^{...
0
votes
1
answer
75
views
$5^n$ is relatively prime with 13, n in $\mathbb{N}$
$5^n$ is prime with 13, n in $\mathbb{N}$?
I have proved that $5^{n+4}-5^n \equiv$ 0(mod 13)
. So $5^n(5^4-1) \equiv$ 0(mod 13)
Now Im stuck on how to prove that $5^n$ is relatively prime with 13
0
votes
1
answer
47
views
What is the function/symbol to represent the set of Coprimes?
Just wondering if there’s an established symbol or function used to represent the set of coprimes of N which are less than or equal to N?
Thanks!
1
vote
0
answers
128
views
Intersection of subgroups is trivial
We all know that if two subgroups $A \le G$ and $B \le G$ have coprime order $\gcd(|A|, |B|)=1$, then their intersection is trivial: $A \cap B=\{e\}$.
Does the converse of this statement remains true? ...
2
votes
0
answers
32
views
least upper bounds that are coprime
Given $n$ natural numbers $p_1$, $p_2$, ... $p_n$ find numbers $q_1$, $q_2$, ... $q_n$ that are pairwise coprimes such that $p_i$ ≤ $q_i$ and such that $\prod_{i=1..n} q_i$ is smallest possible.
I ...
0
votes
0
answers
24
views
Prove that for fixed $c$ there exits $d$ such that polynomials $p_ 1(x,y)-cq_1(x,y) $and $p_2(x,y)-dq_2(x,y)$ are coprime
Let
$$
f(x,y)=p_1(x,y)-cq_1(x,y),\\
g(x,y)=p_2(x,y)-dq_2(x,y),
$$
be polynomials, where $c,d\in\left(0,1\right)$. Coefficient $x,y$ of polynomials represent probabilities, so $x,y\in\left<0,1\right&...
1
vote
0
answers
41
views
Find $e$ in set closed under subtraction, hence prove co-prime elements have GCD $=1$.
In the book by Andre Weil, titled : Number theory for Beginners, is given on page 4,5 theorem #II.1 regarding a set M i.e. closed under subtraction. There are also two corollaries to the same, ...
3
votes
1
answer
50
views
Simple proof that there exist that you can obtain difference of 1 between multiples of coprimes $a$ and $b$
Given two coprimes $a$ and $b$ (assume wlog that $a < b$), there are non-negative integers $n_a$ and $n_b$ such that $n_b \cdot b = n_a \cdot a + 1$. Easy to prove using Bézout's identity, but is ...
0
votes
2
answers
132
views
Distinct Mersenne numbers are relatively prime specific proof verification [duplicate]
As the title states, I'm supposed to prove for distinct primes $p_1,p_2 >2$ the primes dividing $2^{p_1}-1$ and $2^{p_2}-1$ are distinct.
The Wikipedia page on Theorems about Mersenne Numbers ...
2
votes
1
answer
130
views
Making sure $a$ and $b$ are relatively prime
I came across this interesting problem in the Olympiad Maths challenge practice problem, and it is really fascinating:
Some $n$ numbers are selected randomly from the integers $1$ to $420$. $2$ ...
0
votes
0
answers
66
views
Prove that the elements of a sequence are pairwise co-prime [duplicate]
Hi I need help on this question:
Consider the sequence of positive integers an, for $n ≥ 1$, defined by
$a_n = 6^{2^n} + 1$.
(a) Prove that the elements of this sequence are pairwise co-prime, i.e. ...
1
vote
0
answers
20
views
Multiple co-prime condtions
Suppose $n$ is co-prime with a set of primes $\{p_1 = 2, \dots p\}$. There is a known bound (Tenenbaum) on the number of $n, \ \Phi_{cp}(x, p)$ satisfying the co-prime condition in an interval $n \le ...
1
vote
1
answer
80
views
In general, can we prove that admissible quadratic polynomials must yield at least one prime value?
By admissible, I'm referring to an integer-valued quadratic function with no common factors, i.e. one that meets the basic requirements to be able to produce primes. To be more specific, a quadratic ...
0
votes
1
answer
134
views
The probability that two integers picked at random are Prime.
It's known that The probability that two integers m and n picked at random are relatively prime is $\frac{6}{\pi^2}$
To see for myself, I ran 100,000,000 random tests of $gcd(m=random(), n=random())$ (...
1
vote
1
answer
163
views
Lattice points on $x+y=n$ always visible from the origin.
Let $m \in \mathbb{Z_{\gt 0}}$ and $\{n \in \mathbb{Z_{\gt 0}}:n\mod 10\}$ = $\{1, 3, 7, 9\}$.
Define
$\Large a_{m} = \frac {5^m-3}2$
Claim
Any lattice points $(x,y)$ of the form
$\Large(\left \...
2
votes
0
answers
144
views
Do infinite coprime points $(x,y)$ exist satisfying $x+y=n$ where $x,y,n \in \mathbb{N}$?
I'm trying to prove infinite primes exist based upon this:
For $n$ prime, every grid point on the line is coprime.
Examples of $x+y=n$ for $n$ prime
...
3
votes
2
answers
271
views
Finding the number of pairs (a,b) such that gcd(a,b,n)=1
This is question 6E from the 2019 Cambridge Mathematics Tripos paper 1A (which can be accessed at https://www.maths.cam.ac.uk/undergrad/pastpapers/files/2019/paperia_4_2019.pdf).
"Let $n\geq 2$ ...