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

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,1

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

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 *)

Prog

(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
(PARI) a(n)=forcomposite(m=n+1, , if(Mod(n, m)^(m-1)==1, return(m))) \\ Charles R Greathouse IV, May 18 2015

Crossrefs

Records in A098653 & A098654.

Cf. A071904, A002808.

Sequence in context: A239293 A295997 A090086 * A000783 A098654 A317058

Adjacent sequences: A007532 A007533 A007534 * A007536 A007537 A007538

Keyword

nonn,nice,easy

Author

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

Extensions

Corrected and extended by Patrick De Geest, October 2000

Status

approved