quasi
Posts:
9,078
Registered:
7/15/05
|
|
Re: a contradiction worth reading (unless a silly mistake was made)
Posted:
Jul 20, 2011 4:48 AM
|
|
On Wed, 20 Jul 2011 03:31:15 -0500, quasi <quasi@null.set> wrote:
>Simon Roberts initially claimed:
>
>>there exists an i: 1<i<=(n-3)/2 when n is prime and (n-1)/2
>>is odd such that x^(2^i)=x^2 (mod n)
>
>As I noted in a previous reply, the above is false, however
>as Simon Roberts noted in a later reply, the counterexample
>I provided is avoided if the expression (n-3)/2 above is
>replaced with (n-1)/2.
>
>In fact, Simon Roberts' revised claim is true.
>
>Here's a version of the revised claim, with proof ...
>
>Proposition:
>
>Let p be prime with p > 3 and p = 3 (mod 4), and let x
>be an integer which is not a multiple of p. Then
>
> x^(2^e) = x^2 (mod p)
>
>for some integer e with phi(w) < e <= w, where w = (p-1)/2.
>
>proof:
>
>Fix an integer x which is not a multiple of p. Let w = (p-1)/2.
>
> p = 3 (mod 4) => w is odd => gcd(2,w) = 1.
>
>By Fermat's Little Theorem, 2^(phi(w)) = 1 (mod w), hence
>
> 2^((phi(w) + 1) = 2 (mod (p-1)).
>
>Letting e = phi(w) + 1, we get
>
> 2^e = 2 (mod (p-1)).
>
>Then e = phi(w) + 1 => phi(w) < e <= w.
>
>Again by Fermat's Little Theorem
>
> 2^e = 2 (mod (p-1)) => x^(2^e) = x^2 (mod p),
>
>which completes the proof.
Actually, the statement of the claim can be improved.
Proposition:
If p is prime with p = 3 (mod 4), then for all integers x,
x^(2^e) = x^2 (mod p)
where e = phi((p-1)/2) + 1.
proof: Same as my previous proof.
quasi
|
|
