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
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 ...
user avatar
  • 8,990
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 ...
user avatar
  • 175
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 ...
user avatar
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 ...
user avatar
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(...
user avatar
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{...
user avatar
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 + ...
user avatar
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!
user avatar
  • 1
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(...
user avatar
  • 13
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 ...
user avatar
  • 111
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 ...
user avatar
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 ...
user avatar
  • 6,853
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 ...
user avatar
  • 273
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 ...
user avatar
  • 2,820
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 ...
user avatar
  • 953
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 ...
user avatar
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$, ...
user avatar
  • 2,820
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 ...
user avatar
  • 899
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} + ...
user avatar
-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-...
user avatar
  • 57
-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$ ...
user avatar
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 ...
user avatar
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 \...
user avatar
  • 534
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 ...
user avatar
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 ...
user avatar
  • 1,621
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,\,...
user avatar
  • 215
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 ...
user avatar
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$ ...
user avatar
  • 13.3k
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 ...
user avatar
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 ...
user avatar
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 =...
user avatar
  • 603
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. ...
user avatar
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$ ...
user avatar
  • 247
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^{...
user avatar
  • 331
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
user avatar
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!
user avatar
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? ...
user avatar
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 ...
user avatar
  • 29
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&...
user avatar
  • 519
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, ...
user avatar
  • 3,645
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 ...
user avatar
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 ...
user avatar
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$ ...
user avatar
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. ...
user avatar
  • 1
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 ...
user avatar
  • 45
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 ...
user avatar
  • 4,979
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())$ (...
user avatar
  • 805
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 \...
user avatar
  • 805
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 ...
user avatar
  • 805
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$ ...
user avatar
  • 109

1
2 3 4 5