quasi
Posts:
12,067
Registered:
7/15/05


Re: a contradiction worth reading (unless a silly mistake was made)
Posted:
Jul 22, 2011 11:30 PM


On Fri, 22 Jul 2011 19:16:52 0700 (PDT), Simon Roberts <2assume@gmail.com> wrote:
>Say the set S = {1,2,3,...,(n2),(n1)}. >Then if we squared each element x_i in S, we would get a new >set S' (with (n1)/2 elements) whose elements would be >x_i)^2 mod n. Note we are assuming (n1)/2 is odd, so >n = 3 mod 4. If we square each element in S' >((x_i)^2)^2 mod n we would end up with the same exact set S' >and so on. > >Do you agree with this statement?
Yes, assuming also that n is a prime. Actually, it still holds if n is a product of an odd number of primes all congruent to 3 (mod 4). By the way  usually the letter p is used to emphasize that a variable is prime.
One of my main complaints with your "statements" is that you assume things not stated. Can't you make a complete statement? Why do I always have to do it for you?
Here's what you're claiming now:
Proposition:
If p is prime with p = 3 (mod 4), then the sets
{x^2 (mod p)  x = 1,2,3 ... (p1)}
{x^4 (mod p)  x = 1,2,3 ... (p1)}
are equal.
Remark:
The above claim is true and is easily proved, but that does _not_ yield a proof of your prior claim:
False Proposition:
If p is prime with p = 3 (mod 4), then for all integers x,y not congruent to 0,1,1 (mod p), the sets
{x^(2^i) (mod p)  i = 1,2,3 ...}
{y^(2^j) (mod p)  j = 1,2,3 ...}
are equal.
Counterexample: p = 19. quasi

