A309316 Euler primary pretenders: a(n) is the smallest odd composite k such that n^((k+1)/2) == +-n (mod k).

9, 9, 341, 121, 341, 15, 15, 21, 9, 9, 9, 33, 33, 21, 15, 15, 15, 9, 9, 9, 15, 15, 21, 33, 15, 15, 9, 9, 9, 15, 15, 15, 25, 33, 21, 9, 9, 9, 39, 15, 15, 21, 21, 21, 9, 9, 9, 65, 21, 21, 15, 15, 39, 9, 9, 9, 21, 21, 57, 15, 15, 15, 9, 9, 9, 15, 15, 33, 25, 15, 15, 9, 9, 9, 15, 15, 15, 21, 21, 39, 9, 9, 9

Offset: 0

Author

Thomas Ordowski, Jul 23 2019

Keywords

• nonn

Comments

Note that if p is an odd prime, then n^((p+1)/2) == +-n (mod p) for all n.

a(n) is the least Euler weak pseudoprime to base n, as A000790(n) is the least Fermat weak pseudoprime to base n.

This sequence is bounded, namely a(n) <= 1729, the smallest absolute Euler pseudoprime, because n^((1729+1)/2) == n (mod 1729) for every n, see A033181.

The set A = {a(n)} of terms contains all odd semiprimes pq < 1729 such that p-1 | q-1. Other numbers in the set are 561, 645, 1065, 1247, and 1729. Probably complete. Cf. A108574.

This sequence is periodic with a very long period P = LCM(A) = p#*q#/2^2, where p and q are the largest primes such that p^2 < 1729 and 3q < 1729. Such primes are p = 41 and q = 571, so the period P = 41#*571#/4 (248 digits) is much longer than period of the (Fermat) primary pretenders.

Problem: is P the fundamental period of this sequence?

Records of a(n) are 9, 341, 561, 703, 793, 1145, 1263, 1477, and 1729; for n = 0, 2, 383, 1822, 3308, 4702, 10103, 12252, and 21821. - Amiram Eldar, Jul 24 2019

Examples

			a(2) = 341 since 2^((341+1)/2) = 2^171 == 2 (mod 341) and 341 is the smallest odd composite number satisfying this congruence.
a(5) = 15 since 5^((15+1)/2) = 5^8 == -5 (mod 15) and 15 is the smallest odd composite number with this property.
a(8) = 9 since 8^((9+1)/2) = 8^5 == 8 (mod 9) and 9 is the smallest odd composite number.
		

Crossrefs

Cf. A000790, A033181, A108574.

Programs

Maple

f:= proc(n) local k,r;
  for k from 9 by 2 do
    if isprime(k) then next fi;
    r:= n &^ ((k+1)/2) mod k;
    if r = (n mod k) or r = (-n mod k) then return k fi
  od
end proc:
map(f, [$0..100]); # Robert Israel, Jul 23 2019

Mathematica

a[n_] := Module[{k=9}, While[!CompositeQ[k] || ((m = PowerMod[n, (k+1)/2, k]) != Mod[n, k] && m != Mod[-n, k]), k+=2]; k]; Array[a, 100, 0] (* Amiram Eldar, Jul 23 2019 *)

Formula

a(n) = 9 if and only if n == {-1,0,1} (mod 9).

a(n + P) = a(n), where the period P = 41#*571#/4.

Extensions

More terms from Amiram Eldar, Jul 23 2019