mersenneforum.org  

Go Back   mersenneforum.org > Great Internet Mersenne Prime Search > Math

Reply
 
Thread Tools
Old 2005-04-11, 06:30   #1
devarajkandadai
 
devarajkandadai's Avatar
 
May 2004

22×79 Posts
Default A Counter example, anyone?

I may be wrong but I feel it may be difficult to cite a counter to the following:

Let N = P1P2P3 be a three factor composite number.

The necessary & sufficient condition for N to be a pseudo-prime is that
atleast one of the following should be an integer:

( P1 - 1)(N - 1)/(P2 -1)(P3-1),

(P2-1)(N - 1)/(P1 -1)(P3 - 1) or

(P3 - 1)(N -1)/(P1 -1)(P2 -1)

A.K. Devaraj
devarajkandadai is offline   Reply With Quote
Old 2005-04-11, 08:54   #2
Dougy
 
Dougy's Avatar
 
Aug 2004
Melbourne, Australia

9816 Posts
Default Integer !=> Pseudoprime

Double check this, but if we take 42 = 2 x 3 x 7.

Then (7-1) x (42-1) / ((2-1) x (3-1)) = 6 x 41 / 2 = 123 is an integer.

However there does not exist a whole number a such that a^41 = 1 (mod 42) (a != 1 mod 42)
Dougy is offline   Reply With Quote
Old 2005-04-12, 02:32   #3
devarajkandadai
 
devarajkandadai's Avatar
 
May 2004

1001111002 Posts
Default

Quote:
Originally Posted by Dougy
Double check this, but if we take 42 = 2 x 3 x 7.

Then (7-1) x (42-1) / ((2-1) x (3-1)) = 6 x 41 / 2 = 123 is an integer.

However there does not exist a whole number a such that a^41 = 1 (mod 42) (a != 1 mod 42)
I should have specified the Ps as odd prime numbers;now I am not sure u will
be able to cite a counter example.
A.K. Devaraj

Last fiddled with by devarajkandadai on 2005-04-12 at 02:33 Reason: "am" left out
devarajkandadai is offline   Reply With Quote
Old 2005-04-12, 23:34   #4
maxal
 
maxal's Avatar
 
Feb 2005

22×32×7 Posts
Default

Quote:
Originally Posted by devarajkandadai
Let N = P1P2P3 be a three factor composite number.

The necessary & sufficient condition for N to be a pseudo-prime is that
atleast one of the following should be an integer:

( P1 - 1)(N - 1)/(P2 -1)(P3-1),

(P2-1)(N - 1)/(P1 -1)(P3 - 1) or

(P3 - 1)(N -1)/(P1 -1)(P2 -1)
It seems to work only in one direction (which is a particular case of your previous conjecture), i.e., if N is pseudo-prime then at least one (actually, all three) of the specified fractions is integer.
But there are such non-pseudoprime N for which at least one of the fractions is integer.
The smallest counterexamples:
105 = 3*5*7
165 = 3*5*11
195 = 3*5*13
maxal is offline   Reply With Quote
Old 2005-04-13, 03:52   #5
mfgoode
Bronze Medalist
 
mfgoode's Avatar
 
Jan 2004
Mumbai,India

22×33×19 Posts
Smile

Quote:
Originally Posted by maxal
It seems to work only in one direction (which is a particular case of your previous conjecture), i.e., if N is pseudo-prime then at least one (actually, all three) of the specified fractions is integer.
But there are such non-pseudoprime N for which at least one of the fractions is integer.
The smallest counterexamples:
105 = 3*5*7
165 = 3*5*11
195 = 3*5*13

There are two types of pseudo-primes viz 1) Fermat pseudo-primes and 2) Carmichael numbers. Kindly clarify which are you referring too.
Mally
mfgoode is offline   Reply With Quote
Old 2005-04-13, 03:59   #6
maxal
 
maxal's Avatar
 
Feb 2005

22×32×7 Posts
Default

Quote:
Originally Posted by mfgoode

There are two types of pseudo-primes viz 1) Fermat pseudo-primes and 2) Carmichael numbers. Kindly clarify which are you referring too.
Either one. The quoted counterexamples are neither Fermat pseudoprimes, nor Carmichael numbers.
maxal is offline   Reply With Quote
Old 2005-04-13, 04:28   #7
mfgoode
Bronze Medalist
 
mfgoode's Avatar
 
Jan 2004
Mumbai,India

22·33·19 Posts
Question A Counter example anyone?

Quote:
Originally Posted by maxal
Either one. The quoted counterexamples are neither Fermat pseudoprimes, nor Carmichael numbers.

Thank you maxal . Could you please elaborate the distinction between them and the no.s. you have derived as Im a bit confused
Mally
mfgoode is offline   Reply With Quote
Old 2005-04-13, 04:55   #8
maxal
 
maxal's Avatar
 
Feb 2005

22×32×7 Posts
Default

Quote:
Originally Posted by mfgoode
Could you please elaborate the distinction between them
See http://mathworld.wolfram.com/FermatPseudoprime.html and http://mathworld.wolfram.com/CarmichaelNumber.html
Quote:
Originally Posted by mfgoode
and the no.s. you have derived
What's "no.s." ?
maxal is offline   Reply With Quote
Old 2005-04-13, 07:21   #9
99.94
 
99.94's Avatar
 
Dec 2004
The Land of Lost Content

3×7×13 Posts
Default

Quote:
Originally Posted by maxal
What's "no.s." ?
Numbers? (abbreviation).
99.94 is offline   Reply With Quote
Old 2005-04-13, 10:26   #10
mfgoode
Bronze Medalist
 
mfgoode's Avatar
 
Jan 2004
Mumbai,India

22·33·19 Posts
Cool A Counter example anyone?

Quote:
Originally Posted by maxal
Either one. The quoted counterexamples are neither Fermat pseudoprimes, nor Carmichael numbers.
Yes 99.94. This abbr. is widely used in this part of the world.

Thank you once again maxal.
The no.s you have derived evidently satisfy at least one of Devraj's eqn.s ( abbr.-equations).

[Quote] Either one. The quoted counterexamples are neither Fermat pseudoprimes, nor Carmichael numbers.[/UNQUOTE]' maxal.

If you have ruled these two sets out then what category do the numbers 105
,165,195 etc. fall under?
Thank you
Mally
mfgoode is offline   Reply With Quote
Old 2005-04-13, 22:08   #11
maxal
 
maxal's Avatar
 
Feb 2005

3748 Posts
Default

Quote:
Originally Posted by mfgoode
Quote:
Originally Posted by maxal
Either one. The quoted counterexamples are neither Fermat pseudoprimes, nor Carmichael numbers.
If you have ruled these two sets out then what category do the numbers 105
,165,195 etc. fall under?
These numbers are not pseudoprimes (neither "Fermat pseudoprimes", nor "Carmichael numbers") for which at least one of Devaraj's fractions is integer.
(I think I've already said that).

Last fiddled with by maxal on 2005-04-13 at 22:09
maxal is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Cheating at chess how to counter it Brian-E Chess 71 2019-07-15 14:10
Reset the milestone counter: New SoB & PSP was found !! Aillas Prime Sierpinski Project 4 2016-11-08 04:24
Visitor counter Rodrigo Forum Feedback 9 2010-09-14 14:14
"no threads newer" counter cheesehead Forum Feedback 0 2008-09-17 05:14
Counter-examples, please Numbers Miscellaneous Math 4 2005-12-29 11:03

All times are UTC. The time now is 14:50.

Tue Aug 4 14:50:25 UTC 2020 up 18 days, 10:37, 0 users, load averages: 1.27, 1.29, 1.43

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2020, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.