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

Author

Alonso del Arte, Oct 23 2013

Keywords

• nonn
• easy

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.

Examples

			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.
		

Links

• 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).

Crossrefs

Cf. A206786.

Programs

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

PARI

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

Formula

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