quasi
Posts:
10,226
Registered:
7/15/05


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


On Fri, 22 Jul 2011 15:50:24 0500, quasi <quasi@null.set> wrote:
>On Fri, 22 Jul 2011 10:06:10 0700 (PDT), Simon Roberts ><2assume@gmail.com> wrote: > >>Please correct me if this is not well written but for each >>i>=1 and every x x^(2^i) mod n forms a set that is identical >>to the set x^(2^j) mod n j>=1 j!=i. > >It's poorly written: > >(1) You never specified your intended restrictions on n. > >(2) You didn't specify any restrictions on x. What about >x = 0 (mod p)? What about x = 1 or 1 (mod p)? > >Would it have hurt you to at least give a careful and >complete statement of the proposition you're claiming is >true? It shouldn't be necessary for people to piece >together your claim from prior messages, many of which >may have already been deleted from their news interface >(not everyone uses Google Groups). > >I'll state what it appears you're claiming ... > >Proposition: > >if p is prime with p = 3 (mod 4), then for all integers x,y >with x,y not congruent to 0,1,1 (mod p), > > {x^(2^i), i = 1,2,3, ...} = {y^(2^j), j = 1,2,3, ...}
I meant:
{x^(2^i) (mod p), i = 1,2,3, ...} = {y^(2^j) (mod p), j = 1,2,3, ...}
>>I don't know if this is a well known result and if it has >>or can be proved more simply. > >It's not well known, and it hasn't and can't be proved since >it's false. For example, try p = 19. > >In fact, for primes p = 3 (mod 4), the claim of the above >proposition is always false if (p1)/2 is composite, and it's >even false in many cases where (p1)/2 is prime. > >The primes p = 3 (mod 4) with p < 1000 and (p1)/2 also prime >for which the conclusion of the above proposition holds are: > > 7,11,23,59,107,167,263,347,359,587,839,887,983 > >Question: > >For which primes p = 3 (mod 4) with (p1)/2 also prime does >the conclusion of the above proposition hold? > > >Remark: > >However, a quick scan of the data suggests the following >tentative claim ... > >Conjecture: > >If p is prime with p = 3 (mod 4) and (p1)/2 also prime, then >for all integers x,y with x,y not congruent to 0,1,1 (mod p), >the sets > > {x^(2^i), i = 1,2,3, ...} > > {y^(2^j), j = 1,2,3, ...} > >have the same number of elements.
I meant:
the sets
{x^(2^i) (mod p), i = 1,2,3, ...}
{y^(2^j) (mod p), j = 1,2,3, ...}
have the same number of elements.
quasi

