4

"The square root of a square number modulo 257 is unique modulo 257" (This is something that I have to prove or invalidate)

I don't understand what 'is unique modulo 257' means?

1 Answers1

6

It means that if $x^2 \equiv z \pmod {257}$ and $y^2 \equiv z \pmod {257}$ then $x \equiv y \pmod {257}$.

Generally "a thing with property X is unique modulo ..." means that if two things have property X (in this case, their square is equivalent to the same number mod 257) then they are equivalent in whatever the equivalence relation following the word "modulo" is.

Ian
  • 101,645
  • 1
    Thank you for your answer, I'm trying to understand it. If x^2 and y^2 are equivalent to the same number mod 257, would that mean that x^2 = y^2? –  Oct 03 '18 at 23:19
  • 1
    @Capucine No, "equivalent to the same number mod 257" means that they give the same remainder when you try to divide them by 257. For example $1 \equiv 5 \pmod 4$. – Ian Oct 03 '18 at 23:26
  • 1
    @Capucine It is a little hard to tell from your question... modulo odd primes, square roots come in $\pm$ pairs. In particular, the square roots of $-1$ are $16, 241 \pmod {257},$ as $16^2 = 256 \equiv -1 \pmod {257}.$ There is typically a unique pair... Note $241^2 + 1 = 257 \cdot 226$ – Will Jagy Oct 03 '18 at 23:35
  • 1
    @Ian Oh thank you! I think I understand now :) –  Oct 03 '18 at 23:45
  • 1
    @WillJagy I forgot to say that x must be a natural number, so it can't be -1 or any other negative number. My mistake! –  Oct 03 '18 at 23:48
  • 1
    @Capucine Are you sure you understand? Do you think that the claim in the first sentence in your answer is correct? – Bill Dubuque Oct 03 '18 at 23:49
  • 1
    @Capucine I suspect the writers of the question actually intend for you to invalidate the statement through just the sort of example that Bill has been alluding to. Perhaps it's invalid in your context for you to refer to the $\pm$ pairs in that exact fashion, but keep in mind that mod $n$, $-1$ and $n-1$ are equivalent... – Ian Oct 03 '18 at 23:53
  • 1
    I did invalidate the claim, with x=250 and y=7 (if I understand it correctly?). –  Oct 04 '18 at 00:15
  • 1
    @Capucine Yes, that one will do the job (since 250 is equivalent to -7). – Ian Oct 04 '18 at 00:44
  • 1
    @Ian Thanks! I'm trying to understand what you mean when you say "mod n, −1 and n−1 are equivalent"? Something like 9mod4 -1=0 and (9-1)mod4=0? –  Oct 04 '18 at 00:48
  • 1
    $-1 \equiv 7 \pmod 4$ for example. – Ian Oct 04 '18 at 01:16
  • 1
    @Ian I see, thanks! –  Oct 04 '18 at 01:34