0

Let $ k $ be a positive integer. Let x be a positive integer that satisfies $ x \not\equiv 0 \pmod{8} $ and $ x \not\equiv 4 \pmod{8} $. Then is the following statement true?

$$ x^2 \equiv k^2 \pmod{16} \iff x \equiv \pm k \pmod{8}. $$

Example: Let $ x = 13 $. Then $ x^2 = 169 \equiv 9 \pmod{16} $ and $ x \equiv 5 \equiv -3 \pmod{8} $.

How can I prove it without enumerating all 16 possible cases for $ k $?

Lone Learner
  • 1,076
  • Show what you tried and where you got stuck. – Anne Bauval Oct 24 '22 at 20:39
  • 3
    There are so few classes $\pmod {16}$...if all else fails, just list them all and check by hand. – lulu Oct 24 '22 at 20:39
  • @lulu Is it possible to prove this without enumerating all possible cases by hand? While this is a specific question with modulo 16, if there is a way to prove this without enumerating all cases, it would help me to attack such problems for arbitrary modulus too. – Lone Learner Oct 24 '22 at 20:43
  • 1
    I don't understand why you wouldn't just do the enumeration. It only takes a second and then you know the answer. As to generalizations, well of course it depends on the sort of generalization you had in mind. As a rule though, looking at the congruence $x^2\equiv 1 \pmod n$ is a good place to start. – lulu Oct 24 '22 at 20:45
  • You could perhaps learn things by enumerating. for example, $13=-3$ then $13^2=(-3)^2=9$. Which could be useful for other problems. – Stéphane Jaouen Oct 24 '22 at 20:47
  • Thank you for the comments! Yes, enumeration does show that this is true. I am still struggling to prove it without using enumeration though. The part I am having trouble with is: How do we start with a congruence modulo 16 and drop down to a congruence modulo 8? – Lone Learner Oct 24 '22 at 20:50
  • @AnneBauval Can you provide a value of $ x $ that is a counterexample? – Lone Learner Oct 24 '22 at 20:53
  • For the case in which $x$ is coprime to $16$: If $x^2\equiv 1 \pmod {16}$ then $(x-1)(x+1)\equiv 0\pmod {16}$ and since $\gcd(x-1, x=1)≤2$ we see that one of the factors must be $0\pmod 8$ – lulu Oct 24 '22 at 20:54
  • @AnneBauval Are you possibly overlooking the fact that the OP excluded $x\in {0,4}$? – lulu Oct 24 '22 at 20:55
  • 1
    @AnneBauval No worries, I made the same error initially. – lulu Oct 24 '22 at 20:56

1 Answers1

-1

According to the condition, $$16|x^2-k^2$$ $$\implies16|(x+k)(x-k) $$ As $(x+k)$ and $(x-k)$ have the same parity, they must both be even.
So, we have a number of sub-cases, one of which is:
$4|(x+k)$ and $4|(x-k)$
This is precisely where $x\equiv \pm k\pmod8$ does not hold anymore.
A good counterexample would be that $256\equiv 16\pmod{16}$ is true, but, $ 16\not\equiv \pm4\pmod8$
I hope your question has been resolved.

Rijhi
  • 15