NetNews Usenet Archive 1992 #18/NN_1992_18.iso/spool/sci/math/10470

Internet Message Format | 1992-08-20 | 1.9 KB

Path: sparky!uunet!dtix!darwin.sura.net!jvnc.net!nuscc!bhonsle!bhonsle
From: [e-mail] (Shailendra K Bhonsle)
Newsgroups: sci.math
Subject: Can you do it
Keywords: number theory
Message-ID: <[e-mail]>
Date: 21 Aug 92 02:00:53 GMT
Sender: bhonsle@bhonsle (Shailendra K Bhonsle)
Followup-To: Can you do it?
Organization: Institute of Systems Science, NUS, Singapore
Lines: 56



>>In an article in sci.math, you said:

>>:Prove that for primes p & q, q<p
>>:
>>:if 2^(p-1) == 1 (mod q^2)
>>:then either 2^(q-1) == 1 (mod q^2) or q | p-1  { q divides (p-1}
>>:
>>:I have some sort of solution but I am not very sure.
>>::Shailendra
>>:
>>:(bhonsle @ iss.nus.sg)

>>Bob Silverman ([e-mail]) replied:

>>> We have that 2 has order p-1 in the group of units of Z/q^2Z.
>>> Hence, p-1 | phi(q^2) by Lagrange's theorem.

>That's not correct.  We only know that  2^(p-1)  is 1, not that  p-1  is
>the minimal exponent such that  2^e  is 1.  E.g. p=13 and q=3 satisfy the
>hypothesis, but not Bob's conclusion.

>Here's a correct proof:  Let s be the order of 2 mod q; i.e. s is the
>smallest positive integer such that  2^s == 1 (mod q).  Note that
>s | p-1  and  s | q-1,  since both  2^(p-1)  and  2^(q-1)  are congruent
>to 1 mod q.
>
>Let  2^s = 1 + qk.
>
>If k is divisible by q, then  2^s == 1 (mod q^2).  Since  s | q-1,  it
>follows that  2^(q-1) == 1 (mod q^2).
>
>If k is not divisible by q, let  p-1 = sr.  Then  1 == 2^(p-1) =
>(2^s)^r = (1+qk)^r == 1 + qkr (mod q^2).  So  q^2 | qkr.  Since k is
>not divisible by q, it follows that  q | r,  so  q | p-1.
>
>(Note that the assumption that p is prime is not needed.)
>
>Dean Hickerson
>[e-mail]


Absolutely correct, (I think). I had exactly the same proof.

It is very interesting to note that p may not be prime.

Thanks a lot.

Shailendra

N.B.: I will post this article on the net.



--