A105222 -id:A105222 - cp's OEIS frontend

A185103 Smallest k > 1 such that k^(n-1) == 1 (mod n^2).

5, 8, 17, 7, 37, 18, 65, 80, 101, 3, 145, 19, 197, 26, 257, 38, 325, 28, 401, 197, 485, 28, 577, 182, 677, 728, 177, 14, 901, 115, 1025, 485, 1157, 99, 1297, 18, 1445, 170, 1601, 51, 1765, 19, 1937, 82, 2117, 53, 2305, 1047, 2501, 577, 529, 338, 2917, 1451

Offset: 2

Michel Lagneau, Dec 26 2012

nonn

a(n) <= n^2 + (-1)^n. - Thomas Ordowski, Dec 28 2016
If n = p^k for a prime p > 3 and k > 0, then gcd(n, a(n)^2 - 1) = 1. - Thomas Ordowski, Nov 27 2018
A039678 interleaved with A256517. - Felix Fröhlich, Apr 29 2022

			a(2) = 5 because 2^(2-1) == 2 (mod 2^2), 3^(2-1) == 3 (mod 2^2), 4^(2-1) == 0 (mod 2^2), but 5^(2-1) == 1 (mod 2^2). - _Petros Hadjicostas_, Sep 15 2019

Michel Lagneau and Charles R Greathouse IV, Table of n, a(n) for n = 2..10000 (terms to 500 from Michel Lagneau)
K. Broughan, Relaxations of the ABC Conjecture using integer k'th roots, New Zealand J. Math. 35(2) (2006), 121-136. - _Felix Fröhlich_, Jun 24 2014

Cf. A039678, A105222, A220105, A256517.

with(numtheory):for n from 2 to 100 do:ii:=0:for k from 1 to 10000 while(ii=0) do:x:=k^(n-1)-1:if irem(x,n^2)=0 and k>1 then ii:=1:printf(`%d, `,k):else fi:od:od:

Table[k = 2; While[PowerMod[k, n - 1, n^2] != 1, k++]; k, {n, 2, 100}]

a(n)=my(v=List([1]));for(k=2,n-1,if(Mod(k,n)^(n-1)==1, if(Mod(k,n^2)^(n-1)==1, return(k)); listput(v,k))); v=vector(#v,i, v[i%#v+1]-v[i]); v[#v]+=n;forstep(k=n+1,n^2+1,v,if(Mod(k,n^2)^(n-1)==1, return(k))) \\ Charles R Greathouse IV, Dec 26 2012

a(n) = for(k=2, 200, if(Mod(k, n^2)^(n-1)==1, return(k))) \\ Felix Fröhlich, Apr 29 2022

def a(n):
    k, n2 = 2, n*n
    while pow(k, n-1, n2) != 1: k += 1
    return k
print([a(n) for n in range(2, 56)]) # Michael S. Branicky, Apr 29 2022

from sympy.ntheory.residue_ntheory import nthroot_mod
def A185103(n):
    z = nthroot_mod(1,n-1,n**2,True)
    return int(z[0]+n**2 if len(z) == 1 else z[1]) # Chai Wah Wu, May 18 2022

Definition adjusted by Felix Fröhlich, Jun 24 2014

A242742 Let k be the n-th composite number: then a(n) is the smallest base b such that b^(k-1) == 1 (mod k).

Original entry on oeis.org

5, 7, 9, 8, 11, 13, 15, 4, 17, 19, 21, 8, 23, 25, 7, 27, 26, 9, 31, 33, 10, 35, 6, 37, 39, 14, 41, 43, 45, 8, 47, 49, 18, 51, 16, 9, 55, 21, 57, 20, 59, 61, 63, 8, 65, 8, 25, 69, 22, 11, 73, 75, 26, 45, 34, 79, 81, 80, 83, 85, 4, 87, 28, 89, 91, 3, 93, 32, 95

Offset: 1

Felix Fröhlich, Aug 16 2014

nonn

Felix Fröhlich, Table of n, a(n) for n = 1..8769 (all terms up to k=10^4)

Cf. A002808, A001567, A105222, A181780, A211455, A211456, A211457, A211458.

sbb[n_]:=Module[{b=2},While[PowerMod[b,n-1,n]!=1,b++];b]; sbb/@Select[ Range[ 100],CompositeQ] (* Requires Mathematica version 10 or later *) (* Harvey P. Dale, Dec 29 2018 *)

forcomposite(k=2, 1e2, for(b=2, 1e9, if(Mod(b, k)^(k-1)==1, print1(b, ", "); next({2}))); print1(">1e9, "))

a(n) = A105222(A002808(n)). - Michel Marcus, Aug 21 2014

A239452 Smallest integer m > 1 such that m^n == m (mod n).

Original entry on oeis.org

2, 2, 2, 4, 2, 3, 2, 8, 8, 5, 2, 4, 2, 7, 4, 16, 2, 9, 2, 5, 6, 11, 2, 9, 7, 13, 26, 4, 2, 6, 2, 32, 10, 17, 6, 9, 2, 19, 12, 16, 2, 7, 2, 12, 8, 23, 2, 16, 18, 25, 16, 9, 2, 27, 10, 8, 18, 29, 2, 16, 2, 31, 8, 64, 5, 3, 2, 17, 22, 11, 2, 9, 2, 37, 24, 20, 21

Offset: 1

Robert FERREOL, Mar 19 2014

nonn

Composite n are Fermat weak pseudoprimes to base a(n).
If n > 2 is prime then a(n) = 2. The converse is false : a(341) = 2 and 341 isn't prime.
a(n) <= A105222(n). a(n) = A105222(n) if and only if a(n) is coprime to n.
For n > 1, a(n) <= n and if a(n) = n, then A105222(n) = n+1.
It seems that a(n) = n if and only if n = 2^k with k > 0, a(n) = n-1 if and only if n = 3^k with k > 0, a(2n) = n if and only if n = p^k where p is an odd prime and k > 0. - Thomas Ordowski, Oct 19 2017

			We have 2^4 != 2, 3^4 != 3, but 4^4 == 4 (mod 4), so a(4) = 4.

Giovanni Resta, Table of n, a(n) for n = 1..10000
Gérard P. Michon, Weak pseudoprimes to base a

Cf. A105222.

import Math.NumberTheory.Moduli (powerMod)
a239452 n = head [m | m <- [2..], powerMod m n n == mod m n]
-- Reinhard Zumkeller, Mar 19 2014

L:=NULL:for n to 100 do for a from 2 while a^n - a mod n !=0 do od; L:=L,a od: L;

a[n_] := Block[{m = 2}, While[PowerMod[m, n, n] != Mod[m, n], m++]; m]; Array[a, 100] (* Giovanni Resta, Mar 19 2014 *)

a(n)=my(m=2); while(Mod(m,n)^n!=m, m++); m \\ Charles R Greathouse IV, Mar 21 2014

L=[];
for n in range(1,101):
   a=2
   while (a**n - a) % n != 0:
      a+=1
   L=L+[a]
L

a(20)-a(77) from Giovanni Resta, Mar 19 2014

A345675 Numbers m such that D_{m-1} is the smallest base b > 1 for which b^{m-1} == 1 (mod m), where D_k is the denominator (A027642) of Bernoulli number B_k.

Original entry on oeis.org

35, 14315, 22399, 35711, 455891, 881809, 1198159, 1917071, 2287987, 3310037, 4464941, 11029439, 12190061, 13325753, 17832803, 33012941, 33296147, 37814849, 44986423, 74437181, 76911149, 82873661, 91909571, 98859851, 108266171, 128008159, 128981243, 132391409

Offset: 1

Thomas Ordowski, Sep 04 2021

nonn

These are numbers m such that A027642(m-1) = A105222(m).

The corresponding bases of these pseudoprimes are 6, 6, 42, 66, 66, 46410, 3318, 66, 42, 30, 330, 6, 330, 61410, 6, 330, 1074, 510, 3318, 330, 7890, 330, 66, 12606, 66, 42, 6, 510, ...

Cf. A027642, A105222, A121707, A316940.

Den[n_] := Times @@ (1 + Select[Divisors[n], PrimeQ[# + 1] &]); q[k_] := Module[{m = 2, d = Den[k - 1]}, If[PowerMod[d, k - 1, k] != 1, False, While[m < d && PowerMod[m, k - 1, k] != 1, m++]; m == d]]; Select[Range[3, 10^6, 2], q] (* Amiram Eldar, Sep 04 2021 *)

f(n) = my(m=2); while(Mod(m, n)^(n-1)!=1, m++); m;
isok(m) = f(m) == denominator(bernfrac(m-1)); \\ Michel Marcus, Sep 04 2021

More terms from Amiram Eldar, Sep 04 2021

cp's OEIS Frontend

A185103 Smallest k > 1 such that k^(n-1) == 1 (mod n^2).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

PARI

Python

Python

Extensions

A242742 Let k be the n-th composite number: then a(n) is the smallest base b such that b^(k-1) == 1 (mod k).

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A239452 Smallest integer m > 1 such that m^n == m (mod n).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Haskell

Maple

Mathematica

PARI

Python

Extensions

A345675 Numbers m such that D_{m-1} is the smallest base b > 1 for which b^{m-1} == 1 (mod m), where D_k is the denominator (A027642) of Bernoulli number B_k.

Views

Author

Keywords

Comments

Crossrefs

Programs

Mathematica

PARI

Extensions