Given positive odd number $m$ and integer ${a}.$ Proof: For any real number $c,$ $$\#\left\{x\in\mathbb Z\cap [c,c+\sqrt m]\mid x^2\equiv a\pmod m\right\}\le 2+\log_2m.$$Proposed by Yinghua Ai
Problem
Source: 2024 CTST P12
Tags: number theory, 2024 CTST
12.03.2024 04:35
12.03.2024 05:12
We can in fact prove a bound of $\omega(m) + 1$ for $m > 1$. First, note that by reducing to smaller values of $m$, we may assume that $a$ is coprime to $m$. If this reduction takes $m$ to $1$, then we get a bound of $2 \leq \omega(m) + 1$. Now assume $m > 1$. Let $q_1,\ldots,q_k$ be the prime powers dividing $m$ and for each $i$ choose a square root $r_i$ of $a$ modulo $q_i$. Given some $x$ with $x^2 \equiv a \pmod{m}$, associate to it the vector $\mathbf{v}_x = (v_1,\ldots,v_k)$, where $v_i = \sqrt{\log q_i}$ if $x \equiv r_i \pmod{q_i}$ and $v_i = -\sqrt{\log q_i}$ if $x \equiv -r_i \pmod{q_i}$. The key observation is that if $0 < \lvert x - y \rvert \leq \sqrt{m}$, then $\mathbf{v}_x \cdot \mathbf{v}_y < 0$, since otherwise $x - y$ would be divisible by a product of the $q_i$'s that is strictly larger than $\sqrt{m}$. The result now follows immediately from the well-known fact that the maximum number of mutually obtuse vectors in $\mathbb{R}^k$ is $k+1$.
12.03.2024 11:43
EthanWYX2009 wrote: The skill here is Gallagher's Sieve, which is introduced in Chapter 2 of SFTB. What's interesting, CTST really requires many techniques, we need Mobius inversion in P3, Ramsey theory on hypergraph in P9, and Gallagher in P12 you're right, and the competitors may have advantages over others if they have wide view in mathematics in tst
12.03.2024 11:43
First TST3 this year! I have no patience to write down a neat solution, so...... The skill here is Gallagher's Sieve, which is introduced in Chapter 2 of SFTB. What's interesting, CTST really requires many techniques, we need Mobius inversion in P3, Ramsey theory on hypergraph in P9, and Gallagher in P12
13.03.2024 21:06
What is SFTB?
22.03.2024 09:26
@EthanWYX2009 could you kindly write your solution in latex, so it would be nicer to follow. Thank you.
29.03.2024 17:16
@bruhmomentmathematics SFTB is straight from the book - a sister book of problems from the book , A legendary book in my opinion! You can get its PDF from the net