Ggrmanova T.A.

Tanya sequentially wrote down numbers of the form $\{n \wedge 7-1\}$ for natural numbers $n=2,3, \dots$ and noticed that for $n=8$ the resulting number is divisible by 337. For what smallest $n>1$ will she get a number divisible by $2022?$
Let the natural number \$ \$ \$ be such that \$n $\wedge 7-1$ \$ is divisible by \$2022=21cdot 3lcdot 337\$. Then \$n 2 and on 3 , so $\$ n \$-$ is an odd number, having a remainder of 1 when divided by 3. In addition, $\$ n \wedge 7-1$ is divisible by 337. Note that if two numbers are congruent modulo 337 (i.e., they give the same remainder when divided by 337), then the seventh powers of these numbers are also congruent modulo 337. This means that to find the desired number, it is sufficient to consider all integers $\$ \mathrm{n} \$$ from the interval $\$[0 ; 336] \$$, satisfying the congruence $\$ \mathrm{n} \wedge 7$ lequiv $1 \backslash p \operatorname{lod}\{337\} \$$.

We will use the following statement. Let \$p\$ be a prime number, \$P_k\$ be a polynomial of degree \$k\$ with integer coefficients, the leading coefficient of which is not divisible by \$p\$; then the congruence \$P_k(n)ไequiv 01 pmod p $\$$ has no more than $\$ k \$$ solutions among the integers $\$ 0 \backslash l e q s l a n t ~ n ~<p \$$. (This statement can be proven by induction on the degree $\$ k \$$, in a similar way to the fact that a polynomial of degree $\$ k \$$ with real coefficients has no more than \$k\$ real roots. See also the article by A. Geronimus "Congruences modulo a prime" in Kvant No. 11 for 1978.)

Now let's find all solutions to the congruence $\$ n \wedge 7 \backslash$ equiv $1 \backslash p \operatorname{lod}\{337\} \$$ on the interval $\$[0 ; 336] \$$. We know two solutions: \$n_1=1\$, \$n_2=8\$. Note that if \$n\$ is a solution to the congruence \$n^7 \equiv $1 \backslash$ pmod\{337\}\$, then for any natural $\$ s \$$ the numbers $\$ n \wedge s \$$ are also solutions. Therefore, the solutions to this congruence are \begin{align*} 8^2\&=64\equiv } 6 4 \backslash p m o d \{ 3 3 7 \} , \backslash \backslash 8 ^ { \wedge } 3 \& = 5 1 2 \backslash e q u i v 1 7 5 \backslash p m o d \{ 3 3 7 \} , \backslash \backslash

![](https://cdn.mathpix.com/cropped/2024_05_06_278dceb3f0947a8409cfg-02.jpg?height=48&width=1940&top_left_y=296&top_left_x=-1)
$79 \backslash$ equiv $295 \backslash$ pmod $\{337\}$. \end{align*}

Thus, we have found seven solutions on the interval $\$[0 ; 336] \$:$ \$n_1=1\$, \$n_2=8\$, \$n_3=52\$, \$n_4=64\$, \$n_5=79\$, \$n_6=175\$, \$n_7=295\$. Since the number 337 is prime, by the above statement, there are no other solutions on this interval. Among them, the odd numbers with a remainder of 1 when divided by 3 are \$n_1=1\$, \$n_5=79\$, \$n_6=175\$ and \$n_7=295\$. The smallest one greater than 1 is \$n_5=79\$.

## Answer

79.