Sets with ab+1-closure

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

Sets with ab+1-closure

G H J

Reveal topic tags

L

G H BBookmark kLocked kLocked NReply

Source: ELMO 2019 Problem 5, 2019 ELMO Shortlist N3

The post below has been deleted. Click to close.

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

202 posts

#1 h Jun 25, 2019, 9:52 PM • 3 Y

Y by Adventure10, Mango247, Funcshun840

Let $S$ be a nonempty set of positive integers such that, for any (not necessarily distinct) integers $a$ and $b$ in $S$ , the number $ab+1$ is also in $S$ . Show that the set of primes that do not divide any element of $S$ is finite.

Proposed by Carl Schildkraut

This post has been edited 1 time. Last edited by pieater314159, Jun 27, 2019, 9:46 PM

Z K Y

The post below has been deleted. Click to close.

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

539 posts

#2 h Jun 25, 2019, 10:05 PM • 2 Y

Y by Adventure10, Mango247

Glancing at this problem, does the solution involve the fact that $ab+1$ is prime if $a$ and $b$ are prime?

Z K Y

The post below has been deleted. Click to close.

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

3564 posts

62861

#3 h Jun 25, 2019, 10:06 PM • 4 Y

Y by e_plus_pi, aopsuser305, Adventure10, Mango247

Solution

Z K Y

The post below has been deleted. Click to close.

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

3042 posts

#4 h Jun 25, 2019, 10:50 PM • 5 Y

Y by Pluto1708, Wizard_32, Pratik12, Adventure10, Kingsbane2139

Solution. Let $a_1,a_2,\ldots ,a_k$ be all the distinct residues modulo $p$ of elements in $S$ and $p\nmid a_i$ for all $i = 1,2,\ldots, k$ , where $p$ is a prime.

If $a_ia_j + 1\equiv a_ia_l + 1\pmod p$ for some $i,j,l$ and $j\neq l$ , then $a_i(a_j - a_l) \equiv 0 \pmod p$ . But $p\nmid a_i$ , so $p\mid a_j - a_l$ which is false. This gives us that $a_ia_1 + 1, a_ia_2 + 1, \ldots , a_ia_k+1$ are all distinct residues modulo $p$ . Also note that as $a_1,a_2,\ldots, a_k$ are the residues modulo $p$ of the elements of $S$ , the residue $a_ia_j + 1 \pmod p$ also is in $\{a_1,a_2,\ldots ,a_k\}$ .

This gives us $\{a_ia_1 + 1,a_ia_2 + 1,\ldots ,a_ia_k + 1\} \equiv \{a_1,a_2,\ldots ,a_k\} \pmod p$ for any $i = 1,2,\ldots ,k$ . Summing up both the sets modulo $p$ gives us $a_i(a_1+a_2+\ldots +a_k) + k \equiv (a_1+a_2+\ldots +a_k)\pmod p \implies (a_i - 1)(a_1+a_2+\ldots + a_k) \equiv -k \pmod p \text{ for any i} = 1,2,\ldots ,k.$ If $p\mid a_1+a_2+\ldots + a_k$ , then $p\mid -k$ , so $k\geq p$ but as none of $a_i$ 's are divisible by $p$ , we get a contradiction. Therefore $p\nmid a_1+a_2+\ldots +a_k$ , so $a_i - 1 \equiv \frac{-k}{a_1+a_2+\ldots + a_k} \pmod p \text{ for any i} = 1,2,\ldots ,k.$ If $k>1$ , then $a_1 - 1 \equiv \frac{-k}{a_1+a_2+\ldots + a_k} \equiv a_2 - 1\pmod p$ which is false as $a_1,a_2$ are distinct residues modulo $p$ . Therefore we have, $k = 1$ . This means that if $p\nmid$ any element of $S$ , then the number of possible residues of $S$ modulo $p$ is exactly one.

Now as $S$ is non-empty, say $a\in S$ . We claim that all primes greater than $a^2 - a + 1$ divide some element in $S$ . Suppose there is a prime $p$ greater than $a^2 - a + 1$ which does not divide any element of $S$ . We proved that then the number of possible residues of $S$ modulo $p$ is exactly one which is $a\pmod p$ . Therefore $a^2 + 1 \equiv a \pmod p$ , so $p\mid a^2 - a+1$ or $p\leq |a^2 - a + 1|$ , but as $a^2 - a + 1 = \left(a - \frac{1}{2}\right)^2 + \frac{3}{4} \ge 0$ and as $p>a^2 - a + 1$ , we get that this is false. Therefore we get that all primes greater than $a^2 - a + 1$ will divide at least one element of $S$ . Further, as $a^2 - a + 1$ is finite, only finite primes exist which do not divide any element of $S$ and we are done. $~\blacksquare$

This post has been edited 1 time. Last edited by TheDarkPrince, Jun 25, 2019, 10:55 PM

Z K Y

The post below has been deleted. Click to close.

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

1595 posts

#5 h Jun 25, 2019, 10:51 PM • 15 Y

Y by tapir1729, Hamel, WolfusA, Wizard_32, FadingMoonlight, junioragd, microsoft_office_word, Aimingformygoal, IMO-Fe, Jalil_Huseynov, PROA200, Adventure10, Mango247, panche, Funcshun840

Fix an element $s\in S$ . Any prime $p\nmid s^2-s+1$ works. Assume not.

Let $\{x_1,x_2,\hdots,x_n\}$ are all different residues of $S$ in $\pmod p$ . Then for any $a\in\{x_1,\hdots,x_n\}$ , we have $\{ax_1+1,ax_2+1,\hdots,ax_n+1\}$ are $n$ different residues of $S$ . They must be the same set thus
$a(x_1+x_2+\hdots+x_n)+n\equiv (x_1+x_2+\hdots+x_n)\pmod p$ Let $T=x_1+\hdots+x_n$ . Clearly $T\not\equiv 0\pmod p$ as otherwise $n=p$ , which means all residues are in $S$ . Thus $(a-1)\equiv\tfrac{-n}{T}\pmod p$ for any $a\in\{x_1,\hdots,x_n\}$ .

This forces $n=1$ . So if $x_1=s$ , then $s^2+1\in S\implies s^2+1\equiv s\pmod p$ . This means $p\mid s^2-s+1$ , contradiction.

Z K Y

The post below has been deleted. Click to close.

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

GetOffTheInternet

7 posts

GetOffTheInternet

#6 h Jun 26, 2019, 12:48 AM • 3 Y

Y by zephyr7723, Adventure10, MS_asdfgzxcvb

The result follows from the following statement.

If $S$ is a set of residues modulo a prime $p$ such that $S$ contains $SS + 1$ and does not contain $0$ , then $S$ is a singleton.

A set of integers clearly cannot be constant modulo an infinity of primes.

Proof. The number of elements of $SS$ is at least $|S|$ (we are now in the multiplicative group of nonzero residues) and equality holds only if $S$ is a coset of a subgroup. This means that for $k = |S|$ we have $k \mid p - 1$ and the elements of $S$ are the $k$ solutions of an equation $a^k = c$ . Any element of $SS$ satisfies $z^k = c^2$ . As $z + 1$ is an element of $S$ , we also know that $(z + 1)^k = c$ . So the polynomials $z^k - c^2$ and $(z + 1)^k - c$ have the same $k$ roots. This means that they must be equal as formal polynomials. However, if $k > 1$ , then the linear term in one has coefficient $0$ and in the other $k$ .

Z K Y

The post below has been deleted. Click to close.

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

111 posts

#7 h Jun 26, 2019, 2:25 AM • 2 Y

Y by top1csp2020, Adventure10

My sketch: By Dirichlet, pair up a.b=-1 (mod p) so the number of remainder of S mod p has an upper bound m<=p-1/2. Thus by maximal arguement and primitive root, we reduce to consider modulo p-1, maxsum < 2p-4. By |A+A|>=2|A|-1 and Dirichlet, we reduce to consider 2 case. If |A+A|=2|A|-1 thus arithmetic progression so sum up all remainder have contradiction. If |A+A|=2|A|, prove that it only happen when |A|<=4 thus by case work and choose p large we have q.e.d

This post has been edited 3 times. Last edited by nguyenhaan2209, Jun 26, 2019, 2:32 AM

Z K Y

The post below has been deleted. Click to close.

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

3070 posts

#9 h Jun 26, 2019, 2:49 AM • 3 Y

Y by MathbugAOPS, Haaaa, Adventure10

Pick any two distinct elements $a,b$ in $S$ and choose any prime $p$ so that $p$ does not divide $a,b,a-b$ ; we'll prove that $S$ has a number divisible by $p$ . Since only finitely many primes can not be chosen, this will imply the result. From now on, reduce $S$ modulo $p$ . For contradiction, assume $0\not\in S$ .

Lemma: If $x,y\in S$ , then $(y-1)/x\in S$ .
Proof
Now $a,b\in S$ , so by our lemma, $(b-1)/a\in S$ , so $\left(\tfrac{b-1}{a}-1\right)/b=(b-a-1)/ab\in S$ . But that means $\tfrac{b-a-1}{ab}\cdot a+1=\tfrac{2b-a-1}{b}\in S$ , and so $\tfrac{2b-a-1}{b}\cdot b+1=2b-a\in S$ . Using the same argument on $(b,2b-a)$ , we see that $2(2b-a)-b=3b-2a\in S$ , and similarly $2(3b-2a)-(2b-a)=4b-3a\in S$ , and in general $b+n(b-a)\in S$ for integer $n$ . But $p\not | b-a$ , so by choosing $n\equiv -b/(b-a)\pmod{p}$ , we get a contradiction to $0\not\in S$ . This completes our proof. $\blacksquare$

Z K Y

The post below has been deleted. Click to close.

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

109 posts

#11 h Jun 26, 2019, 4:53 AM • 1 Y

Y by Adventure10

$\textbf{VERY CUTE PROBLEM :D}$

Let $a$ be a random element of $S$ . We consider only those elements of $S$ that are generated by $a$ (formally, the elements generated by $a$ satisfy the following: $a$ is generated by itself, $a\cdot a+1=a^2+1$ is generated by $a$ , then if $u$ and $v$ is generated by $a$ , so is $uv+1$ ). Call their set $S'$ . Clearly $S'$ is included in $S$ and if $u,v\in S'$ , then $uv+1\in S'$ . It suffices to prove that there are finitely many primes not dividing any element of $S'$ .

We prove that if $p$ is a prime such that $p>2a^2$ , then $p|u$ for some $u\in S'$ .

Let $T=\{u(\mod~p)~:~u\in S'\}$ . Suppose $0\not \in T$ . If $a^2+1\equiv a(\mod~p)$ , then $p|a^2-a+1$ so $p<|a^2-a+1|$ , false. So $T$ must have at least $2$ elements.

Let $T=\{a_1,a_2,\cdots ,a_m\}$ where $2\le m\le p-1$ , since $0\not \in T$ .

Note that $a_iT+1$ is contained in $T$ by the definition of $T$ . Moreover, since $a_i\not =0$ , $|a_iT+1|=|T|$ . Therefore, $a_iT+1=T$ , for all $i=\overline{1,m}$ .

This implies that $\sum_{j=1}^m(a_ia_i+1)\equiv \sum_{j=1}^ma_j (\mod~p)$ , so $a_is+m\equiv s(\mod~p)$ , where $s=\sum_{j=1}^ma_j$ . If $s\equiv 0(\mod~p)$ , we also get $m\equiv 0(\mod~p)$ , impossible, since $2\le m\le p-1$ . Therefore $s\not \equiv 0(\mod~p)$ so it has an inverse modulo $p$ .

But then for all $i$ we have $a_i\equiv 1-ms^{-1}(\mod~p)$ , which means all elements of $T$ are equal modulo $p$ i.e. they are equal (since all are residues modulo $p$ ). This is however a contradiction, since it implies $m=|T|=1$ , while we already got that $m\ge 2$ !

All these being said, we must have $0\in T$ , hence the conclusion follows.

Z K Y

The post below has been deleted. Click to close.

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

643 posts

#12 h Jun 26, 2019, 5:05 AM • 6 Y

Y by paragdey01, leibnitz, A-Thought-Of-God, PNT, Adventure10, Mango247

Easy for P5?

pieater314159 wrote:

Let $S$ be a nonempty set of positive integers such that, for any (not necessarily distinct) integers $a$ and $b$ in $S$ , the number $ab+1$ is also in $S$ . Show that the set of primes that do not divide any element of $S$ is finite.

Solution. We generalise the result and prove the following claim :

Claim. Let $p$ be a prime which doesn't divide any element of $S.$ Then it follows that $p\mid \min\{S\}^2-\min\{S\}+1.$
Proof. Let $R=\{r_1,r_2,r_3,\ldots,r_k\}$ be the set obtained after reducing $S$ modulo $p,$ here $r_i$ 's are distinct modulo $p.$ For now, assume $k\ge 2.$ Since $p$ doesn't divide any element of $S,$ so $k\le p-1$ . Consider the set $R'=\{r_1^2+1,r_1r_2+1,r_1r_2+1,\ldots,r_1r_k+1\},$ note that all the elements are distinct modulo $p,$ also by definition of $R,$ we must have $R'\subseteq R$ which forces $R=R'.$ Now adding all elements of $R$ we obtain $s=r_1+r_2+\cdots+r_k$ and adding all elements of $R'$ we get $k+r_1s,$ therefore
$s\equiv k+r_1s\pmod{p}$ We cannot have $p\mid s$ as $k\le p-1.$ Now, we can similarly obtain that $s\equiv k+r_is\pmod{p}$ holds for all $i=1,2,3,\ldots,k,$ which would imply $r_i$ 's are same modulo $p$ . Contradiction! Thus the only possibility is that $k=1,$ but then we get $r_1\equiv r_1^2+1\pmod{p}\implies p\mid r_1^2-r_1+1.$ Since $\min\{S\}^2-\min\{S\}+1\ne 0,$ hence the claim. And we are done. $~\blacksquare$

This post has been edited 2 times. Last edited by ayan.nmath, Jun 26, 2019, 5:11 AM

Z K Y

The post below has been deleted. Click to close.

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

272 posts

#14 h May 22, 2020, 10:15 PM

Y by

pieater314159 wrote:

Let $S$ be a nonempty set of positive integers such that, for any (not necessarily distinct) integers $a$ and $b$ in $S$ , the number $ab+1$ is also in $S$ . Show that the set of primes that do not divide any element of $S$ is finite.

Proposed by Carl Schildkraut

Let $a$ be any element of $S$
We will show that a prime $p$ which does not divide $a^2-a+1$ must divide some element of $S$ and hence proof will be over.
Let $\phi :\mathbb{Z}\rightarrow\mathbb{Z}/p\mathbb{Z}=\mathbb{Z}_p$ be the canonical homomorphism (basically takes any $n$ to $n$ (mod $p$ ) )
Let $\phi(a)=a_1$ and $\phi[S]=R$ , if $0\in R$ then we are done so assume $0\notin R$
Let $R=\{a_1,a_2,\cdots,a_t\}$ as $p$ does not divide $a^2-a+1$ and $0\notin R$ we get that $1<t<p$
(Edit : I guess the $t>1$ requires a bit clarification, we have $a\in R$ and $a^2+1\in R$ and as $p$ does not divide $a^2-a+1$ , these two are unequal)
Note that the elements $a_1a_i+1,a_2a_i+1,\cdots,a_ta_i+1$ are all different for a fixed $i$ , but by given condition they all lie in $R$ and hence they are just an permutation of $R$
This in turn gives that the sets $\{a_1a_i,a_2a_i,\cdots,a_ta_i\}$ are same for all $i$ , now let $g_i=\frac{a_i}{a_1}$ then dividing all these sets by $a_1^2$ we get that.
The sets $\{g_i,g_2g_i,g_3g_i,\cdots,g_tg_i\}$ are all same and in particular they are all same as $G=\{1,g_2,g_3,\cdots,g_t\}$
This gives us that $G$ is a group under multiplication in the ring $\mathbb{Z}_p$ and hence a subgroup of $\mathbb{Z}_{p}^{\times}$
As $G$ is a subgroup of a cyclic group it itself must be cyclic and hence it must be of form $\{1,g,g^2,\cdots,g^{t-1}\}$
Again viewing in $\mathbb{Z}_p$ we have $\displaystyle\Sigma_{g\in G} g=1+g+g^2+...+g^{t-1}= \frac{g^t-1}{g-1}=0$ (Here we used that $t>1\implies g\neq 1$ )
Multiplying by $a_1$ gives $\Sigma_{i=1}^t a_i=0$
Remember that $\{a_1,a_2,a_3,\cdots,a_t\}$ and $\{a_1^2+1,a_1a_2+1,a_1a_3+1,\cdots,a_1a_t+1\}$ are permutations of each other.
Summing both of them we get $0=t (mod p) \implies p|t$ but this contradicts $1<t<p$ .
Hence proved.

This post has been edited 1 time. Last edited by BOBTHEGR8, Aug 24, 2020, 7:00 PM

Z K Y

The post below has been deleted. Click to close.

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

square_root_of_3

78 posts

square_root_of_3

#15 h Jul 24, 2020, 10:49 PM

Y by

I may have overcomplicated this problem, but I haven't seen a similar solution so I decided to post it. We will use the fact that every polynomial of degree $\leqslant n$ has at most $n$ zeroes in $\mathbb Z_p$ , and the fact that there exists a primitive root modulo $p$ for odd primes $p$ .

Let $a \in S$ , and let $p>a^2+1$ be a prime. We'll prove that $p \mid x$ for some $x \in S$ . Suppose that this isn't true. Let $\{x_1,\ldots,x_k\}$ be all elements of $\mathbb Z_p$ which are represented in $S$ . We have $p>k\geqslant 2$ since $a$ and $a^2+1$ aren't equal in $\mathbb Z_p$ .

Now, we know that for all $i \in \{1,\ldots, k\}$ , $x_iS+1=S$ , which implies $x_iS=x_jS$ for all $i, j \in \{1,\ldots, k\}$ . Let $g$ be a primitive root modulo $p$ , and let $x_i=g^{a_i}$ , and suppose $0\leqslant a_1< a_2< \ldots <a_k<p-1$ . Now we know that as $i$ runs over $\{1,\ldots, k\}$ , the sets $\{a_i+a_1,a_i+a_2, \ldots, a_i+a_k\}$ are all equal modulo $p-1$ . This means that for every $j \in \{2, \ldots,k-1\}$ , there exists a unique index $m_j$ such that $a_1+a_k\equiv a_j+a_{m_j} \pmod{p-1}$ . However, since $|a_1+a_k-a_j-a_{m_j}|<p-1$ , equality holds. Now, because of $(a_i)$ being increasing, we have the following equalities: $a_1+a_k=a_2+a_{k-1}=\ldots=a_{k}+a_1.$ Similarly, for $j \in \{2,\ldots, k\}$ , there exists a unique index $m_j$ such that $2a_i \equiv a_j+a_{m_j} \pmod{p-1}$ , and since $2a_1<a_j+a_{m_j}<2a_1+2(p-1)$ , we have $2a_1=a_j+a_{m_j}-(p-1)$ . Due to $(a_i)$ being increasing, we have the following equalities: $2a_1=a_2+a_k-(p-1)=a_3+a_{k-1}-(p-1)=\ldots=a_k+a_2-(p-1).$ Substracting equalities $a_j+a_{k+1-j}=a_{j+1}+a_{k-j}$ and $a_{j+1}+a_{k+1-j}=a_{j+2}+a_{k-j}$ , we get $a_{j+1}-a_j=a_{j+2}-a_{j+1}$ for $0<j<k-1$ , which implies that $(a_i)$ form an arithmetic progression, with difference $d=\dfrac{p-1}{k}$ . In particular, $k \mid p-1$ . Let $g^{a_1}=u$ . Now, since $a_j=a_1+(j-1)\frac{p-1}{k}$ we can write $S=uQ$ , where $Q$ is the set of all elements of $\mathbb Z_p$ whose order divides $k$ , i.e. all $x \in \mathbb Z_p$ which satisfy $p \mid x^k-1$ .

Now, if $ux \in uQ$ , then $u\cdot(ux)+1=u^2x+1 \in uQ$ , which implies $ux+u^{-1} \in Q$ . This implies that the polynomials $(ux+u^{-1})^k-1$ and $(ux)^k-u^k$ have $k$ common zeroes (the set of common zeroes is $Q$ ), so their difference, which is of degree $\leqslant k-1$ , is a zero polynomial in $\mathbb Z_p$ . However, comparing coefficients alongside $x^{k-1}$ , we conclude that $p \mid ku^{k-2}$ , which is a contradiction since $u$ is not divisible by $p$ and $k<p$ .

This post has been edited 1 time. Last edited by square_root_of_3, Jul 24, 2020, 10:55 PM

Z K Y

The post below has been deleted. Click to close.

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

558 posts

#17 h Nov 5, 2020, 7:54 PM • 4 Y

Y by MarkBcc168, A-Thought-Of-God, amar_04, Mango247

Let $a$ denote the minimum element of $S$ . We claim that any prime $p$ which doesnt divide any element of $S$ divides $a^2-a+1$ , which finishes.

Work in $\mathbb F_p.$ Let $X=$ $\{x_1,x_2,\dots,x_k\}$ denote the distinct residues of the elements of $S$ modulo $p$ . By assumption, $x_i \neq 0$ . Now pick any $x\in X$ and note that the set $xX+1$ must be the same as $X$ by the condition of the problem. This gives:

$x\left (\sum_{i=1}^{k} x_i\right) + k =\sum_{i=1}^{k} x_i$ $\implies x = 1- \frac k {\sum_{i=1}^{k} x_i}$
Since $x$ was arbitrary, $k=1$ . So $a^2+1\equiv a\pmod p$ , so $p\mid a^2-a+1$ , as desired. $\square$

Z K Y

The post below has been deleted. Click to close.

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

GeronimoStilton

1521 posts

GeronimoStilton

#18 h Apr 3, 2021, 3:08 PM

Y by

Solution with VulcanForge and awang11.

The key claim is that $p$ divides some element of $S$ if there are distinct $a,b\in S$ modulo $p$ . To see this, consider the functions $f:x\mapsto ax+1$ and $g:x\mapsto bx+1$ modulo $S$ . Clearly they are both invertible or we are done, so $f(S)=g(S)=S$ . Let $K$ denote the sum of the distinct elements of $S$ modulo $p$ . Then we get
$aK+|S|=bK+|S|=K$ modulo $p$ .
Since $a\ne b$ modulo $p$ , this implies $K=0$ , so $|S|$ is congruent to $0$ modulo $p$ . As $|S|$ cannot contain $0$ elements modulo $p$ , this implies the desired.

Now, we are done because $p$ can only not divide some element of $S$ if for a fixed $a\in S$ we have $p\mid a^2+1-a$ , which is finite.

This post has been edited 1 time. Last edited by GeronimoStilton, Apr 3, 2021, 3:08 PM

Z K Y

The post below has been deleted. Click to close.

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

238 posts

#19 h Apr 9, 2021, 5:59 PM

Y by

Suppose that there are infinitely such primes $p$ .

Work in $\mathbb F_p$ and let $S=\{a_1,a_2,...,a_n\}$ .

Claim: If $a \in S$ , then $-a$ does not belongs to $S$ .
Proof: Suppose that there is an $a \in S$ such that $-a \in S$ . Hence observe that since the $a_i$ are all distinct, $a.a_i+1$ are all distinct for all $1 \leq i \leq n$ . $\implies \{a_1,a_2,...,a_n\} = \{a.a_1+1,a.a_2+1,...,a.a_n+1\} \quad (\star)$ The same is valid for $-a$ , so $x,-x$ for all $x \in S$ . Thus $\sum_{i=1}^n a_i=0$ .

From $(\star)$ , $\sum_{i=1}^n a_i = a(\sum_{i=1}^n a_i) +n= n$ , so $n=0$ and then $p|n$ , so $n=0$ since $n$ is bounded and $p$ can be large enough, but $n$ clearly cannot be $0$ . This proves the claim. $\square$

From the claim, $x \mapsto x^2+1$ is a bijection under $S$ $\pmod{p}$ . Hence, $\{a_1,a_2,...,a_n\}=\{a_1^2+1,a_2^2+1,...,a_n^2+1\}$ $\implies (\sum_{i=1}^n a_i^2) +n = \sum_{i=1}^n a_i = a_j(\sum_{i=1}^n a_i)+n$ for all $1 \leq j \leq n$ , so $\sum_{i=1}^n a_i^2= (\sum_{i=1}^n a_i)a_j$ . Summing everything, $(\sum_{i=1}^n a_i)^2= n \sum_{i=1}^n a_i^2$ , so $p|(\sum_{i=1}^n a_i)^2-n \sum_{i=1}^n a_i^2$ , but since $(\sum_{i=1}^n a_i)^2-n \sum_{i=1}^n a_i^2$ is bounded and $p$ can be large enough, we must have $(\sum_{i=1}^n a_i)^2-n \sum_{i=1}^n a_i^2=0$ (not just in $\mathbb F_p$ ), but this implies that all $a_i$ must be equal, which is clearly a contradiction, so 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.

867 posts

#20 h Apr 16, 2021, 7:36 PM • 3 Y

Y by jelena_ivanchic, I_am_human, Mango247

We work in $\mathbb F_p$ . Let $p$ be a prime such that $p\not|m,\forall m\in S$ .
Claim. $a,b\in S\implies a+n(a-b)\in S,\forall n\in\mathbb N_0$ ( $a$ and $b$ are not necessarily distinct).
Proof. We induct on $n$ . Clearly, $n=0$ works and now we assume it's true for all $n<M$ .
Note that as $|S|>0$ , define $x_n:=bx_{n-1}+1;a_1=a$ for all $n\geq 2\implies x_i\in S$ and thus, $a,b\not\equiv_p 0,1$ . Hence, $x_{p-1}=ba^{p-2}+\sum_{i=0}^{p-3} a^i\equiv_p \frac{b}{a}-\frac{1}{a}$ Now define, $y_n:=x_{p-1}y_{n-1}+1;y_1=b$ for all $n\geq 2\implies y_i\in S$ . Thus,
$y_{p-1}=x_{p-1}b^{p-2}+\sum_{i=0}^{p-3}b^i\equiv_p \frac{x_{p-1}}{b}-\frac 1 b\equiv_p\frac{b-a-1}{ab}\in S\overset{sym}{\implies}\frac{a-b-1}{ab}\in S$ Also, if $\ell\in S\implies \ell b+1\in S\implies \ell ab+a+1\in S$ and thus, taking $\ell=(a-b-1)/ab$ , we get $a+(a-b)\in S$ . Thus, we may assume $M>2$ . Now, by our inductive hypothesis, we know that $(a+(M-1)(a-b), a+(M-2)(a-b))\in S^2\implies 2[a+(M-1)(a-b)]-[a+(M-2)(a-b)]=a+M(a-b)\in S$ which completes the proof of our claim.
If $a\not\equiv_p b$ , then $\exists w\in\mathbb N$ such that $a+w(a-b)\equiv_p 0$ which is absurd. Thus, $p$ must be a prime divisor of $a-b$ if $a,b\in S$ . Also note that $a\in S\implies a^2+1\in S\implies p|a^2-a+1$ and thus, number of such primes $p$ is finite as $x^2-x+1=0$ has no solution in $\mathbb R$ .

Z K Y

The post below has been deleted. Click to close.

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

5606 posts

#21 h Oct 26, 2021, 9:10 PM

Y by

Suppose $k$ is an element of $S$ .

Lemma: Any prime $p\nmid k^2-k+1$ is a prime divisor of some element in $S$ , which clearly finishes.
Proof: Assume not.

Call the distinct residues $\pmod p$ in $S$ , $r_1,r_2,r_3\ldots r_n$ , with $n<p$ . Since for any $1\le i\le r$ , $r_ir_1+1, r_ir_2+1, r_ir_3+1, \ldots, r_ir_n+1$ have distinct residues $\pmod p$ , their residues are some permutation of $r_1,r_2,r_3\ldots r_n$ .

Now, we can add them up $r_i(r_1+r_2+\ldots+r_n)+n\equiv r_1+r_2+\ldots+r_n\pmod p$ . Let $r_1+r_2+\ldots+r_n=x$ . So $r_i\cdot x -x=x(r_i-1) \equiv -n\pmod p$ .

Claim: $p\nmid x$ .
Proof: If not, then $n\equiv0\pmod p$ , which implies $n=p$ , a contradiction.

Since $x$ is relatively prime to $p$ , if there are two distinct $r_i$ , then $x(r_i-1)$ will have two different residues. So there must be only one residue $r_i$ .

Now, we have $r_1^2+1\equiv r_i\pmod p\implies p|r_i^2-r_i+1.$

Z K Y

The post below has been deleted. Click to close.

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

1481 posts

CT17

#22 h Nov 20, 2021, 9:52 PM

Y by

Does this work?

Claim: Let $p$ be a prime and $T$ a set of nonzero residues mod $p$ with at least $2$ elements. Then there exist not necessarily distinct $s,t\in T$ such that $st+1\not\in S$ .

Proof: We will work entirely mod $p$ . Let $T = \{a_1,a_2,\dots ,a_n\}$ with $n\ge 2$ and assume the contrary (there do not exist such $s$ and $t$ ). Since the elements of $T$ are nonzero we must have $a_ia_j+1\neq a_ia_k+1$ for any distinct $1\le i,j,k\le n$ . Hence, for any $i$ , $a_1a_i+1, a_2a_i+1, \dots , a_na_i+1$ must be a permutation of $a_1,a_2,\dots ,a_n$ . In particular,

$a_1 + a_2 + \dots + a_n = a_1a_i + 1 + a_2a_i + 1 + \dots + a_na_i + 1 = a_i(a_1 + a_2 + \dots + a_n) + n$ .

If $a_1+a_2+\dots +a_n = 0$ we obtain $n=0$ , implying $n=p$ since $n>2$ which means $0\in T$ , a contradiction. Otherwise, for $i\neq j$ we have

$a_1 + a_2 + \dots + a_n = a_i(a_1 + a_2 + \dots + a_n) + n\neq a_j(a_1 + a_2 + \dots + a_n) + n = a_1 + a_2 + \dots + a_n$ ,

also a contradiction and the lemma is proved.

Now, let $q$ be a prime such that the elements of $S$ take at least $2$ distinct residues mod $q$ . We aim to show that some element of $S$ is a multiple of $q$ . Indeed, if one of the residues is $0$ , we are already done. Otherwise, by the lemma we can continue adding residues that must appear in $S$ , one at a time, unless one of our residues is $0$ . But once one of our residues is $0$ , we are done.

Finally, it suffices to show that there are only finitely many primes $r$ such that the elements of $S$ are all equivalent mod $r$ . Assume the contrary, then every one of the primes divides $s-t$ for any distinct $s,t\in S$ , absurd 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.

966 posts

#23 h Dec 29, 2021, 4:50 PM • 2 Y

Y by centslordm, GioOrnikapa

Consider a prime $p$ not dividing any element of $S.$ Let $\{m_1, m_2, \dots m_n \}$ be the set of all residues of elements of $S \pmod{p},$ and let $T$ be their sum. For any $m_k \in \{m_1, m_2, \dots m_n \},$ we have that $\{m_1m_k+1, m_2m_k+1, \dots m_nm_k+1\}$ are $n$ distinct residues of $S.$ So then

$\{m_1m_k+1, m_2m_k+1, \dots m_nm_k+1\} = \{m_1, m_2, \dots m_n \}$
thus $m_kT + n = T \implies m_k-1 \equiv \frac{-n}{T} \pmod{p},$ since if $T = 0$ that means $n = p.$ This forces $n=1,$ and so for any arbitrary element $s$ in $S,$ $s-1 \equiv -1/s \pmod{p} \implies s^2-s+1 \equiv 0 \pmod{p}.$ But there are only a finite number of primes dividing $s^2-s+1,$ contradiction.

Z K Y

The post below has been deleted. Click to close.

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

2726 posts

#24 h Mar 19, 2022, 10:02 PM • 1 Y

Y by megarnie

Let $p$ be a prime not dividing any $x \in S$ .

Claim: All elements of $S$ leave the same residue modulo $p$ .
Proof: Let $r_1, \ldots , r_k$ be the $k$ distinct (clearly nonzero) residues left by elements of $S$ modulo $p$ , where $k \in [1, p-1]$ . Define set $A_i = \{r_ir_j + 1\}_{j = 1}^{k}$ . Note that each $A_i$ has size $k$ , is entirely contained in $S$ , and no two elements leave the same residue: indeed, $p \mid r_a(r_b - r_c)$ is impossible for any $a, b, c$ .

Note that this means each $A_i$ is a complete residue set. That is, $A_i = \{r_1, \ldots , r_k\}$ . Hence, summing both sets, we get $(r_i - 1)(r_1 + \ldots + r_k) + k \equiv 0 \pmod p.$ First, check that if $r_1 + \ldots + r_k = 0 \pmod p$ then $k \equiv 0 \pmod p$ , impossible given the range of $k$ . Then, that means $r_i \equiv 1 - k(r_1 + \ldots + r_k)^{-1} \pmod p$ is a fixed value across all $i$ , so in fact all $r_i$ are the same. However, the assumption is also that they are all distinct, so $k = 1$ , as desired.

Alas, this also means $r_i \equiv 1 - r_i^{-1} \pmod p \iff p \mid r_i^2 - r_i + 1$ for all $r_i$ . However, if we just fix $r_i$ as any element in $S$ , this limits the number of values $p$ can possibly be to the number of divisors of a positive integer, which is clearly finite, so we win.

Z K Y

The post below has been deleted. Click to close.

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

5001 posts

#25 h Mar 24, 2022, 8:37 PM

Y by

Consider any fixed prime $p$ and let $S_p=\{a_1,\ldots,a_k\}$ be the distinct remainders upon dividing all elements in $S$ by $p$ . I claim that either $k=1$ or $k=p$ . Indeed, note that if $0 \in S_p$ , then $1 \in S_p$ , so then if $n \in S_p$ we have $n+1 \in S_p$ as well, so $S_p=\{0,\ldots,p-1\}$ . Suppose $k \neq p$ , so $0 \not \in S_p$ To prove this, pick some index $1 \leq i \leq k$ . Then since $a_i \not \equiv 0 \pmod{p}$ , all $a_ia_j+1$ are distinct modulo $p$ (ranging across $1 \leq j \leq k$ ), which yields $k$ residues. It follows that
$\{a_ia_1+1,\ldots,a_ia_k+1\} \equiv \{a_1,\ldots,a_k\} \pmod{p},$ so summing across all $k$ , we have
$a_i(a_1+\cdots+a_k)+k \equiv a_1+\cdots+a_k \implies (a_i-1)(a_1+\cdots+a_k) \equiv -k \pmod{p}.$ As $k \not \equiv 0 \pmod{p}$ because that would imply $k=p$ , it follows that $a_1+\cdots+a_k \not \equiv 0 \pmod{p}$ either, so $a_i-1$ is constant mod $p$ and thus $k=1$ , as desired.
Now, if $p \nmid n$ for all $n \in S$ for some prime $p$ , we must have $|S_p|=1$ and thus $p \mid n^2-n+1$ for all $n$ in $S$ . Clearly there are a finite number of $p$ that satisfy this (just take an arbitrary $n$ ), so we're done. $\blacksquare$

Z K Y

The post below has been deleted. Click to close.

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

108 posts

#26 h Jun 15, 2023, 11:46 AM

Y by

Take prime $p$ not dividing $w^2-w+1$ for some $w\in S$ - there are only finitely many that do not. Let $T=\{c_1,c_2,\ldots, c_k\}\subseteq \{0,1,2,\ldots, p-1\}$ be the set of remainders of $a\in S$ modulo $p$ . Assume FTSOC that $k\neq 1$ but $0\not\in T$ .

By writing out $c_ic_j+1$ for $1\leq i\leq j\leq k$ , we have $m^2$ numbers, each congruent to some $c_l$ . If $m+1$ of $c_ic_j+1$ are congruent to some $c_l$ , then by Pigeonhole Principle, there exists $x,y,z$ with $y\neq z$ such that
$c_xc_y+1\equiv c_l\equiv c_xc_z+1\pmod{p} \implies c_y\equiv c_z\pmod{p}\implies y=z$ because $c_x\not\equiv 0\pmod{p}$ , a contradiction. Thus, each $c_l$ is congruent to exactly $m$ $c_ic_j+1$ 's.

By Pigeonhole Principle, choose $t$ such that $c_i^2+1\equiv c_t\pmod{p}$ for at most one $1\leq i\leq k$ . Then there are $m-1\geq 1$ indices that form $m-1$ pairs, so we have $x,y,z$ with $y\neq z$ such that $c_xc_y+1\equiv c_t\equiv c_xc_z+1\pmod{p}$ , a similar contradiction. Thus, $m=1$ . Then
$c_1^2+1\equiv c_1\pmod{p}\implies p\mid c_1^2-c_1+1$ a contradiction, because $c_1\equiv w\pmod{p}$ since $w\in S$ . Thus, $0\in T$ as needed.

Z K Y

The post below has been deleted. Click to close.

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

5 posts

Solal

#27 h Nov 28, 2023, 11:48 AM

Y by

Let $p > \min(S)^2-\min(S)+1$ be a prime and let $S_p = \{x \in [\![0, p-1]\!] \; | \; \exists y \in S, p \mid x-y\}$ . Suppose $0 \not \in S_p$ and consider :
$f(x) = \sum_{a\in S_p} x^a.$ Since $b \mapsto ab+1 \pmod p$ forms an injective map from $S_p$ to $S_p$ where $a\in S_p$ , it is also a bijective map and we deduce that $ef(e^a) = f(e)$ whenever $a \in S_p$ where $e^{p-1}+\ldots+1 =0$ .

Consequently for $a,b \in S$ :
$e^af(e^{ab}) = f(e^a)= \frac{f(e)}{e} = f(e^b) = e^bf(e^{ab}).$ Hence $a\equiv b \pmod p$ or $f(e^{ab})=0$ .

Lemma. Assume $f \in \mathbb{Q}[X]$ satisfies $f(e) = 0$ where $g(e) =e^{p-1}+\ldots+e+1 =0$ , then $g = X^{p-1}+\ldots+X+1 \mid f$ .

Consider $\mathrm{gcd}(f,g) \in \mathbb{Q}[X]$ , it has degree greater than $1$ and divides $g$ which is irreductible over $\mathbb{Q}[X]$ so it equals $g$ . Hence $g \mid f$ .

Assume $f(e^{ab})=0$ , then since $0\not \in S_p$ we get that $e^{ab}$ is a root of $\frac{f}{X}$ and that $g(e^{ab})=0$ . Hence $g \mid \frac{f}{X}$ , but this is absurd because $0\leq \deg(f/X) <p-1$ .

Consequently $p \mid a-b$ and with $a= \min(S)$ and $b = a^2+1 \pmod p$ we get $p \mid a^2-a+1$ , which is an absurdity and concludes.

This post has been edited 3 times. Last edited by Solal, Nov 28, 2023, 11:50 AM
Reason: typo^3

Z K Y

The post below has been deleted. Click to close.

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

419 posts

#28 h Mar 31, 2024, 3:22 PM

Y by

Let $m\in S$ be some random element from $S$ . There are only finitely many prime divisors of $m^2-m+1$ . We claim that if $p\nmid m^2-m+1$ then some element of $S$ is divisible by $p$ .

Suppose for contradiction that there is a prime that does not divide any element from $S$ . Let $\{a_1,a_2,\ldots,a_k\}$ be the elements from $S$ each with different residues $\pmod{p}$ covering all residues in $S$ . Let $x\in S$ be a random element in $S$ . Then, $\{xa_1+1, xa_2+1, \ldots, xa_k+1\}$ also consist of different residues $\pmod{p}$ , and since they cover all elements in $S$ , we have
$xa_1+1+xa_2+1+\cdots+xa_k+1 \equiv a_1+a_2+\cdots+a_k \pmod{p}$ $\Longrightarrow (1-x)(a_1+a_2+\cdots+a_k) \equiv k \pmod{p}$ But this holds for any element $x\in S$ . This means that $S\pmod{p}$ is constant. So, $m\equiv m^2+1\pmod{p}$ , which means that $p\mid m^2-m+1$ , which is impossible. $\blacksquare$

Z K Y

The post below has been deleted. Click to close.

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

198 posts

#29 h Apr 21, 2024, 3:43 PM

Y by

Amazing problem!, though kinda easy for P5.

Take any $a \in S$ and we'll prove that for every prime $p > a^2 - a + 1$ , there exists a positive integer $b \in S$ that is divisible by $p$ .

Let $f(x) = x^2 + 1$ . Then consider the sequence $a, f(a), f^2(a), \dots$ . By pigeonhole principle, there exists $f^i(a) \equiv f^j(a)$ , so we may pick the largest $k$ such that $a, f(a), f^2(a), \dots, f^{k-1}(a)$ leave different remainders divided by $p$ . Note that $p \nmid a^2 - a + 1 = f(a) - a$ , so we may assume $k \ge 2$ . It's clear that $k \le p$ . Let $a_i$ be the remainder of $f^i(a)$ divided by $p$ .

Claim: We can generate a remainder $r$ different from $a_0, a_1, \dots, a_{k-1}$ from $a_0, a_1, \dots, a_{k-1}$ unless $k = p$ .

Proof. Assume the contrary, $k \neq p$ and $\{a_ia_0 + 1, a_ia_1 + 1, \dots, a_ia_{k-1} + 1\} \equiv \{a_0, a_1, \dots, a_{k-1}\} (p)$ for all $0 \le i \le k-1$ . Since $k \ge 2$ , we can pick distinct $i, j$ from $\{0, 1, \dots, k-1\}$ . Thus, we have $\{a_ia_0 + 1, a_ia_1 + 1, \dots, a_ia_{k-1} + 1\} \equiv \{a_ja_0 + 1, a_ja_1 + 1, \dots, a_ja_{k-1} + 1\} (p)$ , so we get $p \mid (a_i - a_j)(a_0 + a_1 + \dots + a_{k-1})$ . Hence, $p \mid a_0 + a_1 + \dots + a_{k-1}$ . But, we have $\{a_ia_0 + 1, a_ia_1 + 1, \dots, a_ia_{k-1} + 1\} \equiv \{a_0, a_1, \dots, a_{k-1}\} (p)$ . Combined with the fact that $p \mid a_0 + a_1 + \dots + a_{k-1}$ , we see that $p \mid k$ , a contradiction. $\blacksquare$

By claim, we can generate different remainder $r$ from $a_0, a_1, \dots, a_{k-1}$ until $k = p$ , so at some point, we get a complete residue class modulo $p$ , which means that there is a positive integer $b$ such that $p \mid b$ , as wanted. $\blacksquare$

This post has been edited 2 times. Last edited by thdnder, Apr 21, 2024, 3:55 PM

Z K Y

The post below has been deleted. Click to close.

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

Gedagedigedagedago-

4 posts

Gedagedigedagedago-

#30 h Sep 1, 2024, 6:54 PM • 14 Y

Y by pikapika007, OronSH, ryanbear, ohiorizzler1434, GrantStar, mathleticguyyy, RaymondZhu, balllightning37, LLL2019, TestX01, Ywgh1, EpicBird08, Funcshun840, aidan0626

Gegagedigeda! Gegagedigedagedago! Finite set of primes? WHAT! Help me!

Like = Help

DING!

Create nugget set $T \subset S$ ! $T$ has all remainders on divide by Gegagedigedageda $p$ , excactly once. Fix $n \in S$ , map $u \mapsto nu+1 \pmod{p}$ is natural bigegagedijective! Conclusion: $\sum_{_{nugge}t \in T} { }_{nugge}t \equiv \sum_{_{nugge}t \in T} n {}_{nugge}t + 1 \pmod{p} \implies \forall n \in S (n-1)\sum_{_{nugge}t \in T} {}_{nugge}t \equiv -|T| \pmod{p}!$ Fake nugget for many gegagedesidue! Follow that: exists only one gegagedesidue in $S$ and $r^2 + 1 \equiv r \pmod{p}$ ! But only finite many prime divide $r^2 - r + 1$ ... gegagedigedagedago completion!

Z K Y

The post below has been deleted. Click to close.

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

8861 posts

#31 h Feb 19, 2025, 1:23 AM

Y by

Fix a prime $p$ , and consider all expressions modulo $p$ . The key claim is the following:

Claim: Let $k$ and $a$ be elements of $S$ . Then $k+\frac 1{a^2}+\frac 1a + 1 + a + a^2+a^3$ is also in $S$ .

Proof: Inductively, we may obtain that $k, ka+1, \dots, ka^n + a^{n-1} + \cdots + 1$ are in $S$ for any positive integer $n$ . In particular, $ka^{p-2} + a^{p-1} + \cdots + a + 1 = (k-1)a^{p-2} = \frac{k-1}a \in S$ too. Now, check that

$-\frac 1{a^2} \in S$ by setting $k=a$ and writing $a^{p-2} + a^{p-4} + \cdots + a +1 = - a^{p-3} = -\frac 1{a^2}$ implying that $-a^4 \in S$ , and
$\tfrac{k-1-a-a^2-a^3}{a^4} \in S$ by applying the transformation $k \to \frac{k-1}a$ four times to $k$ .

Thus, if $k \in S$ , then $\left(ka^2+a+1\right)\left(-\frac 1{a^2}\right) + 1 = -k-\frac 1a-\frac 1{a^2} + 1 \in S$ and $-a^4\left(\frac{k-1-a-a^2-a^3}{a^4}\right) + 1 = -k+2+a+a^2+a^3 \in S.$ Composing these two equations yields the result. $\blacksquare$

So now let $a$ be any element of $S$ , and let $p$ be any prime that does not divide $a^6 - 1$ . Then it follows that $d = \frac 1{a^2}+\frac 1a +1+a+a^2+a^3$ is a multiple of $p$ , and thus the residue $a+kd$ appears in $S$ for any $k \in \mathbb N$ . So there exists a multiple of $p$ in $S$ , as needed. Indeed, all but finitely many primes satisfy this constraint, so we are done.

Remark: This solution is a bit inefficient because in fact $p \nmid a^2+a+1$ works, but if it works it works.

This post has been edited 1 time. Last edited by HamstPan38825, Feb 19, 2025, 1:23 AM

Z K Y

The post below has been deleted. Click to close.

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

11 posts

#32 h Mar 28, 2025, 1:18 AM

Y by

Let p be a prime which doesnt divide any element in $\mathbb{S}$ but has at least 2 different residues in $\mathbb{S}$ . Let $Q$ be the set of all residues of numbers in S modulo p. Then we have $1<|Q|<p$ . Note that if $p<7$ this can never hold. We will consider set $Q$ in $\mathbb{F}_p$ We will consider all primes $\geq 7$ . Note that if $1 \in Q$ then for all $a \in Q$ , we have $a+1 \in Q$ . This is a contradiction as we will have every number modulo p by repeating this process. Hence $1 \not \in Q$ .

Now note that if $a \in Q$ then $a \cdot Q +1 = Q$ as $a \cdot Q +1$ has same cardinality as of $Q$ and every element of $a \cdot Q +1$ is an element of Q. Hence for all $a,b \in Q$ , we have
$a \cdot Q = Q-1 = b \cdot Q$ .

Now note that $(ab)Q = a(bQ) = a(Q-1) = aQ- a = Q-a-1$ , similarly $(ab)Q = b(aQ) = b(Q-1) = bQ- b = Q-b-1$ hence $Q-a = Q-b$ , therefore $\forall c \in Q , c+a-b \in Q$ . If we choose distinct a and b we get $c+t(a-b) \in Q$ for all $t$ , note that this implies all residues are in $Q$ which is a contradiction.
Hence if a prime has at least 2 residues in $\mathbb{S}$ , then it has all the residues. Hence all primes which are greater than second smallest element has an element in $\mathbb{S}$ that it divides. QED

Z K Y

The post below has been deleted. Click to close.

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

4187 posts

#33 h Apr 8, 2025, 9:52 PM

Y by

Purely construtive solution involving n^(1 mod 6), hidden for length)

This post has been edited 2 times. Last edited by john0512, Apr 8, 2025, 10:10 PM

Z K Y

The post below has been deleted. Click to close.

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

2534 posts

#34 h Apr 27, 2025, 5:13 PM

Y by

Let $p$ be a prime that does not divide any element of $S$ .

Claim: All elements in $S$ are the same residue modulo $p$ .

Proof: Let the residues of the elements in $S$ be $r_1, r_2, \dots, r_k$ . Consider an arbitrary set

$T_i = \{r_ir_j+1\}_{j=1}^k.$
Obviously, no two elements in $T_i$ can have the same residue modulo $p$ , so they must be a permutation of $\{r_1, r_2, \dots, r_k\}$ in some order. Thus, if we sum the elements of $T_i$ , we get

$r_i(r_1+r_2+\dots+r_k) +k \equiv (r_1+r_2+\dots+r_k) \pmod{p}.$
Letting $r_1+r_2+\dots+r_k =s$ , we obviously see that $p \nmid s$ , or else $p \mid k$ , which is clearly impossible. Hence,

$r_i \equiv 1-k \cdot s^{-1} \pmod{p}.$
The value $1-k\cdot s^{-1}$ is constant for all $i$ , so we have all the residues are equal. This necessarily implies that $k=1$ , as desired. $\square$

Let the sole residue modulo $p$ be $r$ , giving us

$r \equiv 1-r^{-1} \pmod{p} \implies p \mid r^2-r+1.$
However, only finitely many primes can divide $r^2-r+1$ , so we are done. $\blacksquare$

Z K Y

N Quick Reply

G

H

=

© 2025 AoPS Incorporated

a