Search All of the Math Forum:

Views expressed in these public forums are not endorsed by Drexel University or The Math Forum.

Replies: 73   Last Post: Jul 24, 2011 8:55 PM

 Messages: [ Previous | Next ]
 quasi Posts: 9,078 Registered: 7/15/05
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

Date Subject Author
7/19/11 Simon Roberts
7/19/11 Simon Roberts
7/19/11 Simon Roberts
7/19/11 byron
7/19/11 Simon Roberts
7/19/11 quasi
7/19/11 quasi
7/19/11 Simon Roberts
7/19/11 quasi
7/19/11 Simon Roberts
7/19/11 quasi
7/19/11 Simon Roberts
7/19/11 quasi
7/19/11 Simon Roberts
7/19/11 Simon Roberts
7/19/11 Simon Roberts
7/19/11 Simon Roberts
7/19/11 Simon Roberts
7/19/11 Simon Roberts
7/20/11 quasi
7/20/11 quasi
7/20/11 Simon Roberts
7/20/11 quasi
7/20/11 Simon Roberts
7/20/11 tommyrjensen@gmail.com
7/20/11 Simon Roberts
7/20/11 tommyrjensen@gmail.com
7/20/11 Simon Roberts
7/20/11 tommyrjensen@gmail.com
7/20/11 Simon Roberts
7/20/11 Simon Roberts
7/20/11 tommyrjensen@gmail.com
7/20/11 Simon Roberts
7/20/11 Simon Roberts
7/20/11 Simon Roberts
7/20/11 tommyrjensen@gmail.com
7/20/11 Simon Roberts
7/20/11 Simon Roberts
7/20/11 Simon Roberts
7/20/11 Simon Roberts
7/20/11 Simon Roberts
7/20/11 Simon Roberts
7/20/11 Simon Roberts
7/20/11 Simon Roberts
7/22/11 Simon Roberts
7/22/11 quasi
7/22/11 Simon Roberts
7/22/11 Simon Roberts
7/22/11 quasi
7/22/11 quasi
7/22/11 quasi
7/22/11 quasi
7/24/11 quasi
7/22/11 Simon Roberts
7/22/11 quasi
7/22/11 Simon Roberts
7/22/11 Simon Roberts
7/22/11 Simon Roberts
7/22/11 Simon Roberts
7/22/11 quasi
7/23/11 Simon Roberts
7/23/11 quasi
7/23/11 Simon Roberts
7/23/11 Simon Roberts
7/23/11 quasi
7/23/11 Simon Roberts
7/23/11 Simon Roberts
7/23/11 Simon Roberts
7/23/11 quasi
7/24/11 Bill Dubuque
7/24/11 Brian Q. Hutchings
7/23/11 quasi
7/24/11 quasi
7/22/11 quasi