A173138 -id:A173138 - cp's OEIS frontend

A173572 Odd integers n such that 2^n == 4 (mod n).

1, 20737, 93527, 228727, 373457, 540857, 2231327, 11232137, 15088847, 15235703, 24601943, 43092527, 49891487, 66171767, 71429177, 137134727, 207426737, 209402327, 269165561, 302357057, 383696711, 513013327

Offset: 1

Michel Lagneau, Feb 22 2010

nonn

The odd terms of A015921.
Also, nonprime integers n such that 2^(n-2) == 1 (mod n).
For all m, 2^A050259(m)-1 belongs to this sequence.
If n > 1 is a term and p is a primitive prime factor of 2^(n-2)-1, then n*p is also a term. Hence, the sequence is infinite. (Rotkiewicz 1984)

A. E. Bojarincev, Asymptotic expressions for the n-th composite number, Univ. Mat. Zap. 6:21-43 (1967). (in Russian)
R. K. Guy, Unsolved Problems in Number Theory, Springer-Verlag, Third Edition, 2004
G. H. Hardy and E. M. Wright, An Introduction to the Theory of Numbers. 3rd ed., Oxford Univ. Press, 1954, p. 2.

Max Alekseyev, Table of n, a(n) for n = 1..722 (all terms below 10^14)
C. K. Caldwell, Composite Numbers
A. Rotkiewicz, On the congruence 2^(n-2) == 1 (mod n). Math. Comp. 43 (1984), 271-272.

Cf. A015921, A050259, A173138, A002808.

with(numtheory): for n from 1 to 100000000 do: a:= 2^(n-2)- 1; b:= a / n; c:= floor(b): if b = c and tau(n) <> 2 then print (n); else fi;od:

m = 4; Join[Select[Range[1, m, 2], Divisible[2^# - m, #] &], Select[Range[m + 1, 10^6, 2], PowerMod[2, #, #] == m &]] (* Robert Price, Oct 12 2018 *)

is(n) = n%2==1 && Mod(2,n)^n==Mod(4,n) \\ Jinyuan Wang, Feb 22 2019

Edited and term 1 prepended by Max Alekseyev, Aug 09 2012

A033984 Odd integers n such that 2^n == 16 (mod n).

Original entry on oeis.org

1, 7, 40369, 673663, 990409, 1697609, 2073127, 6462649, 7527199, 7559479, 14421169, 21484129, 37825753, 57233047, 130647919, 141735559, 179203369, 188967289, 218206489, 259195009, 264538057, 277628449, 330662479, 398321239, 501126487

Offset: 1

Joe K. Crump (joecr(AT)carolina.rr.com)

nonn

The odd terms of A015924.

For all m, 2^A128121(m)-1 belongs to this sequence.

Max Alekseyev, Table of n, a(n) for n = 1..790 (all terms below 10^14)

Besides initial terms, the sequence coincides with A173138.

Cf. A015924, A173138, A173572.

Select[Range[1,510000001,2],PowerMod[2,#,#]==16&] (* Harvey P. Dale, Dec 11 2010 *)

Edited and terms 1,7 prepended by Max Alekseyev, Aug 09 2012

A015924 Positive integers n such that 2^n == 16 (mod n).

Original entry on oeis.org

1, 2, 4, 6, 7, 8, 12, 16, 20, 24, 28, 40, 44, 48, 52, 60, 68, 76, 80, 92, 112, 116, 120, 124, 148, 154, 164, 172, 188, 204, 208, 212, 236, 240, 244, 264, 268, 280, 284, 292, 316, 332, 340, 356, 364, 388, 404, 412, 428, 436, 452, 508, 520, 524, 548, 556, 596

Offset: 1

Robert G. Wilson v

nonn

Odd terms are given by A033984.

For all m, 2^A128121(m)-1 belongs to this sequence.

T. D. Noe, Table of n, a(n) for n = 1..1000
OEIS Wiki, 2^n mod n

Contains A050992 as a subsequence.

Cf. A033984, A173138.

Select[Range[1000], Mod[2^# - 2^4, #] == 0 &] (* T. D. Noe, Aug 17 2012 *)
Join[{1,2,4,6,7,8,12,16},Select[Range[600],PowerMod[2,#,#]==16&]] (* Harvey P. Dale, Dec 03 2021 *)

Edited and terms 1,2,4,6,7,8,12,16 prepended by Max Alekseyev, Jul 29 2011

A385073 a(n) = b^(n-1) mod n, where b = A053669(n) is the least integer greater than 1 and coprime to n.

Original entry on oeis.org

0, 1, 1, 3, 1, 5, 1, 3, 4, 3, 1, 5, 1, 3, 4, 11, 1, 11, 1, 7, 4, 3, 1, 5, 16, 3, 13, 27, 1, 7, 1, 11, 4, 3, 9, 29, 1, 3, 4, 27, 1, 17, 1, 27, 31, 3, 1, 29, 15, 33, 4, 27, 1, 11, 49, 3, 4, 3, 1, 43, 1, 3, 4, 43, 16, 23, 1, 27, 4, 13, 1, 29, 1, 3, 34, 27, 9, 5, 1, 27, 40, 3, 1, 17

Offset: 1

Robert G. Wilson v, Jun 16 2025

Inspired by Fermat's Little Theorem.

a(n) > 0 for n > 1 since n and b are coprime.

Wikipedia, Fermat's little theorem

Cf. A053669, A385074.

f:= proc(n) local b;
  b:= 2;
  while n mod b = 0 do b:= nextprime(b) od;
  b &^ (n-1) mod n
end proc:
f(1):= 0:
map(f, [$1..100]); # Robert Israel, Jun 18 2025

a[n_] := Block[{b = 2}, While[GCD[n, b] > 1, b++]; PowerMod[b, n - 1, n]]; Array[a, 84]

a(n) = forprime(p=2, , if(n%p, return(lift(Mod(p, n)^(n-1))))); \\ Michel Marcus, Jun 18 2025

a(n) = 0 iff n = 1.
a(n) = 1 iff n belongs to A000040, A001567, or A130433.
a(n) = 2 iff n>1 and belongs to A173572;
a(n) = 4 iff n belongs to A033553;
a(n) = 8 iff n>7 and belongs to either A033984 or A173138;
a(n) = 16 iff n>15 and belongs to A276968;
a(n) = 32 iff n>1 and belongs to A215610;
a(n) = 64 iff n>63 and belongs to A276969;
a(n) = 128 iff n>127 and belongs to A215611;
a(n) = 256 iff n>255 and belongs to A276970;
a(n) = 512 iff n>511 and belongs to A215612;
a(n) = 1024 iff n>1023 and belongs to A276971;
a(n) = 2048 iff n>2047 and belongs to A215613;
From Robert Israel, Jun 18 2025: (Start)
a(2*p) = 3 if p is a prime > 3.
a(3*p) = 4 if p is a prime > 2.
a(4*p) = 3^3 if p is a prime > 5.
a(6*p) = 5^5 if p is a prime > 509.
a(8*p) = 3^5 if p is a prime > 271.
a(10*p) = 3^9 if p is a prime > 1951.
a(12*p) = 5^11 if p is a prime > 4069003. (End)

cp's OEIS Frontend

A173572 Odd integers n such that 2^n == 4 (mod n).

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Extensions

A033984 Odd integers n such that 2^n == 16 (mod n).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

Extensions

A015924 Positive integers n such that 2^n == 16 (mod n).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

Extensions

A385073 a(n) = b^(n-1) mod n, where b = A053669(n) is the least integer greater than 1 and coprime to n.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula