A181782 -id:A181782 - cp's OEIS frontend

A322120 a(n) is the smallest composite k such that n^(k-1) == 1 (mod (n^2-1)*k).

341, 91, 91, 217, 481, 25, 65, 91, 91, 133, 133, 85, 781, 341, 91, 91, 25, 49, 671, 221, 169, 91, 553, 217, 133, 121, 361, 341, 49, 49, 25, 545, 703, 341, 403, 217, 85, 341, 121, 671, 529, 25, 703, 133, 133, 65, 481, 247, 793, 451, 671, 703, 361, 697, 403, 25

Offset: 2

Thomas Ordowski, Nov 27 2018

nonn

a(n) >= A271801(n). All terms are odd and indivisible by 3.

Conjecture: if m is a composite number such that b^(m-1) == 1 (mod (b^2-1)m) for some b, then m is a strong pseudoprime to some base a in the range 2 <= a <= m-2. Thus, probably every term a(n) is in A181782.

Cf. A181782, A271801, A298756, A322121.

a[n_] := Module[{k=4}, While[PrimeQ[k] || !Divisible[n^(k-1)-1, (n^2-1)k], k++]; k]; Array[a, 100, 2] (* Amiram Eldar, Nov 27 2018 *)

a(n) = {forcomposite(k=1, ,if (Mod(n, (n^2-1)*k)^(k-1) == 1, return (k)););} \\ Michel Marcus, Nov 28 2018

More terms from Amiram Eldar, Nov 27 2018

A322121 Composite numbers m such that b^(m-1) == 1 (mod (b^2-1)*m) has a solution b.

Original entry on oeis.org

25, 49, 65, 85, 91, 121, 125, 133, 145, 169, 185, 205, 217, 221, 247, 259, 265, 289, 301, 305, 325, 341, 343, 361, 365, 377, 403, 425, 427, 445, 451, 469, 481, 485, 493, 505, 511, 529, 533, 545, 553, 559, 565, 589, 625, 629, 637, 671, 679, 685, 689, 697, 703

Offset: 1

Thomas Ordowski, Nov 27 2018

nonn

The smallest solutions b are 7, 18, 8, 13, 3, 3, 57, 11, ...
These numbers m are odd and indivisible by 3.
They contain all prime powers p^k for p > 3 and k > 1.
It seems that, for a fixed integer k > 0, these are composite numbers m such that c^(m-1) == 1 (mod (c^2-1)m^k) for some base c.
Conjecture: If m is a composite number such that b^(m-1) == 1 (mod (b^2-1)m) for some base b, then m is a strong pseudoprime to some base a in the range 2 <= a <= m-2. Thus, these numbers m are probably a proper subset of A181782.

Cf. A181782, A322120.

aQ[n_] := CompositeQ[n] && LengthWhile[Range[2,n], !Divisible[#^(n-1)-1, (#^2-1) n] &] != n-1; Select[Range[1000],aQ] (* Amiram Eldar, Nov 27 2018 *)

More terms from Amiram Eldar, Nov 27 2018

A329759 Odd composite numbers k for which the number of witnesses for strong pseudoprimality of k equals phi(k)/4, where phi is the Euler totient function (A000010).

Original entry on oeis.org

15, 91, 703, 1891, 8911, 12403, 38503, 79003, 88831, 146611, 188191, 218791, 269011, 286903, 385003, 497503, 597871, 736291, 765703, 954271, 1024651, 1056331, 1152271, 1314631, 1869211, 2741311, 3270403, 3913003, 4255903, 4686391, 5292631, 5481451, 6186403, 6969511

Offset: 1

Amiram Eldar, Nov 20 2019

nonn

Odd numbers k such that A071294((k-1)/2) = A000010(k)/4.
For each odd composite number m > 9 the number of witnesses <= phi(m)/4. For numbers in this sequence the ratio reaches the maximal possible value 1/4.
The semiprime terms of this sequence are of the form (2*m+1)*(4*m+1) where 2*m+1 and 4*m+1 are primes and m is odd.

			15 is in the sequence since out of the phi(15) = 8 numbers 1 <= b < 15 that are coprime to 15, i.e., b = 1, 2, 4, 7, 8, 11, 13, and 14, 8/4 = 2 are witnesses for the strong pseudoprimality of 15: 1 and 14.

Richard Crandall and Carl Pomerance, Prime Numbers: A Computational Perspective, 2nd ed., Springer, 2005, Theorem 3.5.4., p. 136.

Amiram Eldar, Table of n, a(n) for n = 1..350
Louis Monier, Evaluation and comparison of two efficient primality testing algorithms, Theoretical Computer Science, Vol. 11 (1980), pp. 97-108.

Cf. A000010, A033181, A006945, A014233, A071294, A141768, A181782, A195328, A329468.

Cf. A001262, A020229, A020231, A020233.

o[n_] := (n - 1)/2^IntegerExponent[n - 1, 2];
a[n_?PrimeQ] := n - 1; a[n_] := Module[{p = FactorInteger[n][[;; , 1]]}, om = Length[p]; Product[GCD[o[n], o[p[[k]]]], {k, 1, om}] * (1 + (2^(om * Min[IntegerExponent[#, 2] & /@ (p - 1)]) - 1)/(2^om - 1))];
aQ[n_] := CompositeQ[n] && a[n] == EulerPhi[n]/4; s = Select[Range[3, 10^5, 2], aQ]

cp's OEIS Frontend

A322120 a(n) is the smallest composite k such that n^(k-1) == 1 (mod (n^2-1)*k).

Views

Author

Keywords

Comments

Crossrefs

Programs

Mathematica

PARI

Extensions

A322121 Composite numbers m such that b^(m-1) == 1 (mod (b^2-1)*m) has a solution b.

Views

Author

Keywords

Comments

Crossrefs

Programs

Mathematica

Extensions

A329759 Odd composite numbers k for which the number of witnesses for strong pseudoprimality of k equals phi(k)/4, where phi is the Euler totient function (A000010).

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Mathematica