From: achille on
On Aug 1, 9:38 am, david <dlee...(a)yahoo.com> wrote:
> Consider the following equation for the given condition.
>
>      2^[(k-1)(k-2)] = 1 mod k^2               (1)
>
> Condition: prime k > 3.
>
> Question: For what value of k (1) is valid?
>
> A helpful reply will be appreciated.
>
> David

(1) is true iff k is an Wieferich prime (eg 1093 or 3511).

The key is to use Euler's theorem ( \phi(x) below is the
Euler's totient function):

gcd(2,k^2) = 1
=> 2^{\phi(k^2)} = 1 mod k^2.
=> 2^{k(k-1)} = 1

to replace (1) with (1)' 2^{2(k-1)} = 1 mod k^2.
From: achille on
On Aug 1, 12:48 pm, Rob Johnson <r...(a)trash.whim.org> wrote:
> In article <92e181c5-a6b2-4280-8892-90d3ef0f9...(a)q22g2000yqm.googlegroups..com>,
>
> david <dlee...(a)yahoo.com> wrote:
> >Consider the following equation for the given condition.
>
> >     2^[(k-1)(k-2)] = 1 mod k^2               (1)
>
> >Condition: prime k > 3.
>
> >Question: For what value of k (1) is valid?
>
> >A helpful reply will be appreciated.
>
> If k is prime, then phi(k^2) = k(k-1).  If k is odd, gcd(2,k) = 1.
> These two conditions imply
>
>      k(k-1)          2
>     2       = 1 mod k                                        [1]
>
> Using this, we get that
>
>      (k-1)(k-2)    -2(k-1)      2
>     2           = 2        mod k                             [2]
>
> So, your question reduces to
>
>      k-1          2
>     4    = 1 mod k                                           [3]
>
> Since 2^{k-1} = 1 mod k^2 for Wieferich primes, [3] must be true
> also, but there could be other primes that satisfy [3].  I have run
> a check on the first 5,000,000 primes, and the only k less than or
> equal to 86,028,121 which satisfy [3] are the Wieferich primes:
> 1093 and 3511.
>
> Rob Johnson <r...(a)trash.whim.org>
> take out the trash before replying
> to view any ASCII art, display article in a monospaced font

\for all odd prime k,
2^(k-1) = 1 mod k => \exists m s.t. 2^(k-1) = 1 + m k

So 4^(k-1) = 1 mod k^2
<=> ( 1 + k m )^2 = 1 mod (k^2)
<=> 2 m k = 0 mod(k^2)
=> m = 0 mod(k)
=> 2^(k-1) = 1 mod(k^2) ie. k need to be Wieferich primes.
From: Rob Johnson on
In article <949d7e70-1f46-4732-b196-a6c0f16979a8(a)p11g2000prf.googlegroups.com>,
achille <achille_hui(a)yahoo.com.hk> wrote:
>On Aug 1, 12:48 pm, Rob Johnson <r...(a)trash.whim.org> wrote:
>> In article <92e181c5-a6b2-4280-8892-90d3ef0f9...(a)q22g2000yqm.googlegroups.com>,
>>
>> david <dlee...(a)yahoo.com> wrote:
>> >Consider the following equation for the given condition.
>>
>> > 2^[(k-1)(k-2)] = 1 mod k^2 (1)
>>
>> >Condition: prime k > 3.
>>
>> >Question: For what value of k (1) is valid?
>>
>> >A helpful reply will be appreciated.
>>
>> If k is prime, then phi(k^2) = k(k-1). If k is odd, gcd(2,k) = 1.
>> These two conditions imply
>>
>> k(k-1) 2
>> 2 = 1 mod k [1]
>>
>> Using this, we get that
>>
>> (k-1)(k-2) -2(k-1) 2
>> 2 = 2 mod k [2]
>>
>> So, your question reduces to
>>
>> k-1 2
>> 4 = 1 mod k [3]
>>
>> Since 2^{k-1} = 1 mod k^2 for Wieferich primes, [3] must be true
>> also, but there could be other primes that satisfy [3]. I have run
>> a check on the first 5,000,000 primes, and the only k less than or
>> equal to 86,028,121 which satisfy [3] are the Wieferich primes:
>> 1093 and 3511.
>
>\for all odd prime k,
> 2^(k-1) = 1 mod k => \exists m s.t. 2^(k-1) = 1 + m k
>
>So 4^(k-1) = 1 mod k^2
><=> ( 1 + k m )^2 = 1 mod (k^2)
><=> 2 m k = 0 mod(k^2)
> => m = 0 mod(k)
> => 2^(k-1) = 1 mod(k^2) ie. k need to be Wieferich primes.

Indeed. Thanks.

Rob Johnson <rob(a)trash.whim.org>
take out the trash before replying
to view any ASCII art, display article in a monospaced font
From: david on
On Aug 1, 12:48 am, Rob Johnson <r...(a)trash.whim.org> wrote:
> In article <92e181c5-a6b2-4280-8892-90d3ef0f9...(a)q22g2000yqm.googlegroups..com>,
>
> david <dlee...(a)yahoo.com> wrote:
> >Consider the following equation for the given condition.
>
> >     2^[(k-1)(k-2)] = 1 mod k^2               (1)
>
> >Condition: prime k > 3.
>
> >Question: For what value of k (1) is valid?
>
> >A helpful reply will be appreciated.
>
> If k is prime, then phi(k^2) = k(k-1).  If k is odd, gcd(2,k) = 1.
> These two conditions imply
>
>      k(k-1)          2
>     2       = 1 mod k                                        [1]
>
> Using this, we get that
>
>      (k-1)(k-2)    -2(k-1)      2
>     2           = 2        mod k                             [2]
>
> So, your question reduces to
>
>      k-1          2
>     4    = 1 mod k                                           [3]
>
> Since 2^{k-1} = 1 mod k^2 for Wieferich primes, [3] must be true
> also, but there could be other primes that satisfy [3].  I have run
> a check on the first 5,000,000 primes, and the only k less than or
> equal to 86,028,121 which satisfy [3] are the Wieferich primes:
> 1093 and 3511.
>
> Rob Johnson <r...(a)trash.whim.org>
> take out the trash before replying
> to view any ASCII art, display article in a monospaced font

---- ----- -----
So you agree that (A) implies (B) pl see below

2^[(k-1)(k-2)] = 1 mod k^2 (A)

k-1 2
4 = 1 mod k (B)

Where k is Wieferich prime. Otherwise, A does not imply B.

Right or wrong ?

--- ---- ---- ---- --
From: Rob Johnson on
In article <bf6419c3-0449-4e33-8ec2-0984a7d697ea(a)s24g2000pri.googlegroups.com>,
david <dlee753(a)yahoo.com> wrote:
>On Aug 1, 12:48 am, Rob Johnson <r...(a)trash.whim.org> wrote:
>> In article <92e181c5-a6b2-4280-8892-90d3ef0f9...(a)q22g2000yqm.googlegroups.com>,
>>
>> david <dlee...(a)yahoo.com> wrote:
>> >Consider the following equation for the given condition.
>>
>> > 2^[(k-1)(k-2)] = 1 mod k^2 (1)
>>
>> >Condition: prime k > 3.
>>
>> >Question: For what value of k (1) is valid?
>>
>> >A helpful reply will be appreciated.
>>
>> If k is prime, then phi(k^2) = k(k-1). If k is odd, gcd(2,k) = 1.
>> These two conditions imply
>>
>> k(k-1) 2
>> 2 = 1 mod k [1]
>>
>> Using this, we get that
>>
>> (k-1)(k-2) -2(k-1) 2
>> 2 = 2 mod k [2]
>>
>> So, your question reduces to
>>
>> k-1 2
>> 4 = 1 mod k [3]
>>
>> Since 2^{k-1} = 1 mod k^2 for Wieferich primes, [3] must be true
>> also, but there could be other primes that satisfy [3]. I have run
>> a check on the first 5,000,000 primes, and the only k less than or
>> equal to 86,028,121 which satisfy [3] are the Wieferich primes:
>> 1093 and 3511.
>>
>> Rob Johnson <r...(a)trash.whim.org>
>> take out the trash before replying
>> to view any ASCII art, display article in a monospaced font
>
>---- ----- -----
>So you agree that (A) implies (B) pl see below
>
> 2^[(k-1)(k-2)] = 1 mod k^2 (A)
>
> k-1 2
> 4 = 1 mod k (B)
>
> Where k is Wieferich prime. Otherwise, A does not imply B.
>
> Right or wrong ?
>
>--- ---- ---- ---- --

Wrong. Assuming k is an odd prime, (A) and (B) are equivalent.
That's because for any odd prime k,

k(k-1) 2
2 = 1 mod k

Rob Johnson <rob(a)trash.whim.org>
take out the trash before replying
to view any ASCII art, display article in a monospaced font