A Counter example, anyone?

[devarajkandadai]

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

Dear Maxal, I think 105 is pseudo to the base 29.I will check the other two .Regards,
A.K. Devaraj

[maxal]

Originally Posted by devarajkandadai

Dear Maxal, I think 105 is pseudo to the base 29.I will check the other two .

What definition of the pseudoprime do you use?
Note that every odd number is pseudoprime to some base. And there is no much sense to call a number pseudoprime just because there exists a base to which it is pseudoprime. Following this way, every odd number should be called pseudoprime.

Usually the base is fixed (e.g., base=2), then we deal with Fermat pseudoprimes. Alternatively, it can be required that a given number is pseudoprime to every possible base, then we deal with Carmichael numbers.

[devarajkandadai]

Originally Posted by devarajkandadai

Dear Maxal, I think 105 is pseudo to the base 29.I will check the other two .Regards,
A.K. Devaraj

To continue, 165 is pseudo to the base 109 & 195 is pseudo to the base 79.
Regards,
A.K. Devaraj

[maxal]

Originally Posted by devarajkandadai

To continue, 165 is pseudo to the base 109 & 195 is pseudo to the base 79.

What's the point? As I said before, every odd number is pseudoprime to some base.

If you want a counterexample of this flavor, here it comes:
357 = 3*7*17
For this number, neither of your fractions is integer. But 357 is pseudoprime to the base 13.

[mfgoode]

Originally Posted by maxal

What's the point? As I said before, every odd number is pseudoprime to some base.

If you want a counterexample of this flavor, here it comes:
357 = 3*7*17
For this number, neither of your fractions is integer. But 357 is pseudoprime to the base 13.

:surprised
Excellent maxal!
I have checked the websites you have given of Math World and thanks for the same.
However they dont give many examples of pseudo primes.
Could you please direct me to a site which gives Both Fermat pseudo primes and Carmichael numbers separatey? Or give me some of your own that you have tested out?
Math world gives 2 as an even Fermat pseudo prime. Could this be psp(3) ?
Thank you.
Mally

[maxal]

Originally Posted by mfgoode

However they dont give many examples of pseudo primes.
Could you please direct me to a site which gives Both Fermat pseudo primes and Carmichael numbers separatey?

MathWorld provides links to OEIS. For example: sequence of psp(2)'s and Carmichael numbers.

Originally Posted by mfgoode

Math world gives 2 as an even Fermat pseudo prime. Could this be psp(3) ?

Any prime is always a pseudoprime (to any base). In particular, 2 is psp(3) (as well as psp(4), psp(5) etc.).

[R.D. Silverman]

Originally Posted by maxal

MathWorld provides links to OEIS. For example: sequence of psp(2)'s and Carmichael numbers.
Any prime is always a pseudoprime (to any base). In particular, 2 is psp(3) (as well as psp(4), psp(5) etc.).

NO! NO! NO!

Here are the standard definitions.

A number N is a probable prime if, for some a != 0, 1 mod N and (a,N) = 1,
then a^(N-1) = 1 mod N

A number N is a pseudoprime if it is a probable prime and it is composite.

Primes are not pseudoprimes.

I also suggest to the poster that he do the arithmetic to see if 2 is a probable
prime to the base 4. (It isn't) 4^(2-1) = 0 mod 2.

Please people. If you don't understand a particular subject, then please
refrain from making pronouncements.

[maxal]

Originally Posted by R.D. Silverman

NO! NO! NO!

Here are the standard definitions.

A number N is a probable prime if, for some a != 0, 1 mod N and (a,N) = 1,
then a^(N-1) = 1 mod N

A number N is a pseudoprime if it is a probable prime and it is composite.

Primes are not pseudoprimes.

This is just one of the possible definitions. For example, PARI consider primes being pseudoprimes http://pari.math.u-bordeaux.fr/docht...#ispseudoprime

Originally Posted by R.D. Silverman

Please people. If you don't understand a particular subject, then please
refrain from making pronouncements.

And I suggest to refrain from mentor's tone.

[R.D. Silverman]

Originally Posted by maxal

This is just one of the possible definitions. For example, PARI consider primes being pseudoprimes http://pari.math.u-bordeaux.fr/docht...#ispseudoprime


And I suggest to refrain from mentor's tone.

No. It is NOT a possible definition according to the many people who
work in this area [Pomerance, Selfridge, Wagstaff, Lenstra] etc. The agreed
definition is that a pseudoprime is a 'composite that appears to be prime'.


I will refrain from the mentor's tone when people stop posting misinformation.

[maxal]

Originally Posted by R.D. Silverman

I also suggest to the poster that he do the arithmetic to see if 2 is a probable
prime to the base 4. (It isn't) 4^(2-1) = 0 mod 2.

I implicitly assumed that the base is always less than the number being tested (there is no point to consider larger bases). And for prime n, any positive integer less than n is co-prime to n.

[maxal]

Originally Posted by R.D. Silverman

No. It is NOT a possible definition according to the many people who
work in this area [Pomerance, Selfridge, Wagstaff, Lenstra] etc. The agreed
definition is that a pseudoprime is a 'composite that appears to be prime'.

Good for them. But there still exist other definitions.
This whole tread is an illustation to what may happen if people use different definitions for the same terms.