A007535 Smallest pseudoprime ( > n ) to base n: smallest composite number m > n such that n^(m-1)-1 is divisible by m.

4, 341, 91, 15, 124, 35, 25, 9, 28, 33, 15, 65, 21, 15, 341, 51, 45, 25, 45, 21, 55, 69, 33, 25, 28, 27, 65, 45, 35, 49, 49, 33, 85, 35, 51, 91, 45, 39, 95, 91, 105, 205, 77, 45, 76, 133, 65, 49, 66, 51, 65, 85, 65, 55, 63, 57, 65, 133, 87, 341, 91, 63, 341, 65, 112, 91

Offset: 1

Author

N. J. A. Sloane, Mira Bernstein, Robert G. Wilson v

Keywords

• nonn
• nice
• easy

Comments

a(k-1) = k for odd composite numbers k = {9, 15, 21, 25, 27, 33, 35, 39, 45, 49, 51, ...} = A071904(n). - Alexander Adamchuk, Dec 13 2006

References

• A. H. Beiler, Recreations in the Theory of Numbers, Dover, NY, 1964, p. 42 (but beware errors in his table for n = 28, 58, 65, 77, 100).
• N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Links

• T. D. Noe, Table of n, a(n) for n = 1..10000
• G. P. Michon, Pseudoprimes
• Eric Weisstein's World of Mathematics, Fermat's Little Theorem.
• Wikipedia, Pseudoprime
• Index entries for sequences related to pseudoprimes

Crossrefs

Records in A098653 & A098654.

Cf. A071904, A002808.

Programs

Haskell

import Math.NumberTheory.Moduli (powerMod)
a007535 n = head [m | m <- dropWhile (<= n) a002808_list,
                      powerMod n (m - 1) m == 1]
-- Reinhard Zumkeller, Jul 11 2014

Mathematica

f[n_] := Block[{k = n + 1}, While[PrimeQ[k] || PowerMod[n, k - 1, k] != 1, k++ ]; k]; Table[ f[n], {n, 67}] (* Robert G. Wilson v, Sep 18 2004 *)

PARI

a(n)=forcomposite(m=n+1,, if(Mod(n, m)^(m-1)==1, return(m))) \\ Charles R Greathouse IV, May 18 2015

Extensions

Corrected and extended by Patrick De Geest, October 2000