Given a positive integer $k$ show that there exists a prime $p$ such that one can choose distinct integers $a_1,a_2\cdots, a_{k+3} \in \{1, 2, \cdots ,p-1\}$ such that p divides $a_ia_{i+1}a_{i+2}a_{i+3}-i$ for all $i= 1, 2, \cdots, k$. South Africa
Problem
Source: IMO SL 2020 N1
Tags: number theory, Sequence, Divisibility, IMO Shortlist, IMO Shortlist 2020
Aryan-23
21.07.2021 00:04
First we pick $k+3$ rationals $r_i=\frac {p_i}{q_i}$ such that $r_ir_{i+1}r_{i+2}r_{i+3}=i$ for all $1\le i\le k$. Further we can pick $r_1,r_2,r_3$ in such a way such that all the terms are distinct.
Choose a large prime $p$ such that :
$p \not \vert \quad q_i$
$ p\not \vert \quad p_iq_j-q_ip_j$
Finally, pick $a_i=p_i\cdot q_i^{-1}\pmod p$. The first condition ensures that $q_i$ has a inverse mod $p$. The second condition ensures that the $a_i$ are injective $\pmod p$. $\square$
cadaeibf
21.07.2021 00:05
Lemma: given a sequence of distinct rational numbers $q_1=\frac{m_1}{n_1},...,q_N=\frac{m_n}{n_N}$ there exists a prime $p$ and a sequence $a_1,...,a_N$ of distinct integers satisfying $a_i\equiv m_in_i^{-1}\pmod{p}$
Proof: it suffices to take $p$ big enough so that it doesn't divide any of the $m_i, n_i, m_in_j-m_jn_i$($1\leq i\neq j\leq N$), (note that $m_in_j-m_jn_i\neq 0$ since $q_i\neq q_j$ and so there is a finite number of primes dividing it) so that the inverses exist, and the fractions are different, and then just take $a_i=m_in_i^{-1}\pmod{p}$ where $n_i^{-1}$ is the multiplicative inverse modulo $p$.
So we now reduce our problem to finding a sequence of distinct rationals which satisfies the same condition ($p|$ is replaced with $0=$).
This can be easily done by the recurrence
$$a_4=\frac{1}{a_1a_2a_3}, a_{i+4}=\frac{1+i}{i}a_i\forall i=1,...,n-1$$for some fixed rationals $a_1,a_2,a_3$. Now we just have to make sure that the elements of the sequence are actually distinct, and so pick $a_1=1, a_2=M, a_3=M^2$ and so $a_4=\frac{1}{M^3}$, for some big rational $M$.
It is obvious that $a_1<a_5<a_9<a_13<...$ since $1+\frac 1i>1\forall i>0$, and similarly the sequence is strictly increasing if we restrict ourselves to the indices of a certain residue $\pmod{4}$. Now, to prove that these residue classes are also distinct from each other, just take M big enough so that $M>\left(1+\frac 11\right)\left(1+\frac 15\right)\left(1+\frac 19\right)\cdots \left(1+\frac{1}{4\lfloor\frac{n-5}{4}\rfloor}\right)$; by a similar logic we can also ensure that the elements withe the other pairs of residue classes of the indices, by taking $M$ big enough so that the "orders of magnitude" are too much different from each other.
Finally, it suffices to apply our lemma and we can find a sequence of distinct integers $a_1,...,a_n$ which satisfies the condition.
pad
21.07.2021 02:28
Pretty hard for N1. Solved with dantaxyz. Reduction: We claim the problem is equivalent to finding a prime $p$ for which there exist $a_1,a_2,a_3,a_4 \in \{1,\ldots,p-1\}$ for which $a_1a_2a_3a_4\equiv 1 \pmod{p}$, and for each $i\in \{1,\ldots,k-1\}$, we have $\frac{a_{i+4}}{a_i} \equiv \frac{i+1}{i} \pmod{p}$. First, we show why a sequence satisfying the above conditions satisfies the problem statement. Induct on $i$, base case $i=1$ covered by (i) above. Now, if the problem statement condition holds till $i$, then, \[a_{i+1}a_{i+2}a_{i+3}a_{i+4} \equiv (a_ia_{i+1}a_{i+2}a_{i+3})\cdot \frac{a_{i+4}}{a_i} \equiv i\cdot \frac{i+1}{i} \equiv i+1 \pmod{p},\]finishing the induction and showing the equivalency. Construction: WLOG $k\equiv 2 \pmod4$; if not, simply truncate the last few $a_i$'s. For some constants $C_1,C_2,C_3,C_4$, set \begin{align*} a_1 = C_1 \cdot (k-1)(k-5)\cdots 5\cdot 1 \\ a_2 = C_2 \cdot (k-2)(k-6)\cdots 6\cdot 2 \\ a_3 = C_3 \cdot (k-3)(k-7)\cdots 7\cdot 3 \\ a_4 = C_4 \cdot (k-4)(k-8)\cdots 8\cdot 4. \end{align*}Use (ii) -- in particular, $a_{i+4}=\tfrac{i+1}{i}a_i$ -- to extend and compute the rest of $\{a_5,a_6,\ldots,a_{k+3}\}$. Due to our construction, the RHS's will all be integers. The above construction satisfies (ii) for any choice of $C_i$'s. We need to make sure there exist some $C_i$'s so that (i) holds, i.e. \[ a_1a_2a_3a_4 = C_1C_2C_3C_4(k-1)! \equiv 1 \pmod{p}. \]Also, we need to make sure that each of the $a_i$'s are less than $p$. Set $C_1=1$, $C_2=10k$, and $C_3=1000k$. Then we want $p\mid 10^3(k-1)! C_4-1$. In fact, we will make them equal. By Dirichlet, there exists infinitely many primes $p \equiv -1 \pmod{10^3k^2(k-1)!}$. Then set $C_4 = \frac{p+1}{10^3k^2(k-1)!}$ for one of the really large $p$'s. Proof of construction:To show this choice works, first we show $a_n<p$ for all $n$. Notice \[ \frac{a_n}{a_{n\mod 4}} < \frac{n-3}{n-4} \cdot \frac{n-4}{n-5}\cdots \frac{2}{1} = n-3, \]so for $n\equiv 1,2,3\pmod{4}$, the number $a_n$ is a fixed function of $k$, which means we can take $p$ to be arbitrarily large along the infinitely many primes generated by Dirichlet, to assure $a_n < p$. Finally, for $n\equiv 0 \pmod4$, \[ a_4 = \frac{p+1}{10^3k^2(k-1)!} \cdot (k-4)(k-8)\cdots 8\cdot 4 < \frac{p+1}{10^3k^2}, \]so $a_n < (n-3)a_4 < ka_4 < \tfrac{p+1}{10^3k} \ll p$. Secondly, we need to show $a_i \not = a_j$ for any $i$ and $j$. Given the massive multipliers $C_1,C_2,C_3,C_4$ (note that $C_4$ is the most massive since we made $p$ extremely large, and $k$ is fixed), this is clear by size.
Pretty tricky NT-construct kind of problem. The reduction to the (i) and (ii) is clear; the idea being that $a_{i+4}$ can be expressed as a fraction times $a_i$ by comparing adjacent equations from the original problem statement. The first main idea is to simply write down $a_1,a_2,a_3,a_4$ in the given form so that upon extending using (ii), the terms are all integers. However, we need to also ensure that $p\mid a_1a_2a_3a_4-1$.
The hardest part of the problem is choosing the correct multipliers so this works out. We need to find $C_1,C_2,C_3,C_4$ so that $C_1C_2C_3C_4\equiv \tfrac{1}{(k-1)!} \pmod{p}$. The issue is that if any of the $C_i$'s grows linearly in $p$, aka is too large, then some $a_i$ may be too large and spill over larger than $p$. So we need to force (some multiple of $p$) + ($(1/(k-1)!) \mod p$) to have a lot of factors, but also not be too big. This is really hard to do. The main idea is to switch perspectives, and instead of fixing $p$ and trying to find some $C_i$'s that work, instead we fix $C_1,C_2,C_3$, and find a $p$ that works. This is the main idea, and then some Dirichlet construction works, and we can prove it with size.
SnowPanda
21.07.2021 05:46
Let $c = (k + 3)!$ and $a_1 = q_1c$, $a_2 = q_2c$, $a_3 = q_3c$, and $a_4 = q_4cd$ for distinct primes $q_i > k + 3$ and a positive integer $d$, such that $a_1a_2a_3a_4 - 1$ is a prime $p$; this is possible by Dirichlet's Theorem.
Then for each $i \geq 1$, let $\tfrac{a_{i + 4}}{a_i} = \tfrac{i + 1}{i}$. These are all integers because $c$ is divisible by the product of all the $i$. Since the first modular condition is satisfied, by induction this means all the others will be as well.
To show all the $a_i$ are distinct, note that within each residue class mod $4$ the $a_i$ are strictly increasing. Meanwhile we can't have $a_i = a_j$ for $i$ and $j$ different mod $4$ -- if one of them is $0$ mod $4$ then it's divisible by $q_4$ and the other isn't, while otherwise both have a $q_i$ that the other residue class doesn't.
Finally, each $a_i$ satisfies $a_i \leq ca_k$ for some $1 \leq k \leq 4$, so then $a_i < ca_k < a_1a_2a_3a_4$, and the less than $p$ condition is satisfied.
jackson46
22.07.2021 10:28
........
jackson46
22.07.2021 10:30
/........
FAA2533
23.07.2021 08:05
For $k>1$, pick sufficiently large positive integers $a_1, a_2, a_3$ such that $a_1 << a_2 << a_3$ and $k!$ divides each of $a_1, a_2, a_3$.
By Dirichlet's Theorem, there exists a prime $P$ such that $$P = T(k! \cdot a_1a_2a_3) + (k! \cdot a_1a_2a_3 - 1) = (T+1) k! \cdot a_1a_2a_3 - 1$$where $T >> a_3.$
Pick $a_4 = (T+1) \cdot k!$. We claim that $P$ satisfies the desired condition.
Pick $a_{i+4} = (i+1)i^{-1}a_i$ for $1 \leq i \leq k-1$. We claim that this set of ${a_i}$ satisfies the desired condition for $P$.
$k! \mid a_i$ for $i=1,2,3,4$ implies all $a_i$'s are integer for $1 \leq i \leq k+3$.
The condition $a_1 << a_2 << a_3 << a_4$ implies $a_i << a_j << a_k << a_l$ where $$i \equiv 1 \pmod 4$$$$j \equiv 2 \pmod 4$$$$k \equiv 3 \pmod 4$$$$l \equiv 0 \pmod 4$$It is also easy to check that $a_i > a_j$ for $i > j$ and $i \equiv j \pmod 4$ which implies that all $a_i$'s are distinct positive integers. Obviously, $a_i < P$ for all $1 \leq i \leq k+3$ for size reason.
We are going to prove the divisibility conditions by induction.
The base case for $i=1$ is $P \mid a_1a_2a_3a_4 - 1 = P$, which is obvious.
Suppose for some $1 < t < k$, we have $P \mid a_ta_{t+1}a_{t+2}a_{t+3} - t$.
For $i=t+1$, we have $a_{t+1}a_{t+2}a_{t+3}a_{t+4} - (t+1) = (t+1)t^{-1}a_ta_{t+1}a_{t+2}a_{t+3} - (t+1) = (t+1)t^{-1}(a_ta_{t+1}a_{t+2}a_{t+3} - t)$
Here $(P,t) = 1$ as $P >> t$ and $a_ta_{t+1}a_{t+2}a_{t+3} - t$ is divisible by $P$ from the inductive hypothesis.
Thus, $P \mid a_{t+1}a_{t+2}a_{t+3}a_{t+4} - (t+1)$ and we are done.
For $k=1$, just pick $(a_1, a_2, a_3, a_4) = (2,3,4,5)$ and $p = 7$.
RemarkThe size condition forces distinctness and divisibility by $k!$ forces all $a_i$ to be integer in our construction. We could have replaced '$k!$' with smaller values for each $a_i (1 \leq i \leq 4)$, but we used $k!$ instead for simplicity.
guptaamitu1
23.07.2021 18:55
Below is a solution by transformation: Fix $k$ and choose $p$ to be sufficiently large (how much large and why such a $p$ should exist should be clear from what follows). Also, just for convenience, we will assume that $k+3 = 4l$ for some integer $l$ (we can do this since it is clear that if the assertion is true for $k=k_0$, then it is evident that the assertion is true for all value of $k$ less than $k_0$). First we define some conventions we will be using: We will working modulo $p$ throughout this solution. That is, if we write/say two numbers are equal then we mean they are equal modulo $p$ and when we write/say two numbers are not equal, we mean they we mean they are not equal modulo $p$. For any two sets of rational numbers $P_1,P_2$, we will write $P_1 \sim P_2$ if $ r \ne s~ \forall ~ r \in P_1,s \in P_2$. Lastly, note that is fine to work with rational numbers (with denominator not divisible by $p$, and as we will see, denominator would never be divisible by $p$ as $p$ would be sufficiently large) and not only integers since this is allowed in modular arithmetic. We will call a set $S = \{b_1,b_2,\dots,b_{k+3}\}$ of rational numbers good if $p$ divides $a_ia_{i+1}a_{i+2}a_{i+3} - i$ for all $i = 1,2,\dots,k$ and pick any such good set $S$. Define sets $S_i = \{b_i,b_{i+4},\dots,b_{4l-4+i}\} ~ \forall ~ i = 1,2,3,4$. Our idea to solve the problem is the following: First we show if two numbers lie in the same set $S_i$ (for any $i = 1,2,3,4$), then they are not equal. So now we just want to make sure that $S_i \sim S_j ~ \forall ~ i \ne j \in \{1,2,3,4\}$. Then we do a particular type of transformation which will preserve that $S$ is good and will make $S_i \sim S_j ~ \forall i \ne j \in \{1,2,3,4\}$ (and from the definition of the transformation it would be clear that first property is also preserved). Finally, this transformed set $S$ would be the set we are looking for. So lets proceed with our ideas! First of all, note that all elements of set $S$ must be non-zero. Claim 1 : If two numbers lie in the same set $S_i$ (for any $i = 1,2,3,4$), then they are not equal. proof: We will consider the case $i=1$ (as the other cases are analogous). It is easy to prove that $a_{i+4} = a_i \cdot \frac{i+1}{i}$. In particular, we could write set $S_i = \{a_1,r_1 \cdot a_1, r_2 \cdot a_1, \dots, r_n \cdot a_i\}$ where $r_1,r_2,\dots,r_n$ are distinct and fixed rational numbers. So basically, our claim would get reduced to showing that $p$ does not divide some fixed integers. Now since $p$ is sufficiently large, it is clear that our claim holds true. $\square$ Claim 2: Given any $4$ sets $A=\{x_1,x_2,\dots,x_l\},B=\{y_1,y_2,\dots,y_l\},C=\{z_1,z_2,\dots,z_l\},D=\{t_1,t_2,\dots,t_l\}$ of rational numbers such that no two numbers in the same set are equal, then there exists a integer $c \ne 0$ such that among the sets, $A'= \left\{\frac{x_1}{c},\frac{x_2}{c},\dots,\frac{x_l}{c}\right\},B'=\{y_1,y_2,\dots,y_l\},C'=\{z_1,z_2,\dots,z_l\},D'=\{c \cdot t_1, c \cdot t_2, \dots,c \cdot t_2\}$, we have $A' \sim B'~,~ A' \sim C' ~,~ D' \sim B' ~,~ D' \sim C' ~,~ A' \sim D'$. proof: Note that in order to guarantee any one of $A' \sim B' ~ ,~ A' \sim C' ~,~ D' \sim B' ~,~ D' \sim C' $, we just need to make sure that $c$ doesn't take some particular $l^2$ (or less) values ; and in order to guarantee $A' \sim D'$, we just need to make sure $c$ does not take some particular $2l^2$ (or less) values. Hence in order to guarantee all the five conditions, we just need to make sure $c$ does not take some particular $6l^2$ (or less) values. But as $p$ is sufficiently large, so it is clear that such a $c$ exists. $\square$ Now following is the key observation: For any $i \ne j \in \{1,2,3,4\}$, if we multiply all the elements of set $S_i$ by some constant integer, and divide all elements of set $S_j$ by the same integer, then set $S$ still remains good. So we are now ready to solve the problem. By a weaker version of Claim 2 , we can do a transformation of the mentioned form (on sets $S_1,S_4$) to obtain $S_1 \sim S_4$. Again, by Claim 2 we can then do a transformation of the mentioned form (on sets $S_2,S_3$) to also have $S_2 \sim S_1~,~ S_2 \sim S_4 ~,~ S_3 \sim S_1 ~,~ S_3 \sim S_4 ~,~ S_2 \sim S_3$. Finally, as this transformation didn't effect sets $S_1,S_4$, so we must also have $S_1 \sim S_4$. So finally, we have that $$ S_i \sim S_j ~ \forall ~ i \ne j \in \{1,2,3,4\} ~~~ (\text{here we are also using that } S_i \sim S_j ~ \iff ~ S_j \sim S_i) $$This completes the proof of the problem. $\blacksquare$
CT17
27.07.2021 15:46
Does this work? Let $p_1$, $p_2$, $p_3$, and $p_4$ be distinct primes greater than $k$. By Dirichlet's there exists a positive integer $m$ such that $mp_1p_2p_3p_4k!^4 - 1$ is a prime $p$. We define the $a_i$ recursively as follows: $a_1 = p_1k!$ $a_2 = p_2k!$ $a_3 = p_3k!$ $a_4 = mp_4k!$ $a_i = \frac{i-3}{i-4}a_{i-4}$ for all $i\ge 5$. This clearly satisfies the divisibility condition in the problem. Moreover, $a_i < k!\text{max}(a_1,a_2,a_3,a_4 ) < p$ for all $i$. Finally, $a_i\neq a_j$ whenever $i\neq j\pmod{4}$ since they would have different large prime factors, and since $a_i$, $a_{i+4}$, ... is an increasing sequence for each $i\in \{1,2,3,4\}$, the $a_i$ are distinct, as desired.
green_leaf
03.08.2021 13:21
Let $m$ be a sufficiently large positive integer and let $a_1 = r \cdot m!$, $a_2 = r \cdot (m+1)!, a_3 = r \cdot (m+2)!, a_4 = r \cdot (m+3)!$. There exists $r$ such that $a_1a_2a_3a_4 - 1$. Let $a_5 = 2a_1, 2a_6 = 3a_2, 3a_7 = 4a_3, 4a_8 = 5a_4$, and for all $4<t \leq k+3, a_t = \frac{(t+1)(t-3)a_j}{t}$ where $1 \leq j \leq 4$ and $t \equiv j \pmod{4}$. It is easy to see that this construction satisfies $p | a_ia_{i+1}a_{i+2}a_{i+3} - 1$. It remains to be proven that $a_{t_1} \neq a_{t_2}$ for any choice of $t_1, t_2$. This is equivalent to $\frac{(t_1+1)(t_1-3)a_{j_1}}{t_1} \neq \frac{(t_2+1)(t_2-3)a_{j_2}}{t_2}$ where $j_1, j_2 \in \{1, 2, 3, 4 \}$. If $j_1 = j_2$, we need $t_1(t_2+1)(t_2-3) \neq t_2(t_1 + 1)(t_1 - 3) \implies t_1|t_2, t_2|t_1 \implies t_1 = t_2$.Continue casework on $j_1 = j_2+1$, etc.
Spacesam
08.08.2021 04:45
We can rephrase the problem as follows: we choose integers $a_1, a_2, a_3, a_4$ such that $a_1a_2a_3a_4 \equiv 1\pmod p$, and then we require $2a_1 \equiv a_5, 3a_2 \equiv 2a_6$, etc. Observe that $2a_1 \equiv a_5, 6a_5 \equiv 5a_9$, etc forms a bunch of disjoint chains $\pmod 4$. At this point, set $M = 69420^{k^k} \cdot ((k + 3)!)^{69}$. We take a prime $p \equiv 1\pmod{M^5 \cdot k^k}$ by Dirichlet, and we write $p = 1 + a \cdot M^5 k^k$. From here, we choose $a_1 = M \cdot k$, $a_2 = M^2 \cdot k$, $a_3 = a \cdot M^3 k^{k - 1}$, $a_4 = a \cdot M^4 \cdot k^{k - 1}$. Since $a_1a_4 = p - 1$ and $a_2a_3 = p - 1$, the first equivalence is satisfied. The presence of the $(k + 3)!$ means $2a_1 \equiv a_5$, $6a_5 \equiv 5a_9$, etc all become equalities and not just congruences because we have sufficiently many factors. Additionally, by size reasons none of the chains intersect due to how big $M$ is and the fact that the increase from $a_1$ to $a_{4k' + 1}$ for some $k'$ is at most $k'! < (k + 3)!$. This works.
Illuzion
21.08.2021 02:24
Assume that for some $k$ there isn$'$t such a $p.$ Note that the sequence is completely determined by $a_1, a_2, a_3$ when we are using a fixed prime $p.$ We will consider a large prime $p$ and random $a_1, a_2, a_3$ and construct the sequence from there and see if its injectivity can really break$.$ Observe that for the sequence $\{a_i\}_{i=1}^{i=k},$ where $a_{i+3}=\frac{i}{a_ia_{i+1}a_{i+2}}\pmod p,$ we have $$\frac{a_{i+4}}{a_i}\equiv \frac{i+1}{i}\pmod p.$$Iterating for a bit$,$ we obtain $$a_{i+4t}\equiv a_i\cdot\frac{i+1}{i}\frac{i+5}{i+4}\cdots\frac{i+4(t-1)+1}{i+4(t-1)}\pmod p$$for any $i\in \{1, 2, 3\}$ and $1\leq i+4t\leq k+3.$ If we have $a_{i+4t_1}\equiv a_{j+4t_2}\pmod p,$ then $$\frac{a_i}{a_j}\equiv \frac{j+1}{j}\cdots\frac{j+4(t_2-1)+1}{j+4(t_2-1)}\cdot\frac{i}{i+1}\cdots\frac{i+4(t_1-1)}{i+4(t_1-1)+1}\pmod p.$$ Observe that the right-hand side is only dependent on $i, j, t_1, t_2,$ so it can take on at most $3\cdot 3\cdot (\lfloor\frac{k+3}{4}\rfloor+1)^2=C=const$ values modulo $p.$ Call these values bad. If we chose $a_1, a_2, a_3$ more carefully at the beginning$,$ we could make sure that the value of $\frac{a_i}{a_j}\pmod p$ is not bad for any $i, j\in \{1, 2, 3\},$ thus reaching a contradiction$.$ The case $i=j$ is a little awkward and so we deal with it first$.$ Assuming that $t_2>t_1,$ we have $$1\equiv \frac{j+4(t_2-1)+1}{j+4(t_2-1)}\cdots\frac{j+4t_1+1}{j+4t_1}\pmod p.$$For clarity denote $b_1=j+4t_1, b_2=j+4t_1+4, \dots, b_{t_2-t_1}=j+4t_2-4.$ The congruence then becomes $$(b_1+1)\cdot (b_2+1)\cdots (b_{t_2-t_1}+1)\equiv b_1\cdot b_2\cdots b_{t_2-t_1}\pmod p.$$But notice that $b_\ell <k$ for all $\ell$ and that $t_2-t_1 \leq t_2 \leq \frac{k+3} {4}\leq k$ as well$.$ This means that the difference between the $\text{LHS}$ and the $\text{RHS}$ in the last congruence is a non-zero number$,$ which is bounded by some function of $k$ (not depending on $p$) and this is the desired contradiction$.$ Now we are left with the case where $a_{i+4t_1}\equiv a_{j+4t_2}\pmod p$ and $i\neq j.$ Denote $$x=\frac{a_1}{a_2}\pmod p, y=\frac{a_2}{a_3}\pmod p.$$We need to show that none of the values $$x, y, xy\pmod p, \frac{1}{x}\pmod p, \frac{1}{y}\pmod p, \frac{1}{xy}\pmod p$$is bad$.$ Let$'$s look at unordered pairs of the type $$(u, \frac{1}{u}\pmod p) \hspace{0.3cm}\text{for}\hspace{0.3cm} u\in \{2, 3\cdots, p-2\}.$$We have $\frac{p-3}{2}$ such pairs$.$ Call such a pair good$,$ if neither $u,$ nor $\frac{1}{u}\pmod p$ is bad$.$ We need to choose $x, y$ in good pairs so that $xy$ is also in a good pair$.$ But as we have only at most $C$ bad residues$,$ the number of not good pairs is at most $C,$ so the number of good pairs is at least $\frac{p-3}{2}-C.$ Order the good pairs as $(u_0, v_0), \dots, (u_n, v_n)$ with $u_i>v_i$ for all $i$ and $u_0<u_1<\cdots<u_n.$ Now look at the (unordered) pairs $$(u_0u_1, v_0v_1), \dots, (u_0u_n, v_0v_n)\hspace{0.3cm}(*).$$We would like to know how many distinct such pairs there are$.$ Assume that $(u_0u_i, v_0v_i)\equiv (u_0u_j, v_0v_j).$ If $u_0u_i\equiv u_0u_j\pmod p,$ then $u_i\equiv u_j\pmod p,$ contradiction$.$ Therefore $$u_0u_i\equiv v_0v_j\pmod p\iff v_j\equiv u_0^2u_i\pmod p.$$But this means that only the pairs $(u_0u_i, v_0v_i)$ and $(u_0u_j, v_0v_j)$ can coincide to one another$,$ i$.$e$.$ there isn$'$t a third pair $(u_0u_\ell, v_0v_\ell)$ which coincides with them$,$ since otherwise we would obtain $v_\ell\equiv u_0^2u_i\pmod p$ as well$,$ which is not possible$.$ Therefore among all $n=\frac{p-3}{2}-C-1$ pairs of type $(*),$ there are at least $\frac{n}{2}$ unique$.$ But as that number is large for large $p$ and the number of not good pairs is the constant $C,$ we see that there must be a good pair $(u_0u_i, v_0v_i).$ But now we can just set $$x=u_0, y=u_i$$and we would be done$.$
Remarks: I believe that I also prove that for each sufficiently large prime $p,$ there is such a sequence $\{a_i\}$ of length $k+3$ $-$ a fixed positive integer$.$ I also think that my proof can be generalized to problems with more than $4$ variables (i$.$e$.$ with the condition $p\mid a_ia_{i+1}a_{i+2}a_{i+3}a_{i+4}a_{i+5}-i,$ etc$.$)$,$ but I$'$m too tired to do it and so I leave it as an exercise for the reader$.$
lazizbek42
30.01.2022 14:56
I think for N1 very hard problem
TFIRSTMGMEDALIST
31.01.2022 20:09
No beautiful solution again
Tung-CHL
09.05.2022 11:42
We only need to choose $a_1,a_2,a_3,a_4$ since $$a_i\equiv\frac{i}{i+1}a_{i+4} \pmod{p}\; \forall i \in \{1,2,\dots,k-1\}$$My idea is if we choose $a_1 \ll a_2 \ll a_3 \ll a_4\ll p$, we don't need to worry about $a_i=a_j$ for some $i\ne j$. Hence let $$a_1=k!, a_2=(k!)^2, a_3=(k!)^3, a_4=m(k!)^4$$for some $m$ such that $m(k!)^{10}-1$ is a prime number (there are infinitely many of them due to Dirichlet Theorem). P.S. This proof doesn't work for $k=1$, but I would skip it since it is a trivial case
awesomeming327.
17.02.2023 21:06
Note that the condition is equivalent to \begin{align*} a_1a_2a_3a_4 &\equiv 1\pmod p \\ a_5/a_1 &\equiv 2\pmod p \\ a_6/a_2 &\equiv 3/2 \pmod p \\ &~~~~\vdots \\ a_{k+3}/a_{k-1} &\equiv k/(k-1) \pmod p \end{align*}Let $M=(k+3)!(k+4)!(k+5)!(k+6)!$ and $p$ be a prime such that $M$ is a fourth power $\pmod p$. Let $m=M^{-1/4}$ and \[a=m(k+3)!,a_2=m(k+4)!,a_3=m(k+5)!,a_4=m(k+6)!\]which satisfies the first condition. The other values of $a$ can also be iteratively constructed.
cj13609517288
06.06.2023 17:16
Construct positive integer sequences $w_m$, $x_m$, $y_m$, $z_m$ such that \[\frac{w_{m+1}}{w_m}=\frac{4m-2}{4m-3},\]\[\frac{x_{m+1}}{x_m}=\frac{4m-1}{4m-2},\]\[\frac{y_{m+1}}{y_m}=\frac{4m}{4m-1},\]\[\frac{z_{m+1}}{z_m}=\frac{4m+1}{4m},\]and the number of terms is the number of times the letter appears in the string $wxyzwxyz\dots$(which has length $k$). Now multiply $x_m$ by a large enough positive integer so that it is always greater than any term in any previous sequence(in this case only $w_m$), and do the same to $y_m$ and $z_m$ in that order. Now choose a prime $p$ that is $-1$ mod $w_1x_1y_1z_1$, possible by Dirichlet's, then scale $z_m$ again so that $w_1x_1y_1z_1=p+1$. Now simply interlace the sequences in the $wxyzwxyz\dots$ pattern to finish. $\blacksquare$
TheHazard
20.11.2023 09:58
COMBO NULL Fix $a_{k+3} = 0$, and vary $a_1, a_2, a_3$, defining the rest of $a_4$ through $a_{k+2}$ through the relations. Then, define the polynomial in ${\mathbb F}_p$ of \[ P(a_1, a_2, a_3) = \prod_{i < j} (a_i - a_j) \]which allows us to get a polynomial with degree at most $d = \binom{k}{2} \cdot 3^{k+3}$ in each dimension. Then, taking $p - 1 > d$ gives the result by Alon's combinatorial nullstellenstatz.
Acclab
28.02.2024 21:15
This is the same as saying with $p$ big enough, there exists $a, b, c, d, \in \mathbb{F}_p$ so that $$a, 2a, \frac{2 \times 6}{1 \times 5}a, \frac{2 \times 6 \times 10}{1 \times 5 \times 9}a, ...; b, \frac{3}{2}b, \frac{3 \times 7}{2 \times 6}b, \frac{3 \times 7 \times 11}{2 \times 6 \times 10}b, ...; c, \frac{4}{3}c, \frac{4 \times 8}{3 \times 7}c, \frac{4 \times 8 \times 12}{3 \times 7 \times 11}c, ...; d, \frac{5}{4}d, \frac{5 \times 9}{4 \times 8}d, \frac{5 \times 9 \times 13}{4 \times 8 \times 12}d, ...$$are all well-defined and distinct (in $\mathbb{F}_p$). Indeed, choosing $a > b > c > d$ to be distinct prime $>k$, and $p$ bigger than the greatest numerator product term squared times $a$, then if two of the terms listed above $x, y$ coincides, write $x = \frac{m}{n}x_0$ and $y = \frac{m'}{n'}y_0$ with $x_0, y_0 \in \{a, b, c, d\}$, then $$ x = y \text{ ( in $\mathbb{F}_p$ ) } \iff \frac{m}{n}x_0 = \frac{m'}{n'}y_0 \text{ ( in $\mathbb{F}_p$ ) } \iff mn'x_0 = m'ny_0 \text{ ( in $\mathbb{F}_p$ ) } \iff mn'x_0 = m'ny_0 \text{ ( in $\mathbb{N}$ ) }$$implying $x_0 = y_0$(i.e., the two terms must be of the same "family"), but then it's easy to see $\frac{m}{n} \neq \frac{m'}{n'}$ if the terms are different.
HamstPan38825
16.06.2024 03:51
I guess this is ``hard" for N1, although the solution is completely mechanical and doesn't really require insight. It's a bit long though. Fix some large prime $p \equiv 3 \pmod 8$, and notice that $\left(\frac{p-1}2\right)! \equiv 1 \pmod p$ by Wilson's theorem. Observe that $\frac{p-1}2 \equiv 1 \pmod 4$, so write it as $4r+1$, and let \begin{align*} a_1 &= 1 \cdot 5 \cdots (4r-3)(4r+1) \\ a_2 &= 2 \cdot 6 \cdots (4r-2) \\ a_3 &= 3 \cdot 7 \cdots (4r-1) \\ a_4 &= 4 \cdot 8 \cdots (4r). \end{align*}Furthermore, for each $i$ such that $4i+1 \leq k$, write \[a_{4i+1} = 2 \cdot 6 \cdots (4i-2)(4i+1) (4i+5) \cdots (4r+1).\]Similarly, define \[a_{4i+2} =3 \cdot 7 \cdots (4i-1)(4i+2) \cdots (4r-2)\]and similar for $a_{4i+3}$ and $a_{4i+4}$. Observe that these choices satisfy $\frac{a_{i+4}}{a_i} = \frac{i+1}i \pmod p$, so we can verify inductively that we have $a_ia_{i+1}a_{i+2}a_{i+3} \equiv i \pmod p$, with the base case $i=1$ guaranteed by the choice of $p$. It remains to show that all the $a_i$ for $i \leq k$ are indeed distinct. Notice that by choosing $r$ sufficiently large, we guarantee that $a_{4i+j} < a_{j+1}$ for all $j \in \{2, 3\}$, as both terms are the product of $r$ numbers. Furthermore, let $a_\ell$ be the maximal term with $\ell$ a multiple of $4$ (i.e. $\ell$ the largest multiple of $4$ less than $k$), such that \begin{align*} \frac{a_\ell}{a_1} &= \frac{5 \cdot 9 \cdots (\ell - 3) (\ell) \cdots (4r)}{5 \cdot 9 \cdots (4r-3)(4r+1)} \\ &= \frac{\ell}{\ell + 1} \cdot \frac{\ell + 4}{\ell + 5} \cdots \frac{4r}{4r+1} < 1. \end{align*}It follows that $a_{4i+1} > a_1 > a_\ell > a_4$ for all $i$, meaning we have strictly ordered all the $a_i$ in the sequence, so they must all be distinct. This yields a valid example for the problem.
ezpotd
26.09.2024 02:04
????????? this is almost certainly wrong but i can't find the error The sequence can be written as $a_1, a_2, a_3, a_4, 2a_1, \frac 32 a_2, \frac 43 a_3 \cdots (\prod_{k > k - 1 - 4i > 0} \frac{k - 4i}{k - 1 - 4i} )a_{(k + 3 \mod 4)}$. This is a working sequence if the (way too strong) condition $\frac{a_i}{a_j} \neq \frac{x}{y} \mod p$ holds for all $i \neq j \le 4$ and $xy \le k!$ AND $a_1a_2a_3a_4 = 1 \mod p$. We find such a prime $p$ and a sequence. Let $a_3a_1 = a_4a_2 = 1\mod p$, then realize the other condition is a weaker form of "no product or quotient of $a_1, a_2$ except $1$ is the ratio of two numbers at most $k!$ mod $p$." Thus for a sufficiently large prime $p$, we can just take $a_1 \neq 1,-1 \mod p$ (avoid $a_3 = a_1$) and $a_1$ squared not being congruent to something less than $k!$ and we will have bounded amount (polynomial in $k!$) of $a_2$ that don't work, so we can find some value of $a_2$ such that the condition is true and that $a_2 \neq 1,-1 \mod p$ and we are done.
onyqz
19.10.2024 13:55
storage
Our given condition translates to $a_i\equiv \frac{a_{i-4}}{i-4}\cdot(i-3) \mod p \, , \forall i\in\{5,6,\dots,k+3\}$.
Now we also want choose $a_1 \ll a_2 \ll a_3 \ll a_4 \ll p$, s.t. there exist multiplicative inverses and we have no two $a_i\equiv a_j$ for $i\neq j$.
So we take $a_1 = 2^{2^k}, a_2=2^{2^{k+1}}, a_3=2^{2^{k+2}}, a_4=2^{2^{k+3}}$ and $p=n\cdot2^{2^{k+3}+2^{k+2}+2^{k+1}+2^k}-1$ a prime , which exists by Dirichlet. $\square$