A230579 a(n) = 2^n mod 341.

1, 2, 4, 8, 16, 32, 64, 128, 256, 171, 1, 2, 4, 8, 16, 32, 64, 128, 256, 171, 1, 2, 4, 8, 16, 32, 64, 128, 256, 171, 1, 2, 4, 8, 16, 32, 64, 128, 256, 171, 1, 2, 4, 8, 16, 32, 64, 128, 256, 171, 1, 2, 4, 8, 16, 32, 64, 128, 256, 171, 1, 2, 4, 8, 16, 32, 64, 128, 256, 171

Offset

0,2

Comments

Jeans asserts that it would have been impossible for the ancient Chinese to have discovered a case of failure for the converse of Fermat's little theorem because the smallest counterexample "(n = 341) consists of 103 figures" in base 10.

Granted that without a computer, the task of calculating 2^340 - 1 and dividing by 341 is tedious and error-prone, thus discouraging the discovery of that number as a counterexample to the so-called Chinese hypothesis.

But by instead computing just a few dozen powers of 2 modulo 341, it becomes readily apparent that the sequence of powers of 2 modulo 341 has a period of length 10 and therefore 2^340 = 1 mod 341, yet 341 = 11 * 31, which is not a prime number.

Links

Table of n, a(n) for n=0..69.

L. Halbeisen and N. Hungerbühler, On generalised Carmichael numbers, Hardy-Ramanujan Society, 1999, 22 (2), pp. 8-22. (hal-01109575). See p. 8.

J. H. Jeans, The converse of Fermat's theorem, Messenger of Mathematics 27 (1898), p. 174.

Index entries for linear recurrences with constant coefficients, signature (1,-1,1,-1,1,-1,1,-1,1).

Formula

a(0) = 1, a(n) = 2*a(n-1) mod 341.

Example

a(8) = 256 because 2^8 = 256.
a(9) = 171 because 2^9 = 512 and 512 - 341 = 171.
a(10) = 1 because 2 * 171 = 342 and 342 - 341 = 1.

Mathematica

PowerMod[2, Range[0, 79], 341]
LinearRecurrence[{1, -1, 1, -1, 1, -1, 1, -1, 1}, {1, 2, 4, 8, 16, 32, 64, 128, 256}, 70] (* Ray Chandler, Jul 12 2015 *)

Prog

(PARI) a(n)=lift(Mod(2, 341)^n) \\ Charles R Greathouse IV, Mar 22 2016

Crossrefs

Cf. A206786.

Sequence in context: A243086 A087079 A252757 * A361937 A009694 A275816

Adjacent sequences: A230576 A230577 A230578 * A230580 A230581 A230582

Keyword

nonn,easy

Author

Alonso del Arte, Oct 23 2013

Status

approved