Sum-free multiplicative group mod p can be arbitrarily large

Art of Problem Solving

AoPS Online

High School Olympiads Regional, national, and international math olympiads

Regional, national, and international math olympiads

3 M G

BBookmark VNew Topic kLocked

High School Olympiads Regional, national, and international math olympiads

Regional, national, and international math olympiads

3 M G

BBookmark VNew Topic kLocked

No tags match your search

M

Sum-free multiplicative group mod p can be arbitrarily large

G H J

Reveal topic tags

abstract algebra

modular arithmetic

L

G H BBookmark kLocked kLocked NReply

Source: USA January TST for the 55th IMO 2014

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

6879 posts

#1 h Apr 28, 2014, 6:54 AM • 10 Y

Y by langkhach11112, Davi-8191, HamstPan38825, HWenslawski, megarnie, Adventure10, Mango247, ehuseyinyigit, ys-lg, and 1 other user

For a prime $p$ , a subset $S$ of residues modulo $p$ is called a sum-free multiplicative subgroup of $\mathbb F_p$ if
$\bullet$ there is a nonzero residue $\alpha$ modulo $p$ such that $S = \left\{ 1, \alpha^1, \alpha^2, \dots \right\}$ (all considered mod $p$ ), and
$\bullet$ there are no $a,b,c \in S$ (not necessarily distinct) such that $a+b \equiv c \pmod p$ .
Prove that for every integer $N$ , there is a prime $p$ and a sum-free multiplicative subgroup $S$ of $\mathbb F_p$ such that $\left\lvert S \right\rvert \ge N$ .

Proposed by Noga Alon and Jean Bourgain

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

15142 posts

#2 h Apr 28, 2014, 7:19 AM • 5 Y

Y by bcp123, langkhach11112, Adventure10, Mango247, ehuseyinyigit

I wonder if this problem was "inspired" from the result(s) of this article http://www.cs.tau.ac.il/~nogaa/PDFS/multip1.pdf of Noga Alon

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

2903 posts

#3 h Apr 28, 2014, 7:25 AM • 12 Y

Y by SCP, narutomath96, TheStrangeCharm, langkhach11112, rafayaashary1, Leooooo, fields123, chem123, solver1948, xhx0123, Adventure10, Mango247

The key insight to this problem is to transfer it over the the complex numbers, where roots of unity behave a lot more nicely. Fix $q > \max(N,3)$ and let $S$ be the set of $q^{th}$ roots of unity for a prime $p$ . Now if $S$ were not sum free modulo $p$ , there must exist $a,b$ such that:
$1 + \alpha^a \equiv \alpha^b \pmod{p}$
Exponentiation by $q$ :
$(1 + \alpha^a)^q \equiv 1 \pmod{p}$
Now, I claim that $(1 + x^a)^q - 1$ and $x^q - 1$ are relatively prime polynomials over $\mathbb{Z}[x]$ . This is clear as we have $1 + \omega^a$ is a $q^{th}$ root where $\omega$ is a $q^{th}$ root of unity, but this is impossible for $q > 3$ . Thus there exist $m(x), n(x) \in \mathbb{Z}[x]$ and an integer $c_a$ such that:
$m(x) ((1 + x^a)^q - 1) + n(x) (x^q - 1) = c_a$
Now if $p > c_a$ , we get $p$ cannot simultaneously divide $(1 + x^a)^q - 1$ and $x^q - 1$ . Thus if we set $p \equiv 1 \pmod{q}$ with $p > c_0, c_1, ..., c_{q-1}$ , we get $S$ must be sum free as desired.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

606 posts

#4 h Apr 28, 2014, 8:57 PM • 7 Y

Y by langkhach11112, Supercali, Nathanisme, TheBarioBario, Adventure10, Mango247, RootofUnityfilter

During the actual test I found a pretty funny proof. Throughout when say polynomial, I mean integer polynomial (I may have forgotten to mention it at places)

For some preliminary stuff, we need $\alpha^x+\alpha^y \not= \alpha^z$ for any integers $0 \le x, y, z \le p-2$ . Dividing through by $\alpha^z$ gives $\alpha^{x-z}+\alpha^{y-z} \not= 1$ , and letting $c = x-z, d = y-z$ we just need that $\alpha^c+\alpha^d \not= 1$ .
This motivates us to look at polynomials of the form $x^c+x^d-1$ . (*)

Lemma 1: For some polynomial $f(x) \in \mathbb{Z}[x]$ such that $f(1)$ is odd, we can find a polynomial $g(x^2)$ such that $f(x) | g(x^2)$ and $g(1)$ is also odd.

Proof: Let $g(x^2) = f(x)f(-x)$ , because both sides are even functions. But then $g(1) = f(1)f(-1) \equiv f(1)^2 \equiv 1 \pmod{2}$ .

Note that this implies that for any positive integer $N$ we can find a polynomial $h$ such that $f(x) | h\left(x^{2^N}\right)$ and such that $h(1)$ is odd, by induction.

Now choose primes of the form $p = k \cdot 2^N+1$ (infinitely many by Dirichlet's theorem) only and fix $\alpha$ to have order $2^N$ . By (*) we now consider the polynomials of the form $x^c+x^d-1$ for $0 \le c, d \le 2^N$ and we prove that for all large enough $p$ $\alpha$ will not be a root in $\mathbb{F}_p$ . Assume $\alpha$ is a root. Let $f(x) = x^c+x^d-1$ , and by Lemma 1 (the note afterwards) that we can find a $h$ such that $f(x) | h\left(x^{2^N}\right)$ . If $\alpha$ is a root of $f$ , plugging in $\alpha$ , we get that we need that $h\left(\alpha^{2^N}\right) \equiv h(1) \pmod{p}$ to equal 0. But $h(1)$ is fixed for any primes $p$ and it is odd by the Lemma (since $f(1) = 1$ is odd), so it is not identically 0. So $\alpha$ is eventually not a root. Since we can do this for any polynomials $f(x)$ for $0 \le c, d \le 2^N$ , eventually $\alpha$ will not be a root of any of them, so we're done.

Note: You can also replace $2$ (even) by any prime $q$ and essentially repeat the above argument.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

4302 posts

#5 h Apr 29, 2014, 9:46 AM • 3 Y

Y by langkhach11112, Adventure10, Mango247

mavropnevma wrote:

I wonder if this problem was "inspired" from the result(s) of this article http://www.cs.tau.ac.il/~nogaa/PDFS/multip1.pdf of Noga Alon

"Inspired" is quite a generous word.

As briefly hinted at in the end of that paper, it is not hard to extend the methods to show that the " $0\notin S+S-S$ " condition of (b) can be replaced by $0\notin a_1S+a_2S+\cdots+a_kS$ (for integers $a_i$ ) if and only if $\sum a_i \ne 0$ .

Then the gimmicky stuff like " $1+\omega,\omega$ can't simultaneously be $q$ th roots for large $q$ " doesn't work, although as mathocean97 notes, the argument isn't too much harder.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

2903 posts

#6 h Apr 29, 2014, 9:42 PM • 3 Y

Y by langkhach11112, Adventure10, Mango247

math154 wrote:

Then the gimmicky stuff like " $1+\omega,\omega$ can't simultaneously be $q$ th roots for large $q$ " doesn't work.

I wouldn't call it gimmicky as it generalizes as well. Basically instead we would have to show if $P$ is a polynomial with integer coefficients whose coefficients do not sum to 1, then there exists some sufficiently large $n$ such that $P(\omega_n)$ is not an $n^{th}$ root of unity and then we take an $n$ larger than the required $n$ 's for each of the possible polynomials. But this is simple using the fact $[\mathbb{Q}[\omega_n]:\mathbb{Q}] = \varphi(n)$ , as then we can just take $n$ with $\varphi(n) > \deg P +1$ . Note that the coefficient summing to one condition comes into play as we may get $P(x) = x^k$ in that case which breaks the argument but otherwise we are fine.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

4302 posts

#7 h Apr 29, 2014, 9:52 PM • 1 Y

Y by Adventure10

dinoboy wrote:

math154 wrote:

Then the gimmicky stuff like " $1+\omega,\omega$ can't simultaneously be $q$ th roots for large $q$ " doesn't work.

I wouldn't call it gimmicky as it generalizes as well.

I was just saying the usual geometry proof of this doesn't work well (which most people who solved the problem live did, although I know you know better). I basically had the same approach as you (which is actually also the same as mathocean97's, if you look closely enough at the $g$ / $h$ he constructs).

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

366 posts

#8 h May 1, 2014, 1:27 AM • 3 Y

Y by langkhach11112, Adventure10, Mango247

The key idea is that there are $m$ $m$ -th roots of unity, so if we take $p$ big, these roots of unity should be "spaced out". Another very important idea is to consider polynomials in $\mathbb{Z}$ , and then evaluate them mod $p$ .

Let's look at polynomials. If the problem was wrong, then for $p$ sufficiently big, the $Q$ -th roots of unity mod $p$ don't work. So there exists a solution to $(1+x^b)^Q-1=x^Q-1=0$ mod $p$ . Let $A(x)=(1+x^b)^Q-1$ and let $B(x)=x^Q-1$ . Since $w+1$ and $w$ cannot both be roots of unity (in $\mathbb{C}$ ) when $Q$ is big, we have that $A$ ad $B$ are coprime polynomials. And so we have $mA+nB=c$ for some $m,n$ polynomials, $c$ a nonzero nteger. We have that for all $p \equiv 1$ (mod $Q$ ) there must exist a $b$ such that $p | c$ . But we can simply take a very gigantic $p$ , greater than all $Q$ possible values of $c$ (since there are $Q$ possible values of $b$ ). This $p$ exists by Dirichlet. So we are done.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

3 posts

#9 h Jul 7, 2014, 5:18 AM • 1 Y

Y by Adventure10

https://www.facebook.com/photo.php?fbid=341156276033763&set=a.300473743435350.1073741828.100004181803371&type=1&theater
I wrote my solution here in Vietnamese but i think it's very easy to understand:))))

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

676 posts

bcp123

#10 h Aug 1, 2014, 5:58 PM • 2 Y

Y by Adventure10, Mango247

dinoboy wrote:

and let $S$ be the set of $q^{th}$ roots of unity for a prime $p$ .

Can someone explain this?

This post has been edited 1 time. Last edited by bcp123, Nov 11, 2015, 2:59 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

606 posts

#11 h Aug 1, 2014, 7:57 PM • 4 Y

Y by bcp123, langkhach11112, Adventure10, Mango247

It's actually exactly what you would expect. It's the solutions to $x^q \equiv 1 \pmod{p}$ . If $q | p-1$ , then there are exactly $q$ roots of unity $\pmod{p}$ .

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

2079 posts

pi37

#12 h Nov 11, 2015, 6:59 AM • 3 Y

Y by langkhach11112, Adventure10, Mango247

Basic idea: we want to translate the sum-free condition with small $S$ to be a kind of finite restriction, which taking $p$ sufficiently large can break.

So fix some $k$ to be the size of $S$ and let $p$ be some indeterminate prime for now with $p\equiv 1 \pmod k$ . Of course, if the sum-free condition fails then there are two elements of the group which add to one. Thus there would exist $g$ such that both $g^k\equiv 1\pmod{p}$ and $(1-g)^k\equiv 1 \pmod{p}$ . Now we decide to take $p\equiv 2\pmod{3}$ , so the polynomials $x^k-1$ and $(1-x)^k-1$ have no shared complex roots and are thus relatively prime. Then there exist $p,q\in \mathbb{Z}[x]$ such that
$p(x)(x^k-1)+q(x)((1-x)^k-1)=n$ for some positive integer $n$ . Thus since there exists $g$ which makes the LHS vanish $\pmod{p}$ , if $p\nmid n$ , then the subgroup is sum-free. Thus all we have to do is take $p>n$ , with $p\equiv 1 \pmod{k}$ and $p\equiv 2\pmod{3}$ by Dirichlet, and we're done.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

2130 posts

DrMath

#13 h Apr 9, 2017, 6:42 PM • 2 Y

Y by primesarespecial, Adventure10

Let $q$ be a prime, and let $z$ be a primitive $q$ th root of unity. Then let $f(X)=\prod_{i, j} (X-z^i-z^j) \in \mathbb{Z}[X]$ . First, note that $f(z^k)=\prod_{i,j} (z^k-z^i-z^j)=\prod_{i, j} (z^{k'}-z^{i+k'-k}-z^{j+k'-k})=\prod_{i', j'} (z^{k'}-z^{i'}-z^{j'})=f(z^{k'})$ . This means that $f(X)=g(X)(X^q-1)+r$ for some finite constant $r$ . Moreover, this constant is nonzero, as if $f(1)=0$ then $1=z^i+z^j$ for some $i,j$ . But then this means that the minimal polynomial of $z$ would be $X^i+X^j-1$ which has degree greater than 0 but at most $q-1$ , contradiction. Thus $r\neq 0$ . But then note that if we take $q-1\mid p$ and $p>r$ , then $X^q-1\nmid f(X)$ in $\mathbb{F}_p[X]$ . Then if $\alpha\in\mathbb{F}_p$ such that $\alpha^q=1$ , then $f(X)=\prod_{i,j} (X-\alpha^i-\alpha^j)$ which decomposes into linear factors in $\mathbb{F}_p[X]$ . But also note $f(\alpha)\neq 0$ , so in particular it cannot be true that $\alpha=\alpha^i+\alpha^j$ for any $i,j$ and we are done.

Now $|S|=q$ , and we can make $q$ arbitrarily large, so we are done.

This post has been edited 1 time. Last edited by DrMath, Apr 9, 2017, 6:47 PM
Reason: forgot last line

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

1980 posts

#14 h Jun 17, 2018, 12:54 AM • 2 Y

Y by Adventure10, Mango247

This feels a little bit easy for TST #6, so I'm probably missing something

v_Enhance wrote:

For a prime $p$ , a subset $S$ of residues modulo $p$ is called a sum-free multiplicative subgroup of $\mathbb F_p$ if
$\bullet$ there is a nonzero residue $\alpha$ modulo $p$ such that $S = \left\{ 1, \alpha^1, \alpha^2, \dots \right\}$ (all considered mod $p$ ), and
$\bullet$ there are no $a,b,c \in S$ (not necessarily distinct) such that $a+b \equiv c \pmod p$ .
Prove that for every integer $N$ , there is a prime $p$ and a sum-free multiplicative subgroup $S$ of $\mathbb F_p$ such that $\left\lvert S \right\rvert \ge N$ .

Proposed by Noga Alon and Jean Bourgain

Let $d=2^{|N|+1}$ and $p \equiv 1 \pmod{d}$ be a prime. Then pick $\alpha$ with $d$ the minimal number such that $\alpha^d \equiv 1 \pmod{p}$ . Then we claim that the set $S=\{1, \alpha, \alpha^2, \dots\}$ works fine. Clearly, $|S|>N$ and $S$ has the given type. Now we prove that $\alpha^m+\alpha^n=\alpha^k$ has no solution mod $p$ . Equivalently, $1+\alpha^c=\alpha^b \pmod{p}$ does not happen for any $b,c$ . Note that in $\mathbb{F}_p[x]$ we have $X^d-1=\prod_{s \in S} (X-s)$ so we wish to show that $X-s$ is not a factor of $(X+1)^d-1$ . We just need to show that their $\gcd$ is $1$ . Suppose $f(x) \in \mathbb{Z}[x]$ is their gcd (non-constant else its actually $1$ ); then $f(x)$ divides them both in $\mathbb{F}_2[x]$ as well. However, they have gcd $1$ in $\mathbb{F}_2[x]$ since $(X+1)^{2{|N|+1}}-1 \equiv X^{2^{|N|+1|}}$ by Frobenius Endomorphism. Thus, $f(x)=1+2g(x)$ for some integer polynomial $g$ . However $f$ must be monic as it integrally divides two monic integer polynomials; contradiction!

Edit: Okay, so a constant gcd may not be $1$ . Suppose we can find $q(x), r(x) \in \mathbb{Z}[x]$ with $q(x)(x^d-1)+r(x)((x+1)^d-1)=M$ for fixed integer $M$ . Then take $p>M$ to avoid mod $p$ issues. Hope this fixes it?

This post has been edited 1 time. Last edited by anantmudgal09, Jun 17, 2018, 12:56 AM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

66 posts

neel02

#15 h Jun 17, 2018, 9:06 AM • 2 Y

Y by Adventure10, Mango247

Hi @anantmudgal09 ! Hope you not [missing anything] since usatst 2016 Dec.# 3 is an another ex. of unbelieveably easy prob !

This post has been edited 1 time. Last edited by neel02, Jun 17, 2018, 9:07 AM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

1298 posts

Kayak

#16 h Sep 22, 2018, 8:53 PM • 1 Y

Y by Adventure10

Can someone point out any mistake in my "solution" ? This looks way too simple for it's position.

???

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

1614 posts

yayups

#17 h Feb 19, 2019, 6:51 AM • 1 Y

Y by Adventure10

Let $N$ be some positive integer relatively prime to $3$ . Pick $p\equiv 1\pmod{N}$ to be a prime much much larger than $N$ . We show that there exists a sum free multiplicative subgroup of $\mathbb{F}_p$ of size $N$ . But first, we need a lemma.

Lemma: $\gcd(X^N-1,(1-X)^N-1)=1$ over $\mathbb{F}_p[X]$ .

Proof of Lemma: Over $\mathbb{C}$ , we can check that $X^N-1$ and $(1-X)^N-1$ share no roots. Indeed, if $r$ was a root of both, then $|r|=|1-r|=1$ . This would mean that $(1-r)(1-1/r)=1$ , or that $r+1/r=1$ , or $r^2-r+1=0$ . Thus, $r^6=1$ , but since $\gcd(N,3)=1$ , we have $r^N\ne 1$ , a contradiction. Thus, $\gcd(X^N-1,(1-X)^N-1)=1$ over $\mathbb{Z}[X]$ as well, so there are fixed polynomials $P(X),Q(X)$ such that
$(X^N-1)P(X)+((1-X)^N-1)Q(X)=1.$ Now, for $p$ sufficiently large, both $P(X)$ and $Q(X)$ won't be $0$ , so then $\gcd(X^N-1,(1-X)^N-1)=1$ over $\mathbb{F}_p[X]$ . $\blacksquare$

Now, suppose $g$ is a primitive root mod $p$ . Let $\alpha=g^{\frac{p-1}{N}}$ , so $S$ has size $N$ . Now, suppose we had $\alpha^i+\alpha^j\equiv\alpha^k\pmod{p}$ . Then, $\alpha^{i-k}+\alpha^{j-k}\equiv 1\pmod{p}$ , so WLOG we can take $k=0$ . Thus, $\alpha^j\equiv 1-\alpha^i\pmod{p}$ , so letting $r=\alpha^i$ , we have $r,1-r$ are both roots of $X^N-1$ over $\mathbb{F}_p$ . But this can't be by the lemma, so we have the desired contradiction. So we have constructed a sum free multiplicative subgroup of $\mathbb{F}_p$ for some $p$ , of arbitrarily large size, as desired. $\blacksquare$

This post has been edited 1 time. Last edited by yayups, Feb 19, 2019, 6:52 AM
Reason: typo

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

544 posts

lminsl

#18 h Oct 8, 2019, 3:02 PM • 3 Y

Y by magicarrow, Nathanisme, Adventure10

Fix some prime $q$ bigger than $N$ .

We will set $p$ as a prime dividing $\Phi_{q}(\alpha)$ , and $S$ generated by powers of $\alpha$ modulo $p$ , where $\alpha$ is a integer determined later. Note that $|S|=q$ here, so $S$ satisfies the size condition.

The main observation is the following:

Main Lemma: For coprime polynomials $f, g\in \mathbb{Z}[x]$ , there exist a integer $C>0$ such that $\gcd(f(n), g(n))$ divides $C$ for every integer $n$ satisfying $\left( f(n), g(n) \right) \neq (0, 0)$ .

Since $\Phi_q(x)$ is irreducible over $\mathbb{Z}[x]$ , for every $0\le i<j <q$ , the polynomials $\Phi_q(x)$ and $x^i+x^j-1$ is coprime, so some suitable $C_{i, j}$ exists by the lemma. Now set $\alpha$ such that $\alpha$ is divisible by all such $C_{i, j}$ 's, then $\Phi_q(\alpha) \equiv 1 \pmod {C_{i, j}}$ , so $\Phi_q(\alpha)$ and $\alpha^i+\alpha^j-1$ are coprime as integers.

Now, we prove that the set $S$ is sum-free. Assume that there exists some $i<j<k$ such that $\alpha^i +\alpha^j \equiv \alpha^k \pmod p$ . Multiplying $\alpha^{q-k}$ in each sides give $\alpha^{i+q-k}+\alpha^{j+q-k}-1 \equiv 0 \pmod p$ , whereas $p | \Phi_q(\alpha)$ is coprime with $\alpha^{i+q-k}+\alpha^{j+q-k}-1$ . Hence $S$ is sum-free, and we're done!

This post has been edited 2 times. Last edited by lminsl, Feb 5, 2020, 3:26 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

1740 posts

#19 h Feb 26, 2020, 5:35 AM • 1 Y

Y by sabkx

I claim for every $n$ not divisible by $3$ , we can choose a prime $p\equiv1\mod n$ such that there is a sum-free multiplicative subgroup in $\mathbb F_p$ of size $n$ .

Let $P(x)=x^n-1$ and $Q(x)=(1+x^k)^n-1$ . First I claim $P$ and $Q$ are relatively prime over $\mathbb C[x]$ . If $P$ and $Q$ share a root $\omega$ , then $\omega$ and $1+\omega^k$ are both roots of unity. Then the vectors defined by $\omega^k$ , $1$ , $-(1+\omega^k)$ form an equilateral triangle, which is absurd since $3\nmid n$ .

Thus the greatest common factor of $P$ and $Q$ over $\mathbb Z[x]$ is a positive integer $m$ , so by B\'ezout's lemma we may choose polynomials $A$ and $B$ in $\mathbb Z[x]$ with
$A(x)\left(x^n-1\right)+B(x)\left[\left(1+x^k\right)^n-1\right]=m.\tag{$\star$}$ Assume $S$ has size $n$ and choose a prime $p>m$ such that $p\equiv1\mod n$ . A multiplicative subgroup exists by taking $\alpha=g^{(p-1)/n}$ , where $g$ is a primitive root modulo $p$ . If $S$ is not sum-free, then it contains elements $\alpha^x$ , $\alpha^y$ , $\alpha^z$ with $\alpha^x+\alpha^y=\alpha^z$ . It follows that $(1+\alpha^{y-x})^n=1$ , which is absurd since the left-hand expression vanishes modulo $p$ when taking $x=\alpha$ and $k=y-x$ in $(\star)$ .

This post has been edited 1 time. Last edited by TheUltimate123, Feb 26, 2020, 6:46 AM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

238 posts

#20 h Oct 28, 2021, 6:42 PM

Y by

Pick a prime $q>N$ and let $p$ be a prime number such that $q|p-1$ . Choose $\alpha$ to be a primitive $q$ -th root of unity $\pmod{p}$ . Then, $S=\{1,\alpha,...,\alpha^{q-1}\} \implies$ for all $s \in S$ , $s$ is a root of $X^q-1$ in $\mathbb{F}_p$ .

From the second condition, the polynomial $\prod_{1 \leq i \leq j \leq q} (X-(\alpha^i+\alpha^j))$ is coprime to $X^q-1=\prod_{i=1}^q(x-\alpha^i)$ in $\mathbb{F}_p$ , i.e., they don't share roots. Thus, we want $(\alpha^i+\alpha^j)^q \not \equiv 1 \pmod{p} \iff (1+\alpha^{j-i})^q \not \equiv 1 \pmod{p}$ for all $1 \leq i \leq j \leq q$ . This is the same as saying that $(1+X)^q-1$ and $X^q-1$ don't share a common root modulo $p$ .

Looking in $\mathbb{Z}[X]$ , $(1+X)^q-1,X^q-1$ share a root if and only if $|z|=1=|z+1| \iff z=-\frac{1}{2} \pm \frac{\sqrt{3}}{2}i \implies$ as long as $3 \nmid q$ , $gcd(X^q-1,(1+X)^q-1)=1$ in $\mathbb{Z}[X]$ . Now, we prove the following lemma:

Lemma: If $f,g \in \mathbb{Z}[X]$ such that $gcd(f,g)=1 \implies$ for all sufficiently large prime $p$ , $gcd(f,g)$ is a constant in $\mathbb{F}_p[X]$ , i.e., $f,g$ don't share roots in $\mathbb{F}_p$ .
Proof: By Bézout's Lemma, there is a constant $c \in \mathbb{Z}$ and $a,b \in \mathbb{Z}[X]$ such that $af+bg=c$ , so if $p|f(r),g(r) \implies p|c$ , so $p$ is bounded. $\square$

From the lemma, if $p$ is large enough, $(1+X)^q-1,X^q-1$ are coprime in $\mathbb{F}_p$ , so since $|S|=q>N$ , we are done.

$\blacksquare$

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

CyclicISLscelesTrapezoid

372 posts

CyclicISLscelesTrapezoid

#21 h Dec 30, 2022, 7:13 PM • 1 Y

Y by samrocksnature

Solved with v4913. This might seem like a problem about the structure of orders and primitive roots $\!\!\!\mod{p}$ , but it's really a problem about polynomials.

We claim that for all primes $N$ , there exists a sum-free multiplicative subgroup of size $N$ .

Notice that if there exist integers $k$ , $m$ , and $n$ such that $\alpha^m+\alpha^n \equiv \alpha^k \pmod{p}$ , then by scaling, there exist nonnnegative integers $m$ and $n$ such that $p \mid \alpha^m+\alpha^n-1$ . Consider $P(x)=\prod_{0 \le m,n < N}(x^m+x^n-1).$ We know that $x-1 \nmid P(x)$ because $P(1) \ne 0$ and $1+x+\cdots+x^{N-1} \nmid P(x)$ because $1+x+\cdots+x^{N-1} \nmid x^m+x^n-1$ for all $m$ and $n$ with $0 \le m,n < N$ . Since $x-1$ and $1+x+\cdots+x^{N-1}$ are irreducible cyclotomic polynomials, we have $\gcd(P(x),x^N-1)=1$ . By Bézout on integer polynomials, there exist integer polynomials $A(x)$ and $B(x)$ and a positive $c$ such that $A(x)P(x)+B(x)(x^N-1)=c.$
Now, we can construct. Choose $\alpha=4913c$ (the constant of $4913$ is just there so that $\alpha \ne 1$ ), and let $p$ be a prime dividing $\alpha^N-1$ . Since $c \mid \alpha^N$ , $p \nmid c$ , so $A(\alpha)P(\alpha) \equiv c \pmod{p} \Rightarrow p \nmid P(\alpha).$ That means $p \nmid \alpha^m+\alpha^n-1$ for all $m$ and $n$ with $0 \le m,n < N$ , and we are done.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

8868 posts

#22 h Oct 21, 2023, 1:29 PM

Y by

Fun problem. The key lemma is the following:

Lemma. If $f, g$ are relatively prime in $\mathbb Z[X]$ , then for sufficiently large $p$ , they are relatively prime in $\mathbb F_p[X]$ too.

Proof. By Bezout's lemma there exist polynomials $a, b \in \mathbb Q[X]$ such that $af+bg = 1$ . On the other hand, pick $p$ greater than any denominator of a coefficient in $a$ or $b$ . Suppose there exists $k$ such that $f(k) \equiv g(k) \equiv 0 \pmod p$ ; then $\nu_p(af(k)+bg(k)) \geq 1 \neq 0$ which is an obvious contradiction. $\blacksquare$

Now the problem becomes quite clear. It suffices to find $p$ for which we can construct two polynomials $X^n - 1$ and $(1+X)^n - 1$ which share no roots in $\mathbb F_p$ for as large $n$ as we please. By the lemma, by picking $p$ large, it suffices for these to be relatively prime in $\mathbb Z[X]$ .

On the other hand, construction for this is easy: just take $n = 2^m$ and notice that all $\Phi_{2^k}(X)$ 's have distinct degree. On the other hand, by irreducibility $\Phi_{2^k}(X)$ and $\Phi_{2^k}(X+1)$ are irreducible. This yields infinitely many $n$ , done.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

243 posts

#23 h Jul 12, 2024, 3:39 AM

Y by

Now see that it is well known that all cyclotomic polynomials are irreducible and hence $\gcd\left(\Phi_q(X),\Phi_q \left(X^N-1 \right) \right)=1$ where $q$ is any prime and $q \nmid N$ . If not then one will find if $\omega$ is a $q^\text{th}$ root of unity, then so is $\omega^N-1$ . And so is $\omega^2$ and so is $\omega^{2N}-1$ and hence so is $\omega^N+1$ .

But $|\omega^N-1|=|\omega^N+1|=1 \implies \omega=0$ .

And then by Bezout's lemma on polynomials we get that they are relatively prime polynomials over ${{\mathbb{F}}_p}$ for large enough $p$ $\left(\circledast \right)$ . Now let

$\bullet$ $q \geq 5$ be a prime.
$\bullet$ Pick odd prime $p$ large enough according to $\circledast$ and further let $p \not \equiv \pm 1 \pmod {8}$

(basically $2$ is not a quadratic residue modulo $p$ ) and $p \mid \Phi_q(\alpha)$ such that $\nu_2(\alpha)=2$ and is a quadratic residue modulo $p$ (which obviously exists modulo any odd prime). See that one can pick such a prime $p$ exist due to our choice of $\alpha$ (obviously make sure $\alpha \not \equiv 1$ ).
\end{itemize}
See that construction and the key notes basically ensures that ${\alpha}^q \equiv 1 \pmod p \text{ but } {\left(\alpha^N-1 \right)}^q \not \equiv 1 \pmod p$ because $p \nmid \Phi_q \left({\alpha}^N-1 \right)$ and hence we only need to ensure that $\alpha^N \not \equiv 2 \pmod p$ but this is true as $\alpha$ is a quadratic residue and $2$ is not modulo $p$ .

And now one can easily see that the multiplicative subgroup $\{1,\alpha,\dots,{\alpha}^{q-1}\} \in {{\mathbb{F}}_p}$ is sum-free, and since $q$ is any arbitrarily large prime and the cardinality of the set is $q$ , we win.

This post has been edited 4 times. Last edited by ihategeo_1969, Dec 5, 2024, 4:26 AM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

872 posts

#25 h Jul 29, 2024, 5:31 AM • 1 Y

Y by ys-lg

Take prime number $q>N.$ By Dirichlet Theorem take prime number $p\equiv 1\pmod q,$ let $p=mq+1.$ Take a primitive root $g$ in $\mathbb F_p,$ we prove $\{g^0,g^m,\ldots ,g^{m(q-1)}\}$ satisfies the condition. Here all "=" is under $\mathbb F_p.$ If $g^{mi}+g^{mj}=g^{mk}$ then $(g^{m(j-i)}+1)^q=g^{mkq}=1.$ Therefore $g^{m(j-i)}$ is root of $(x+1)^q-1=0$ and $x^q-1=0.$ Since $\gcd ((x+1)^q-1,x^q-1)=\gcd (x\Phi_q(x+1),(x-1)\Phi_q(x))=1.$ By Bezout Theorem there exists integer polynomial $A(x),B(x)$ and integer $d$ such that $A(x)[(x+1)^q-1]-B(x)(x^q-1)=d.$ So if we take $p>d$ we get contradiction. $\Box$

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

4191 posts

#26 h Oct 21, 2024, 4:52 PM

Y by

All statements in this solution assume that $p$ is sufficently large.

Suppose we fix $n$ and want a group of size $n$ . The group will consist of the roots of $x^n-1\equiv 0\pmod{p}$ . Because the elements can be expressed as $a^0,a^1,\dots$ , no two summing to another is actually equivalent to no two being consecutive (as if $a^x+a^y=a^z$ then $1+a^{y-x}=a^{z-x}$ ). Thus, it suffices to show that there is no $x$ for which
$x^n-1\equiv (x+1)^n-1\equiv 0\pmod{p}.$
Claim: If $3\nmid n$ , then $x^n-1$ and $(x+1)^n-1$ are coprime. We have $x^n-1=\prod_{d\mid n}\Phi_d(x)$ and $(x+1)^n-1=\prod_{d\mid n}\Phi_d(x+1)$ .

Sub-claim: If $a$ and $b$ are positive integers such that $\Phi_a(x)=\Phi_b(x+1)$ for all $x$ , then $a=3$ and $b=6$ . If $\omega$ is a primitive $a$ th root of unity, then $\omega+1$ is a primitive $b$ th root of unity. There are only two ways to move right by $1$ and stay on the unit circle, both of which move from a $3$ rd root of unity to a $6$ th root of unity.

Thus, the only way $x^n-1$ and $(x+1)^n-1$ can share common factors is if the former has $\Phi_3(x)$ and the latter has $\Phi_6(x+1)$ . Thus, choosing $3\nmid n$ avoids this.

Now, we show that arbitrarily large $n\not\equiv 0 \pmod{3}$ work. Because $x^n-1$ and $(x+1)^n-1$ are coprime in $\mathbb{Z}[x]$ , we have that $\gcd(x^n-1,(x+1)^n-1)$ is upper bounded by a constant $C$ due to Euclidean algorithm. Picking $p>C$ , we have that $x^n-1$ and $(x+1)^n-1$ are never both divisible by $p$ , and further specifying $p\equiv 1\pmod{n}$ so that there is actually a group of order $n$ suffices.

This post has been edited 1 time. Last edited by john0512, Oct 21, 2024, 4:53 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

672 posts

#27 h Apr 18, 2025, 11:20 PM

Y by

Let $q > N$ be a prime. Suppose $p\equiv1\pmod q.$ There exist infinitely many such $p$ due to dirichlet.

The second condition translates to $1 + \alpha^a=\alpha^b$ not having roots in terms of $a, b.$ Suppose $g$ is a primitive root modulo $p$ and $\operatorname{ord}_p(\alpha) = q = |S|.$ Then, the equation translates to $X^q - 1, (X - 1)^q - 1$ having no shared roots in $\mathbb F_p.$ It suffices to prove the following claim:

Claim: For sufficiently large $p,$ $X^q - 1, (X - 1)^q - 1$ have distinct roots in $\mathbb F_p.$
Proof: Clearly, if $q > 3,$ then $X^q - 1$ and $(X - 1)^q - 1$ have distince roots. Thus, by Bezouts lemma, there exists $a, b \in \mathbb Z[X]$ such that $a(X^q - 1) - b((X - 1)^q - 1) = d$ and $d \in\mathbb Z.$ Pick some $p > d$ and we are done.

Z K Y

N Quick Reply

G

H

=

© 2025 AoPS Incorporated

a