mersenneforum.org > Math A Counter example, anyone?
 Register FAQ Search Today's Posts Mark Forums Read

 2005-04-11, 06:30 #1 devarajkandadai     May 2004 22×79 Posts 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
 2005-04-11, 08:54 #2 Dougy     Aug 2004 Melbourne, Australia 100110002 Posts 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)
2005-04-12, 02:32   #3

May 2004

13C16 Posts

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

2005-04-12, 23:34   #4
maxal

Feb 2005

22×32×7 Posts

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

2005-04-13, 03:52   #5
mfgoode
Bronze Medalist

Jan 2004
Mumbai,India

22·33·19 Posts

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

2005-04-13, 03:59   #6
maxal

Feb 2005

22·32·7 Posts

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.

2005-04-13, 04:28   #7
mfgoode
Bronze Medalist

Jan 2004
Mumbai,India

205210 Posts
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

2005-04-13, 04:55   #8
maxal

Feb 2005

25210 Posts

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." ?

2005-04-13, 07:21   #9
99.94

Dec 2004
The Land of Lost Content

3·7·13 Posts

Quote:
 Originally Posted by maxal What's "no.s." ?
Numbers? (abbreviation).

2005-04-13, 10:26   #10
mfgoode
Bronze Medalist

Jan 2004
Mumbai,India

40048 Posts
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

2005-04-13, 22:08   #11
maxal

Feb 2005

FC16 Posts

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

 Similar Threads Thread Thread Starter Forum Replies Last Post Brian-E Chess 71 2019-07-15 14:10 Aillas Prime Sierpinski Project 4 2016-11-08 04:24 Rodrigo Forum Feedback 9 2010-09-14 14:14 cheesehead Forum Feedback 0 2008-09-17 05:14 Numbers Miscellaneous Math 4 2005-12-29 11:03

All times are UTC. The time now is 01:22.

Sat Dec 4 01:22:57 UTC 2021 up 133 days, 19:51, 0 users, load averages: 1.22, 1.43, 1.40