Let $n$ be a positive integer. Let $s: \mathbb N \to \{1, \ldots, n\}$ be a function such that $n$ divides $m-s(m)$ for all positive integers $m$. Let $a_0, a_1, a_2, \ldots$ be a sequence such that $a_0=0$ and \[a_{k}=a_{k-1}+s(k) \text{ for all }k\ge 1.\]Find all $n$ for which this sequence contains all the residues modulo $(n+1)^2$. Proposed by N.V. Tejaswi
Problem
Source: India IMOTC 2024 Day 2 Problem 1
Tags: abstract algebra, number theory
AshAuktober
31.05.2024 07:43
Will post solulu later ( in an hour) ; this was the only problem I completely solved.
Rijul saini
31.05.2024 08:09
Answer: $n=2^k-1$ for any $k\in \mathbb{N}$.
We begin by noting that the sequence is given by the formula $$a_{rn+s} = r \cdot \binom{n+1}{2}+\binom{s+1}{2}$$for all $ \ge 0$ and $s=1, 2, \dots, n$. This is easy to confirm by mathematical induction: $a_0=0$ is true, and for fixed $r$, inducting on $s$ gives $$a_{rn+s} = a_{rn+s-1}+s = r\cdot \binom{n+1}{2}+\binom{(s-1)+1}{2}+s = r \cdot \binom{n+1}{2}+\binom{s+1}{2},$$proving this induction step. Finally, $a_{(r+1)n} = (r+1)\binom{n+1}{2} = r \cdot \binom{n+1}{2}+\binom{n+1}{2} = a_{rn+n}$, confirming the induction argument on $r$ as well, proving the claim.
Claim 1: $n+1$ has no odd prime factor.
Proof: Suppose $n+1$ has an odd prime factor $p$. Then $p \mid \binom{n+1}{2}$, so a if all residues mod $(n+1)^2$ are present, then $\binom{s+1}{2}\equiv\frac{s^2+s}{2} \pmod{p}$ covers all possible residues mod $p$. However, the map $x \mapsto x^2+x \pmod{p}$ sends $x$ and $-(1+x)$ to the same element mod $p$ and the two are distinct unless $x \equiv \frac{-1}{2} \pmod{p}$, hence the set of residues represented by $s^2+s \pmod{p}$ has $\frac{p+1}{2}<p$ elements, a contradiction! So every $n$ that satisfies this condition must be one less than a power of $2$.
Claim 2: $n= 2^k-1$ work.
Proof: Let $n=2^k-1$. Then $\binom{n+1}{2} = 2^{k-1}(2^k-1) = 2^{2k-1}-2^{k-1} \pmod{2^{2k}}$. Then, if for $0 \le r$ and $1 \le s \le n$, and $r = 2j+e$, where $e \in \{0, 1\}$, then $$a_{rn+s} = -j \cdot (n+1) + e\cdot \binom{n+1}{2}+\binom{s+1}{2} \pmod{(n+1)^2}.$$Notice that for $s=1, 2, \dots, n$, the numbers $\binom{s+1}{2}$ are all distinct mod $n+1$. Indeed, if $1 \le s<t \le n$ and $\binom{s+1}{2} = \binom{t+1}{2} \pmod{n+1}$, then $(2n+2) \mid (s-t)(s+t+1)$, and since $s, t$ have opposite parities and $2n+2>2n+1 \ge s+t+1>|s-t|>0$, we arrive at a contradiction as $2n+2$ is a power of $2$, proving that the residues are distinct mod $n+1$. Also, note that none of these residues are $0 \pmod{n+1}$. Thus, $-j(n+1)+\binom{s+1}{2}$ (where $e=0$) covers all $n^2+n$ residues which are not of the form $l(n+1) \pmod{(n+1)^2}$.
Finally, for the remaining residues, take $s=n$ and $e=1$, we get $-j(n+1)+2\binom{n+1}{2} = -(j+1)(n+1) \pmod{(n+1)^2}$, so that which covers the remaining residues as $j$ varies.
D_S
02.06.2024 16:46
We claim that all $n$ of the form $2^k-1$, $k \in \Bbb N$ work.
Call a number that satisfies the condition in the problem 'good', otherwise 'bad'.
$s(m) \equiv m \pmod n$, $s(m) \in \{1,2,\ldots, n\}$.
Define a number of the form $\frac{k(k+1)}{2}, k\in \Bbb N \cup \{0\}$ as a triangle number.
It is easy to see that $a_{rn+s} = r \cdot \binom{n+1}{2}+\binom{s+1}{2}$.
Quote:
Claim 1: A number $n$ is good iff the first $n$ triangle numbers cover all the residues modulo $(n+1)/2$ (if $n$ is odd), or $n+1$ (if $n$ is even)
Proof: Suppose $n$ is good. Let $j$ be a residue modulo $(n+1)^2$. Then $\exists k,r$ s.t.
$a_{rn+k} \equiv j \pmod {(n+1)^2}$
Case 1: $n = 2m$.
$r \cdot m(2m+1) \equiv j - \binom{k+1}2 \pmod{(2m+1)^2}$
which is solvable for $r$ for a $k$ iff $n+1 | j - \binom{k+1}2$.
Case 2: $n = 2m-1$.
$r \cdot m(2m-1) \equiv j - \binom{k+1}2 \pmod {(2m)^2}$
which is solvable for $r$ for a $k$ iff $m | j - \binom{k+1}2$. $\blacksquare$
This immediately discards all even $n$ as bad, as $a_i$ is periodic modulo $n(n+1)/2$ (and also modulo $(n+1)$) with period $n$, so can't cover all the residues.
Quote:
Claim 2: Odd $n$ is good iff $\{1+8j| j \in \{1,2,\ldots, (n+1)/2\}\}$ contains only quadratic residues modulo $4(n+1)$.
Proof: $\frac{k(k+1)}2 \equiv j \pmod{(n+1)/2}$
$\iff (2k+1)^2 \equiv 1+8j \pmod{4(n+1)}$ $\blacksquare$
Quote:
Claim 3: Odd $n$ is bad if $(n+1)/2$ has an odd factor greater than 1.
Proof: Let $d$ be an odd divisor of $(n+1)/2$ greater than 1. $\{1+8j| j \in \{1,2,\ldots, (n+1)/2\}\}$ is the complete residue class modulo $d$, (as $\gcd(d,8) = 1$), but all residues modulo $d$ can't be quadratic residues, as $1$ is not congruent to $d-1$, but their squares are congruent. $\blacksquare$
Now the only candidates are numbers of the form $2^k-1$, $k$ is a positive integer. We show all of these work.
Quote:
Claim 4: All residues which are 1 mod 8 are quadratic residues modulo $2^k$, for $k \ge 3$ (the claim is true for $k=1,2$ also).
Proof: Note that exactly one-fourth residues odd residues are 1 mod 8. It is well-known that all odd QR must be 1 mod 8. Thus, if we show that there are exactly $2^{k-3}$ odd QR mod $2^k$ (one-fourth of odd residues), we will be done.
To this end, note that $x^2 \equiv (2^{k-1} - x)^2 \equiv (2^{k-1}+x)^2 \equiv (2^k - x)^2 \pmod {2^k}$. These are distinct odd residues modulo $2^k$ whose squares are congruent.
Now, suppose $x^2 \equiv y^2 \pmod{2^k}$ for $x,y$ odd. Then $2^{k-1}$ must divide exactly one of $(x-y)$ and $(x+y)$ ($2$ divides the other), which can only give the abovementioned solutions. $\blacksquare$
It is easy to see that claims 2 and 4 finish.
motannoir
02.06.2024 18:41
Nice one ! Then answer is $n+1$ is a power of two. Let's see that $a_k=s(0)+s(1)+\dots+s(k)$ so basically a term it is of the form $1+2+\dots+n+1+2+\dots+n+\dots+1+2+\dots+j$ where $0\le j\le n-1$ and the block $1,2,\dots n$ appears $k$ times So all of the terms are of the form $\frac{kn(n+1)}{2}+\frac{j(j+1)}{2}$ and the problem asks which $n$ have the property that all of the terms above span all residues classes mod $(n+1)^2$ We need the following claim: Claim: $n+1$ is even. Suppose by contradiction that it is odd.Then for each $r\in \{0,1,\dots n\}$ there exist $k$ and $j$ such that $(n+1)^2\mid \frac{kn(n+1)}{2}+\frac{j(j+1)}{2}$ so $(n+1)^2\mid kn(n+1)+j(j+1)-2r$ so $n+1\mid j(j+1)-2r$. But $j(j+1)$ spans at most $n$ residues,and $2r$ spans $n+1$ residues which is a contradiction $\blacksquare$ Let $n=2t-1$ and let's prove that $t$ is a power of two. We have that for each $r\in \{0,\dots 4t^2-1\}$ there exist $k\in \mathbb{N}$ and $0\le j\le n-1$ such that $4t^2\mid kt(2t-1)+\frac{j(j+1)}{2}-r$ But let's see that this is equivalent that for each $r$ there exist an $j$ such that $t\mid \frac{j(j+1)}{2}-r$. the first implication is easy because $t\mid kt(2t-1)$ and for the other implication use that $(2t-1,4t)=1$ so it has an inverse so you can find $k$ Define $f(j)=\frac{j(j+1)}{2}$ when $0\le j \le 2t-2$.observe that $f(j)\equiv f(2t-1-j) \pmod t$.so it suffices to consider $0\le j\le t-1$.so the problem becomes whcih $t$ have the property that $f$ is surjective mod $t$.But this is equivalent to $f$ being an injection. So $\frac{j(j+1)}{2} \equiv \frac{l(l+1)}{2} \pmod t \to j\equiv l \pmod t$. But this is equivalent with $2t\mid (j-l)(j+l+1) \to t\mid j-l$ If $t$ is a power of two then since exactly one of $j-l,j+l+1$ is even,$2t$ divides exactly one of them.But by bounding we get a contradiction so it works. If $t=2^m\cdot s$ where $s\ge 3$ is odd take $j=\frac{2^{m+1}+s-1}{2}$ and $l=\frac{|s-2^{m+1}|-1}{2}$.Then $j-l=min\{2,2^{m+1}\};j+l+1=max\{s,2^{m+1}\} $ so their product is $2t$ and their difference is not divisible by $t$ so we are done !! Comment:technical problem,but the ideas are easy to get and the calculation is not hard
P2nisic
15.06.2024 14:12
Rijul saini wrote: Let $n$ be a positive integer. Let $s: \mathbb N \to \{1, \ldots, n\}$ be a function such that $n$ divides $m-s(m)$ for all positive integers $m$. Let $a_0, a_1, a_2, \ldots$ be a sequence such that $a_0=0$ and \[a_{k}=a_{k-1}+s(k) \text{ for all }k\ge 1.\]Find all $n$ for which this sequence contains all the residues modulo $(n+1)^2$. Proposed by N.V. Tejaswi Let $x=an+b$ then we can see that $a_x=a\frac{n(n+1)}{2}+\frac{b(b+1)}{2}$ If $n=even$ then $a_{n(n+1)}=(n+1)\frac{n(n+1)}{2}\equiv 0(mod(n+1)^2))$ so in this case the sequanse haw period $n(n+1)$ so it can not contain all the residues modulo $(n+1)^2$. For $n=odd$ we have $n+1=2m+2$ we now can see that : $a\frac{n(n+1)}{2}=an(m+1)(mod (2m+2)^2)$ and since $(n,4m+2)=1$ we have that $a\frac{n(n+1)}{2}$ can take all the form $c*(m+1)(mod (2m+2)^2)$ So $\frac{b(b+1)}{2}$ should can take all residues $0,1,2,3,..,m(mod (m+1))$. If an odd prime number $p|m+1$ then we have contradiction since: $\frac{b(b+1)}{2}\equiv \frac{(-1-b)(1+(-1-b))}{2}(mod m+1)$ So $m+1=2^l$ then:$\frac{b(b+1)}{2}\equiv \frac{c(c+1)}{2}(mod(m+1))\Leftrightarrow m+1=2^l|\frac{(b-c)(b+c+1)}{2}$ From here esily we can see that $b=c$ so all $n+2^k-1$ works.
Monte-Cristo
18.06.2024 06:24
First note that $s_{nk+r}=k \frac{n(n+1)}{2}+\frac{r(r+1)}{2}$ where $1\le r\le n$.
We want $k \frac{n(n+1)}{2}+\frac{r(r+1)}{2}$ to contain all residues modulo $(n+1)^2$, which by Bezout's lemma is equivalent to saying that $\frac{r(r+1)}{2}$ takes all values modulo $\Big( \frac{n(n+1)}{2}, (n+1)^2\Big)$.
Claim 1: Even $n$ do not work.
Proof: Here $\Big( \frac{n(n+1)}{2}, (n+1)^2\Big)=n+1$, so we require $\{\frac{r(r+1)}{2}| 1\le r\le n\}$, a set of size $n$ to contain at least $n+1$ values, which is impossible.
Claim 2: $n=2^k-1$ works.
Proof: Here $\Big( \frac{n(n+1)}{2}, (n+1)^2\Big)=\frac{n+1}{2}$.
We will now see when $\frac{s_1(s_1+1)}{2}\equiv \frac{s_2(s_2+1)}{2}$ mod $2^{k-1}$.
We get that this holds iff $s_2\equiv s_1$ or $-1-s_1$ mod $2^k$ and from here we can get that there are exactly $\frac{n+1}{2}$ values taken mod $2^{k-1}$ as all values except 0 occur twice in $1, 2,..., n$, which finishes.
Claim 3: If $n+1=2^kd$ where $d>1$ is odd, then $n$ does not work.
Proof: We know that for any $s$, $\frac{r(r+1)}{2}$ is equal for $r=s$ and $r=-1-s$. Thus, each value except 0 occurs at least twice, so it suffices to show that $2^{k-1}| \frac{s(s+1)}{2}$ for some $s\ne n$. By CRT, there is some value $r$ at most $n+1$ for which $2^k|r$ and $d|r+1$ and we can verify that this value is neither $n+1$ nor $n$.