I have a few questions about how squares affect mods. Here they are:
1. Assume p to be an odd prime and a is any integer not congruent to 0 modulo p. It can be proven that the congruence (x^2) = ((-a)^2)(mod p) has solutions IFF p = 1 (mod 4).
How is that proven?
2. Assume there are two numbers c and d where GCD[c,d]=1. If p is any prime number and p|((c^2)+(d^2)), then p = 1 (mod 4),
How is this also proven ?
Any help is greatly appreciated!
So how did you get 1 and 4 out of that expression? I'm sure its really simple, but trial and error is the only way I've shown it thus far. Isn't there a more "concrete" way to get 1 and 4 and not using guess & check?
I will certainly appreciate it if you help me with 1.) . Much thanks will be given!
Lemma: Given , suppose is the smallest number greater than such that and where , then .
Proof: By the division algorithm, where . So we then get . Since and , by the minimality of this forces . So we see that .
Suppose is solvable. This implies is solvable. So observe that it's equivalent to show solvable implies .
Since is odd, , so we have the following:
So as you can see, is the smallest exponent greater than such that . Now by Fermat's little theorem, since . By our above Lemma, this implies .