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
1 vote
1 answer
47 views

Coprime cycle problem help (precalculus-level) [closed]

Problem: a set of integers has a coprime cycle if it can be listed in a cyclic list of the form $(a_1, a_2, a_3, \ldots, a_n)$, where each element of the set appears exactly once and $\gcd(a_i, a_{i+...
Mintylemon66's user avatar
-2 votes
1 answer
68 views

Maximum consecutive multiples of coprimes [closed]

Given a set of coprimes, can we calculate a value or a limit for the maximum number of consecutive multiples of these values that can possibly occur? Now, given the same set of coprimes, if each value ...
Ricky Vesel's user avatar
2 votes
1 answer
78 views

Prove that all numbers in the series are relatively prime to each other [duplicate]

I have been working a bit with the following question: "Prove that all numbers given by $a_n=2^{2^n}+1$ are coprime to each other" I think I have a proof but I can't quite finish the last ...
naytte2's user avatar
  • 369
1 vote
1 answer
103 views

Are coprimes to the set of primes less than the $i^{th}$ prime always between one multiple of $p_i$?

I am not deeply familiar with mathematics, but I've run into an interesting question while programming that I would appreciate some help with. I'll provide context on the programming side of things to ...
user1281418's user avatar
0 votes
1 answer
83 views

What is the max value of $|S|$ where $S$ is a set with the following conditions? [duplicate]

$S$ is a subset of the first 1000 integers. No two elements of $S$ differ by 4 or 7. I have tried dividing the set of integers upto 1000 into subsets of 4 and 7 integers and tried to include into $S$ ...
Suprativ Mondal's user avatar
1 vote
1 answer
26 views

My idea about the number of coprime pairs up to $N$.

Today, I wanted to write a program to count how many integer pairs $(a, b)$ that satisfy: $$1 \leq a < b \leq n, \gcd(a, b) = 1$$ My first instinct was to write a function that check every pair. ...
Minh Đức Hoàng's user avatar
0 votes
0 answers
34 views

What is $N=1,3,5,9,17,77,105,111,429,455\ldots$, where the second player (possibly) always wins in a game involving incrementing to coprime numbers?

Alice and Bob are playing a game. They take $M$ turns, starting with one point each. The winner is the player with the highest score at the end of the game. In each round the players can make "...
dodicta's user avatar
  • 1,383
2 votes
1 answer
80 views

Proportionality of a system of polynomials

I am currently reading Ivanovs „Easy as Pi?“ in fact, I am trying to understand a proof in this book. Following statement is to prove: For $n\geqslant 3$ the curve $x^n+y^n=1$ has no rational ...
tychonovs-scholar's user avatar
2 votes
0 answers
58 views

Game strategy of incrementing to coprime numbers with $N=3$: does the second player always have a winning strategy?

Alice and Bob are playing a game. They take $M$ turns, starting with one point each. The winner is the player with the highest score at the end of the game. In each round the players can make "...
dodicta's user avatar
  • 1,383
3 votes
1 answer
192 views

What is the remainder when dividing $a$ by $5$ if $\sum_{k=1}^{1992}\frac{1}{k}=\frac{a}{b}$?

Consider $$\sum_{k=1}^{1992}\frac{1}{k}=\frac{a}{b}.$$ If $a$ and $b$ are natural numbers that are relatively prime, what is the remainder when dividing $a$ by $5$? $\text{(A) } 0 \space\space\space\...
Hussain-Alqatari's user avatar
0 votes
1 answer
101 views

Is it possible to prove that if $x$ and $y$ are co-prime, then $(x-y)$ and $\sqrt {xy}$ are also co-prime?

I was trying to prove that pythagorean triplets exists in Natural Number domain. Here's simplified argument that I did: consider two natural numbers $x$ and $y$ such that $x > y \ge 1$. $(x + y)^...
Cinverse's user avatar
  • 181
3 votes
0 answers
285 views

Find all positive integers $n$ such that $1+2^n+4^n$ is a prime number

Find all positive integers $n$ such that $1+2^n+4^n$ is a prime number. My attempt: Suppose that $P(n)=1+2^n+4^n$ is a prime number. Let $n=3^kl$, where $l\geq1$ and $l$ is not divisible by 3. We ...
Chivul's user avatar
  • 437
0 votes
0 answers
12 views

For a scoring system where the winner gets points until coprime with the opponent, are the possible number of games consecutive for any final scores?

Consider the following scoring system with a slightly unusual rule. There are two players, A and B, who play $N$ games. They both start with one point each. When one of them wins, they get points ...
dodicta's user avatar
  • 1,383
1 vote
0 answers
21 views

Modular multiplication of co-primes – always unique? [duplicate]

I am following the blog post "A practical use of multiplicative inverses" to implement a pseudo-hash function that needs to be reversible. The idea works perfectly, but I would like to ...
Tom Snelling's user avatar
0 votes
0 answers
28 views

Are there infinitely many relatively prime consecutive integers, whose prime factorization are exactly $2^n$ and $3^m$ for all m,n in Z^+? [duplicate]

Are there infinitely many solutions (m,n) to $\left\lvert3^m - 2^n\right\rvert$= 1 $\forall$ m,n $\in$ $\mathbb{Z}^+$ ? For this argument, (which is part of a larger proof I'm working on) it doesn'...
Jacob Nathaniel's user avatar
1 vote
1 answer
29 views

Prove that $uN\{0,1,2,\dots,m-1\}\equiv N\{0,1,2,\dots,m-1\}\pmod{mN}$, when gcd$(mN,u)=1$

Let $m,N\in\mathbb{N}_2$, and consider modulo $mN$. Let $u\in\{1,\dots,mN-1\}$ such that gcd$(mN,u)=1$. I want to show that the following two sets are equal, where order is unimportant; $$uN\{0,1,2,\...
MeBadMaths's user avatar
0 votes
0 answers
40 views

Why modular exponentiations of random, coprime numbers equals to 1/3?

Why is the average of modular exponentiations of random, coprime numbers equal to 1/3 on average? A similar question for N random (not coprime) numbers, but 'Why ... equal to 1/2 on average'? C++ code ...
Ecleytt's user avatar
  • 11
0 votes
1 answer
40 views

Possible values of $\gcd(2a^2+6a-4, 2a^2+4a-3)$

Let $a \in \mathbb{Z}$.Calculate all possible values of $\gcd(2a^2+6a-4, 2a^2+4a-3)$. By factoring, I can show that they have no common factors, so the answer is 1, but I have to go through non-...
2611throot's user avatar
20 votes
2 answers
581 views

A regular $n$-gon contains a regular $(n+1)$-gon, with no sides coinciding. What is the maximum number of points of contact between them?

A regular $n$-gon contains a regular $(n+1)$-gon. That is, they are in the same plane, and no part of the regular $(n+1)$-gon is outside of the regular $n$-gon. None of their sides coincide. There are ...
Dan's user avatar
  • 21.2k
0 votes
0 answers
19 views

Asympotic for the summatory function $\sum_{k<n, \gcd(k,n)=1}{\Omega(k)}$

I am interested in finding an asymptotic for the following summatory function over $\Omega(n)$, which counts the total number of prime factors of $n$ honoring their multiplicity: $$\sum_{k<n, \gcd(...
Juan Moreno's user avatar
  • 1,020
0 votes
1 answer
37 views

Coprime factorization of rational matrix over the polynomial ring

Dear esteemed colleagues, I have a question regarding the coprime factorization of rational matrices over the polynomial ring. Consider the following rational matrix $$ R(s) = \begin{pmatrix} \frac{1}{...
spin's user avatar
  • 11
0 votes
0 answers
39 views

How to prove that $(4n + 3)$ and $(20n + 23)$ are mutualy prime? [duplicate]

Following the next theorem: $$\gcd(a; b) = \gcd(a - b; b)$$ I get to the point where from these two numbers $4n + 3$ and $20n + 23$ I get these: $4n + 3$ and $8$. It seems obvious that these numbers ...
curioushuman's user avatar
0 votes
0 answers
23 views

Why choosing $x$ at random from $Z_N^*$ is equivalent to choosing $x_j$ s.t. $x = x_j \pmod{p_j^{\alpha_j}}$ with $p_j^{\alpha_j}$ a factor of $N$. [duplicate]

On the book "Quantum computation and quantum information" from Nielsen and Chuang on page 634 at the beginning of a theorem's proof it's assumed to be able to choose a number $x$ uniformly ...
Francesco Greco's user avatar
1 vote
0 answers
32 views

What is the Probability that Exactly One Pair among Three Integers is Coprime

Given three positive integers $a,b,c$ it isn't difficult to show that $$ P(\gcd(a,b,c)=1) = \prod_{p}\left(1-p^{-3}\right)=\frac1{\zeta(3)} $$ where $\zeta$ is the Riemann zeta function. For the next ...
Spador Yedi's user avatar
0 votes
1 answer
78 views

$7x+5y=12$, so why does its solution will be of the format $(1+5n,1-7n)$ [duplicate]

Question Consider all ordered pairs of integers $(x,y)$ such that $$\frac{5}{x}+\frac{7}{y} = \frac{12}{xy}.$$ The smallest positive integer value of $x$ in these ordered pairs is 1, since $x=y=1$ ...
Ayush Upadhyay's user avatar
5 votes
2 answers
530 views

Number of maximal antichains in the set $\{1,2,3,4,5,6,...,120\}$ where the order is by divisibility relation.

Find the number of maximal antichains in the set $\{1,2,3,4,5,6,7,...,120\}$ where the order is divisibility relation. For example, $\{6,7,15\}$ is an antichain but not a maximal antichain, and $\{1\}$...
Squirrel-Power's user avatar
3 votes
0 answers
70 views

Calculating the nth totative of a large primorial

For finding the $n$th prime (or the number of primes less than a number), there are results for large numbers; I was wondering if something similar for the totatives of a primorial number is possible (...
Jamie M's user avatar
  • 153
0 votes
1 answer
46 views

Can a coprime pair be decomposed into two coprime pairs?

Suppose $2p>q>p>1$ and $(p, q)=1$ (i.e., $p$ and $q$ are coprime). Is it the case that we can always find $a,b, c,d$ such that $p=a+c$, $q=b+d$, $(a,b)=1$ and $(c,d)=1$, $2a>b>a$ and $...
maomao's user avatar
  • 1,201
4 votes
0 answers
101 views

Why is $\mathrm{gcd}(n^a+b,(n+1)^a+b)$ almost always prime when $n$ is large?

Given is this function: $$ m=\mathrm{gcd}(n^a+b,(n+1)^a+b)\\ a,b,c\in\mathbb{N} $$ On OEIS A118119, for $2\leq a\leq 84$ and $b=1$, the smallest values for $n$ in each case where this expression is ...
Hubert Schölnast's user avatar
2 votes
0 answers
37 views

Minimising an expression involving prime numbers.

I would like to solve the following problem for a general $n$: Find disjoint sets $P$ and $Q$ of prime numbers so that \begin{align*} \pi_P = \prod_{p \in P} p \leq n \textrm{ and } \pi_Q = \prod_{q \...
Joseph Harrison's user avatar
0 votes
0 answers
27 views

Coprime Modular Arithmetic Proof [duplicate]

Suppose that $a$ is coprime to n. Prove that there exists $z \in\mathbb Z$ such that $az \equiv 1\pmod n$. Proof: By Bezout's Lemma, there exist integers $z$ and $y$ such that $az+ny=1$. So $az = 1+n(-...
user avatar
0 votes
0 answers
32 views

Modular Arithmetic Prime Proof Lemma [duplicate]

Let $a, b, x \in Z$, let $n ∈ N$ and let $h = hcf(a, n)$. Suppose that $h | b$, let $a'=\frac{a}{h}, b'=\frac{b}{h}$ and $n'=\frac{n}{h}$. Prove that $a'$ is comprime to $n'$. By Bezout's lemma, there ...
user avatar
3 votes
1 answer
68 views

Generating function for the "two variable totient"?

Recall that Euler's totient function $\varphi(n)$ is defined as the number of natural numbers $<n$ which are coprime to $n$. The Dirichlet series generating function for $\varphi(n)$ is $$ \sum_{n\...
მამუკა ჯიბლაძე's user avatar
2 votes
1 answer
76 views

Is a prime number $P$ always co-prime with $n$ if $1 < n < P$?

Is a prime number $P$ always co-prime with n such that $$1 < n < P?$$ This would also make sense to me because, just to establish firm definitions, two numbers are co-prime if they share no ...
Darcy Sutton's user avatar
1 vote
1 answer
196 views

Number of ways to write a positive integer as the sum of two coprime composites

I've recently learnt that every integer $n>210$ can be written as the sum of two coprime composites. Similar to the totient function, is there any known function that works out the number of ways ...
JCr's user avatar
  • 93
1 vote
1 answer
51 views

$\mathbb{Z}/n\mathbb{Z}$ as the union of $\frac{n}{e}(\mathbb{Z}/e\mathbb{Z})^\times$

For $e\mid n\in\mathbb{N}$, I want to show that $$ \mathbb{Z}/n\mathbb{Z} = \bigcup_{e\mid n} \frac{n}{e}(\mathbb{Z}/e\mathbb{Z})^\times,$$ where $\mathbb{Z}/n\mathbb{Z}$ are the integers modulo $n$, ...
MeBadMaths's user avatar
2 votes
1 answer
102 views

Transitive group action on two sets $A,B$ implies transitivity on $A\times B$

Let $G$ be a finite group acting transitively and faithfully on $A$ and $B$ (both finite). Futhermore $hcf(|A|,|B|)=1$. Show: $G$ is acting transitively on $A\times B$. My ideas: Since $G$ acts ...
hannah2002's user avatar
1 vote
1 answer
55 views

Modular Arithmetic Congruence Question

If $c$ is odd and $cy$ $≡$ $4$ mod $n$, then $c$ is coprime to $n$. Then it follows that $cy-4 = na$, so $cy-na = 4$. Then by Bezout's lemma, there exists integers $d$ and $w$ where $d=y$ and $e=-a$ ...
user avatar
1 vote
1 answer
68 views

Proving coprimes [closed]

I understand that it is necessary to prove that the GCD = 1, and so the Euclidean Algorithm can be applied in some way, but I'm having trouble actually applying it. Any help would be appreciated. ...
mathelper451's user avatar
0 votes
0 answers
47 views

Proving two expressions are Coprime

How would I prove $3y + 2$ and $3y-1$ are coprime. I know that the highest common factor of these two expressions will divide the difference between the numbers, so it will be a factor of 3, so either ...
user avatar
2 votes
0 answers
58 views

For which positive integers $n$ does there exist a positive integer $m$ for which all numbers between $mn$ and $(m+1)n$ coprime to $n$ are prime?

For which positive integers $n$ does there exist a positive integer $m$ for which all $\varphi(n)$ numbers between $mn$ and $(m+1)n$ coprime to $n$ are prime? I think that there are only finitely many ...
Geoffrey Trang's user avatar
1 vote
1 answer
135 views

A diophantine equation of coprime integers

I conjecture that for two coprime integers $a$ and $b$, for any integer $n$ coprime to $a$ and $b$ they exist integers $x$ and $y$ such that $ax + by = n$ $a,b,x,y,n$ are pairwise coprime I am ...
Juan Moreno's user avatar
  • 1,020
0 votes
1 answer
47 views

Question related to Bezout's identity and Pythagorean triples

Playing with Bezout's identity and Pythagorean triples, it seems that $a^{2}+b^{2}=c^{2}$ for coprime positive integers $a<b<c$ if and only if: $$bx+cy=a^{2}$$ $$b^{2}x+c^{2}y=1$$ Or which is ...
Juan Moreno's user avatar
  • 1,020
1 vote
1 answer
85 views

Help showing that $2^{p}f(x) - 1$ and $1 + 3f(x)$ are coprime [duplicate]

Coprimality of numbers is a new concept for me. I've been reading up on it and I don't quite grasp it yet. Is there a way to show that given $2^{p}f(x) - 1$ and $1 + 3f(x)$ are coprime for all values ...
Tiny Tim's user avatar
  • 423
0 votes
3 answers
64 views

Coprime with $n$ and their modular inverses in $\Bbb Z_n$

Consider $P = \{p_1, \ldots,p_l\}$ the set of numbers coprime to $n$, and set $P^{-1} = \{p_j^{-1}\}$ of inverses in $\Bbb Z_n$, that means: $$ p_j^{-1}p_j \equiv 1 \pmod n $$ I have proved that $P = ...
NeoFanatic's user avatar
0 votes
2 answers
218 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 ...
Hans's user avatar
  • 9,752
0 votes
2 answers
137 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 ...
Luke's user avatar
  • 195
1 vote
1 answer
199 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 ...
questioner's user avatar
0 votes
0 answers
54 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 ...
user3108815's user avatar
2 votes
2 answers
204 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{...
Clyde Kertzer's user avatar

1
2 3 4 5 6