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

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.

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.

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.

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.

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).

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.

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:))))

dinoboy wrote: and let $S$ be the set of $q^{th}$ roots of unity for a prime $p$. Can someone explain this?

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}$.

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.

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 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?

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

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

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$

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!

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)$.

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$

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.

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.

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.

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$

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.