Talk:Fermat pseudoprime

Old comments

Rasta, I would really appreciate it if you didn't cause me more work than necessary. Do I really have to justify every edit on Talk so that you don't revert it? Ok, here we go:

This table

Fermat's little theorem gives us for the first numbers:

n	an-1-1	an-1 -1 mod n
1	0	0
2	1	1
3	3	0
4	7	3
5	15	0
6	31	1
7	63	0
8	127	7
9	255	3
10	511	1
11	1023	0
12	2047	7
13	4095	0
14	8191	1
15	16383	3
16	32767	15
17	65535	0
18	131071	13
19	262143	0
20	524287	7
21	1048575	3
22	2097151	1
23	4194303	0
24	8388607	7
25	16777215	15
26	33554431	1
27	67108863	12
28	134217727	7
29	268435455	0
30	536870911	1
31	1073741823	0
32	2147483647	31
33	4294967295	3

is completely unintelligible. You don't say what a is; apparently you use a = 2. Furthermore, Fermat's little theorem says that the third column should always be 1, so obviously it wasn't used, contrary to the claim.

I removed the | symbol for division because the rest of the article uses "divides".

I removed the Moebius function values since they don't provide any insight here. What point to you want to prove by including them. Sure it is an arithmetical function, but there are dozens of other arithmetical functions, why didn't you add information about σ(n) and φ(n)? It is pointless; there is no connection that needs to be mentioned. Furthermore, anyone interested in the moebius function can easily find the value, since all they have to do is to count the prime factors, which are already given in the table. In the final paragraph, formulating the (false) conjecture in terms of prime factors makes it much easier to read to the non-specialist.

I removed the link to the super-Poulet integer sequence entry because it belongs on the article about super-Poulet numbers, not here.

I also removed "We do not calculate numbers 2^n-1. " because I have no idea what it means. AxelBoldt 16:04 Sep 25, 2002 (UTC)

(1) I really do not want to cause anyone more work than necessary. But I can't help if someone try to suit every single article to his own fashion. You just throw out everything that does not fit to your personal view. Try to edit articles more for the reader and not for yourself. What is wrong if one sentence is not quite adequate and explicit. On the other hand I am doing my best to compose one article from the scratch and then you come and you 'ruin' almost my whole work. Who is doing fruitless work here? You're obviously to deep in the math and you can't see out anymore. Try to read one original work from an original mathematician, please. If you would have a chance, you would probably change even Gauss' work. Remember on what he had written about the estimation of the number of primes and such.

(2) I'll try to fix the table, that bothers you so much. (Just give me some time).

(3) Don't call me Rasta if you're not shure what that means or if you think I am that, if I bear similar cyber nickname, and so on :)

(4) The symbol |. Sometimes you like and sometimes you don't. For instance it is more clear if we write, once we have agreed what | means, 3 | 9, than 3 divides 9. You have once said that any symbol in fact does not have much sence in math so here we go...

(5) What is wrong with Möbius function here or elsewhere. When I make a table, it is clear after that what values are, but try to 'calculate' its values from your mind. I gave the function to depict further on the whole subject. It is pointless; there is no connection that needs to be mentioned. That is you opinion, I guess. Everything is important in math, specially in a number theory. If I wouldn't use Möbius function I wouln't be able to find those two numbers 648 and 700. I guess here μ(n) is 'more' important than other arithmetic functions. That's my opinion. Furthermore, anyone interested in the moebius function can easily find the value, since all they have to do is to count the prime factors, which are already given in the table. Yes, that is true. But many readers do not know at first what μ(n) means and shows. Simply as that.

(6) I am not your student out there somewhere so we have to work for this project. You correct me and I correct you if and only if I can. I am pretty tired of writting articles which envolve math, but I like math very much. And because you know something from the math, you can give your knowledge to others and not just fixing things all around as it is going for one math test. My teachers are mathematicians themselves. Only you change these articles so much, no one else. So I can't figure that they do not understand what is written in them. Egziabeher. --XJam 17:20 Sep 25, 2002 (UTC)

Rasta-kun:

1) Your table header had an error. You wrote this: a^n-1 mod n instead of this: a^n-1-1 mod n. I fixed it.

Thank you. Yo ad ustay an neh ah ukob.

2) Why not write "9 mod 3 = 0" for "3 divides 9"?

Or 9/3=3+0:) --Nuk-ta-fire-sar [2002-09-25] 2T.

--User:Juuitchan

Try to edit articles more for the reader and not for yourself. What is wrong if one sentence is not quite adequate and explicit.

I edit for the reader, and unclear sentences are therefore changed/removed.

The symbol |. Sometimes you like and sometimes you don't.

If you tell the reader what it means, you can use it. But this article uses "divides" throughout, so it doesn't make sense to start using | all of a sudden in the middle of the article, without explanation.

It is pointless; there is no connection that needs to be mentioned. That is you opinion, I guess.

Indeed. And unless you can point me to some interesting connection, some theorem or even conjecture involving pseudoprimes and μ, there is no point in mentioning the μ function here.

But many readers do not know at first what μ(n) means and shows.

Right, and they don't need to know it, since it doesn't have anything to do with the topic at hand. AxelBoldt 18:20 Sep 25, 2002 (UTC)

---

Where does the table with the smallest pseudo primes come from? AxelBoldt 22:52 Sep 25, 2002 (UTC)

The table is entirely my calculation, so do not worry. It took me nearly 3 hours to calculate. The previous one I gave was slightly wrong as probably you have observed. You can throw it away if you don't like it - as you wish :) or as you wrote that "intellectual property rights" does not exist. This is my opinion too. -- XJam 01:07 Sep 26, 2002 (UTC)

How could a person own the rights to mathematical equalities? User:Juuitchan

Most probably he can't. -- XJam

Do you use Maple or Mathematica or some such program? AxelBoldt 01:15 Sep 26, 2002 (UTC)

Strictly Maple (V Release 4.00a). I've made all functions by myself for that particular table, so we can see how Maple is strong. And my knowledge of programming is somewhere in the middle. I have tryed other programmes, but I like Maple the most. --XJam 02:23 Sep 26, 2002 (UTC)

---

I think the bold terms all need to appear in the first few lines. I arrived here expecting Poulet numbers and was completely befuddled until the fifth paragraph. --Omphaloscope 19:14, 8 Apr 2005 (UTC)

Proposed reorganization

I'd like to see a separate article on Fermat pseudoprimes (and its close friends). I think pseudoprime should mainly define the general concept and link to the many types of pseudoprimes, almost like a disambiguation page. I'll make this change if there's no objection. Deco 01:07, 9 Apr 2005 (UTC)

First: I am User from the german Wikipedia. I would like to concentrate the Fermat Pseudoprimes to the Euler Pseudorimes, because the important Fermat Pseudoprimes like Poulet Numbers, Cipolla Pseudoprimes, Carmichael Numbers, Zeisel Numbers, (6n+1)*(12n+1), ... are Euler Pseudoprimes. The rest, like 15, 35, 52, 66, 70, 85, 87, ... are less to unimportant. --Arbol01 01:38, 11 Apr 2005 (UTC)

How are they named?

How is a number of the Form $a^{2(n-1)}\equiv 1\mod n$ for every $\operatorname {gcd} (a,n)=1$ named?

And how is a number of the Form $a^{2^{m}(n-1)}\equiv 1\mod n$ for every $\operatorname {gcd} (a,n)=1$ named? --Arbol01 11:42, 30 July 2005 (UTC)

Reverted back

I re-reverted to the version produced by 71.241.234.207 because in my opinion this version is more accurate than the version proposed by User:EJ. -- Bob.v.R 14:11, 17 April 2006 (UTC)

Table of smallest p-p

In the Table of smallest p-p are some mistakes:

The number 9 is no pseudoprime to base 8 neither to any other base. Anti-Proof: Every natural number q is (q-1) a base so that $(q-1)^{q}\equiv 1\mod q$ => Every natural Number is a fermat pseudoprime. In fact there ar many natural numbers, which are neither a fermat pseudoprime, nor a prime number like 4, 6, 8, 9, 10, .. .

What i wrote for 9 is sesame for every exponation of 3. 9, 27, 81, 243, ... are all no pseudoprimes.

The smallest pseudoprime to base 19 is 15, because 15 is pseudoprime to base (15*n+4) and (15*n+11) which are the bases: 4, 11, 19, 26, 34, 41, 49, 56, ...

15 is not a fermat pseudoprime to base 14. The smallest fermat pseudoprime to base 14 is 65

The smallest pseudoprime to base 20 is not 21 - it is 57.

The smallest pseudoprime to base 24 is not 25 - it is 115.

The smallest pseudoprime to base 26 is not 27 - it is 15.

The smallest pseudoprime to base 29 is not 35 - it is 21.

The smallest pseudoprime to base 32 is not 33 - it is 25.

and so on ... --Arbol01 (talk) 22:17, 7 December 2009 (UTC)

There are different definitions of Fermat pseudoprimes. The article uses a common definition which allows x to be a pseudoprime in base x-1. For other sites doing that, see for example http://primes.utm.edu/glossary/xpage/PRP.html and oeis:A020137 where 9 is a base 8 pseudoprime. With our definition, x is a base x-1 pseudoprime if and only if x is an odd composite. However, our article had an inconsistency in another area. The table of smallest pseudoprimes only includes numbers above the base while the definition does not make that restriction. I have edited the article.[1] PrimeHunter (talk) 02:56, 8 December 2009 (UTC)

I think, i will add the passage over the more strict definition of fermat pseudoprime after Pomerance and Crandall (Prime Numbers - "A Computational Perspective", Springer, ISBN 0-387-25282-7, page 132, theorem 3.4.2) in the article insert. --95.116.82.175 (talk) 09:53, 8 December 2009 (UTC)

Inconsistency

The article says:

Every odd number q satisfies $a^{q-1}\equiv 1{\pmod {q}}$ for $a=q-1$. This trivial case is excluded in the definition of a Fermat pseudoprime given by Crandall and Pomerance:

A composite number q is a Fermat pseudoprime to a base a, if $a^{q-1}\equiv 1{\pmod {q}}$ and $2\leq a\leq q-2.$

This stronger definition excludes every power of three (9, 27, 81, 243, ...), and many even integers from the base-2 Fermat pseudoprimes.

As far as I can see, this does not make any sense. The Crandall and Pomerance extra condition for a = 2 only says that 2 ≤ q − 2, i.e., q ≥ 4. Thus, the only integer excluded from being a base-2 Fermat pseudoprime is 3.—Emil J. 12:57, 9 October 2012 (UTC)

3 is a prime

Therefore the affirmation "This stronger definition excludes 3 from being a base-2 Fermat pseudoprime" at the end of the "Variations" paragraph, should be removed or rephrased. It does not bring any info, and 3 can't be a "pseudo"-prime anyway, as it is a prime. — Preceding unsigned comment added by LaurV (talk • contribs) 08:35, 29 May 2013 (UTC)

Ah, yes. I tend to think about pseudoprimes in terms of probable primes, I sometimes forget about the uncanny exception excluding true primes from the definition.—Emil J. 12:25, 29 May 2013 (UTC)

The condition of Crandall and pomerance exclude numbers like 4, 6, 8, 9, 10, 12, 14, 16, 18, ... from the fermat pseudoprimes. The first two primes, 2 and 3 are the exception of the primes. Every prime greater 3 fullfill the condition of Crandall and Pomerance. The condition of Crandall and Pomerance just exclude the bases '1' and 'n-1', because '1' and 'n-1' are no property of a fermat pseudoprime.

--2001:9E8:215E:8D00:7106:EA27:EE3B:9A5A (talk) 15:54, 8 April 2022 (UTC)

Is 1 a Fermat pseudoprime?

Is 1 a Fermat pseudoprime? b^0 = 1(mod 1) is always true!

Weak vs. Fermat

I was reading the article and I got confused. It says that "A composite number n which satisfy that 'b^n = b' is called weak pseudoprime to base b. However, this is also the definition given for the Fermat pseudoprime. Are the terms synonymous? Any help is appreciated. Thank you. — Preceding unsigned comment added by 108.53.226.245 (talk) 01:53, 27 August 2016 (UTC)

You are right in raising this issue. The section "Weak pseudoprimes" should really be checked and straightened out. Bob.v.R (talk) 03:14, 22 June 2019 (UTC)

Fermat primality test

The section "Fermat primality test" needs some work. One problem with it is, there is no need to pick a number b such that the Jacobi symbol (b/n) is -1. In practice, math libraries simply choose a fixed base like b = 2 and do a Strong pseudoprime test on it. (Or, they use the Miller–Rabin primality test, which is a strong test to several bases). A strong test base 2, in conjunction with a Lucas pseudoprime test, distinguishes all primes from composites up to at least 2^64.

Second, the method for choosing P and Q for a Lucas test is unusual and seems ad-hoc. I have not seen it in any code. There are reasons to use more standard methods, like the one on the Lucas pseudoprime page. The Lucas test also has nothing to do with the Fermat primality test. Lucas tests are already described in detail on the Lucas pseudoprime page, so I would recommend simply removing it from here. At the very least, change the method for choosing P and Q to a more standard method. MathPerson (talk) 00:04, 25 May 2019 (UTC)

Upon further reflection, I think this entire section should be deleted, for these reasons: (1) This section completely confuses the Fermat test with the Euler pseudoprime test; the Jacobi symbol has nothing whatever to do with the Fermat test. (2) Almost all of this section is taken up discussing other types of tests, like Euler and Lucas tests, which already have their own Wikipedia articles. (3) There is already an entire Wikipedia article with this same title as this section, Fermat primality test, and which is already referred to at the beginning of this article. Discussion? Objections? MathPerson (talk) 01:47, 22 June 2019 (UTC)

Maybe the title of that section could better be "Fermat primality test compared to other tests". And then still it could be considered for being moved towards the article Fermat primality test that you mentioned. Bob.v.R (talk) 03:02, 22 June 2019 (UTC)

OK, but then somebody would have to completely rewrite this section. Because other types of pseudoprimes already have their own Wikipedia pages, I think it would make more sense to just list them and be done with it. But if somebody wants to rewrite that section, please do! MathPerson (talk) 18:26, 27 June 2019 (UTC)

Almost everything in this section is just not true. After 6 months since the last comment here, I don't see anyone stepping up to fix all the errors. Therefore, I plan in the near future to delete this entire section, unless somebody completely rewrites it. An encyclopedia emphatically should not have falsehoods and misinformation like this section has. MathPerson (talk) 00:01, 6 February 2020 (UTC)

Done. MathPerson (talk) 20:18, 6 March 2020 (UTC)

Which bases b make n a Fermat pseudoprime?

The table is wrong! For a fermat pseudoprime 'n' are 1 and 'n-1' no bases. A number 'n' with just 1 and 'n-1' as bases is no fermat pseudoprime! The numbers 4, 6, 8, 9, 27 are no fermat pseudoprime, because for every natural numbers greater 1 are 1 and or 'n-1' bases. Just numbers 'n' who have bases between '2' and 'n-2' are fermat pseudoprimes. The smallest fermat pseudoprime is 15 with the bases '4' and '11'.

OEIS: A181780 OEIS: A111305 R. Crandall and C. Pomerance, Prime Numbers: A Computational Perspective, New York: Springer-Verlag (2001): p. 121.

If 'n' is a fermat pseudoprime for the bases 'a' and 'n-a', for which a + (n-a) = n, than are all 'b*n+a' and 'b*n+(n-a)' bases to 'n'. For example: The bases for 15 are 4, 11, 19, 26, 34, 41, ... , b*15+4, b*15+11

--2001:9E8:215E:8D00:7106:EA27:EE3B:9A5A (talk) 00:49, 8 April 2022 (UTC)