From: achille on 31 Jul 2010 22:45 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 1 Aug 2010 01:35 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 1 Aug 2010 06:42 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 1 Aug 2010 12:35 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 1 Aug 2010 16:23
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 |