Finding the next $x \in \mathbb{Z}^+$ such that $x^2 \equiv 17 \pmod{2^{n+1}}$

elementary-number-theorymodular arithmetic

Only parts 4. and 5. are relevant, but for completion's sake, I'll just include the whole problem.

Let $N$ be any positive and let $S(N)$ be the set of remainders when the square numbers $0,1,4,9,\dots$ are divided by $N$.

  1. Prove that all the elements of $S(12)$ are square numbers.

  2. Find an odd integer $N$ and $x \in S(N)$ such that $x$ is not a square number.

  3. For all positive integers $N$, prove that $S(N)$ has at least $\sqrt{N}$ elements.

  4. It is given that there are integers $x,\lambda,n$, where $n \geq 5$, such that $x^2 = 17 + 2^n\lambda$. Prove that $17 \in S(2^{n+1})$.

  5. For $n \geq 5$, prove that $S(2^n)$ has at least $1 + \sqrt{2^n}$ elements.

I don't think part 1. to 3. are related to 4. at all, but I may be missing something. Firstly, part 1. to 3. are easy. For 1., we just need to show that $0,1,4,9,16,25$ have square remainders, as $(n + 6)^2 \equiv n^2 \pmod{12}$. For 2., we have $N = 7$, then $2 \in N$ as $9 \equiv 2 \pmod{7}$. For 3., simply observe that $\{0^2,1^2,\dots,(\lceil\sqrt{N}\rceil – 1)^2\} \subseteq S(N)$.

My main issue is part 4., as part 5. should follow immediately by induction and by part 3., where all of those $\sqrt{N}$ elements are perfect squares but not $17$.

Attempt: The first thing to observe for part 4. is that if $2 \mid \lambda$, then we are done. Thus, we just need to prove for the case of $\lambda$ is odd, which implies that $x^2 \equiv 17 + 2^n \pmod{2^{n+1}}$. My approaches revolve around constructing a square number that is $17 \pmod{2^n}$ from $x^2$.

  1. If $k$ is even, then $kx^2 \equiv 17k \pmod{2^{n+1}}$. Furthermore, $x^4 \equiv 17^2 \pmod{2^{n+1}}$. I observe that $x^4 – 16x^2 \equiv 17 \pmod{2^{n+1}}$, but of course we don't know if $x^4 – 16x^2$ is a square number.
  2. I conjectured that if $x^2 \equiv 17 \pmod{2^n}$ then $x^{2m} \equiv 17 \pmod{2^{n+1}}$ for some $m$. Taking the "base case" as $49 = 17 + 2^5$ and iterating it, it appears to be false.
  3. I tried to consider $(x + k)^2$ for some $k$, such as $(x + 2^n)^2 = x^2 + 2^{n+1}x + 2^{2n} \equiv x^2 \pmod{2^{n+1}}$. If this is indeed the approach, then we will have the carefully pick which $k$ to use. The main problem with this apprach is that we don't know what $x \pmod{2^n}$ looks like.

Any help would be appreciated.

Best Answer

If $\lambda$ is even, we're obviously done. If not, then notice that $x^2 \equiv 17 + 2^n \pmod{2^{n+1}}$, and so $\left( x - 2^{n-1} \right)^2 \equiv x^2 - 2^n + 2^{2n-2} \equiv \left( 17 + 2^n \right) - 2^n + 0 \equiv 17 \pmod{2^{n+1}}$. This is not too different conceptually from the standard proof that the multiplicative group of integers mod $p^2$ for $p$ prime has a generator.

EDIT: Oops, bad factors. Clearly $x$ is odd, so we may invert it $\pmod{2^{n+1}}$. Then expanding $\left( x - 2^{n-1} \mathbf{x^{-1}} \right)^2$ gives $x^2 - 2^n - \frac{2^{2n-2}}{x^2}$, but $x^2$ is nonzero and $2^{2n-2}$ is zero, so the last term is still $0$ and we're fine.

Related Question