A066502 -id:A066502 - cp's OEIS frontend

A066498 Numbers k such that 3 divides phi(k).

7, 9, 13, 14, 18, 19, 21, 26, 27, 28, 31, 35, 36, 37, 38, 39, 42, 43, 45, 49, 52, 54, 56, 57, 61, 62, 63, 65, 67, 70, 72, 73, 74, 76, 77, 78, 79, 81, 84, 86, 90, 91, 93, 95, 97, 98, 99, 103, 104, 105, 108, 109, 111, 112, 114, 117, 119, 122, 124, 126, 127, 129, 130, 133

Offset: 1

Benoit Cloitre, Jan 04 2002

nonn

Numbers k such that x^3 == 1 (mod k) has solutions 1 < x < k.
Terms are multiple of 9 or of a prime of the form 6k+1.
If k is a term of this sequence, then G =  is a non-abelian group of order 3k, where 1 < r < n and r^3 == 1 (mod k). For example, G can be the subgroup of GL(2, Z_k) generated by x = {{1, 1}, {0, 1}} and y = {{r, 0}, {0, 1}}. - Jianing Song, Sep 17 2019
The asymptotic density of this sequence is 1 (Dressler, 1975). - Amiram Eldar, Mar 21 2021

			If n < 7 then x^3 = 1 (mod n) has no solution 1 < x < n, but {2,4} are solutions to x^3 == 1 (mod 7), hence a(1) = 7.

Harry J. Smith, Table of n, a(n) for n=1..1000
Robert E. Dressler, A property of the phi and sigma_j functions, Compositio Mathematica, Vol. 31, No. 2 (1975), pp. 115-118.

Complement of A088232.
Cf. A000010, A066499, A066500, A066501, A066502.
A007645 gives the primes congruent to 1 mod 3.
Column k=2 of A277915.

Select[Range[150], Divisible[EulerPhi[#], 3]&] (* Harvey P. Dale, Jan 12 2011 *)

isok(k)={ eulerphi(k)%3 == 0 } \\ Harry J. Smith, Feb 18 2010

Simpler definition from Yuval Dekel (dekelyuval(AT)hotmail.com), Oct 25 2003

Corrected and extended by Ray Chandler, Nov 05 2003

A319101 Number of solutions to x^7 == 1 (mod n).

Original entry on oeis.org

1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 7, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 7, 1, 1, 1, 1, 1, 7, 1, 1, 1, 1, 1, 1, 1, 1, 7, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 7, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 7, 7

Offset: 1

Jianing Song, Sep 10 2018

All terms are powers of 7. Those n such that a(n) > 1 are in A066502.

			Solutions to x^7 == 1 (mod 29): x == 1, 7, 16, 20, 23, 24, 25 (mod 29).
Solutions to x^7 == 1 (mod 43): x == 1, 4, 11, 16, 21, 35, 41 (mod 43).
Solutions to x^7 == 1 (mod 49): x == 1, 8, 15, 22, 29, 36, 43 (mod 49) (x == 1 (mod 7)).

Jianing Song, Table of n, a(n) for n = 1..10000

Number of solutions to x^k == 1 (mod n): A060594 (k=2), A060839 (k=3), A073103 (k=4), A319099 (k=5), A319100 (k=6), this sequence (k=7), A247257 (k=8).
Cf. A066502, A140444, A293484, A000010.
Mobius transform gives A307382.

f[p_, e_] := If[Mod[p, 7] == 1, 7, 1]; f[7, 1] = 1; f[7, e_] := 7; a[1] = 1; a[n_] := Times @@ f @@@ FactorInteger[n]; Array[a, 100] (* Amiram Eldar, Aug 10 2023 *)

a(n)=my(Z=znstar(n)[2]); prod(i=1, #Z, gcd(7, Z[i]))

Multiplicative with a(7) = 1, a(7^e) = 7 if e >= 2; for other primes p, a(p^e) = 7 if p == 1 (mod 7), a(p^e) = 1 otherwise.
If the multiplicative group of integers modulo n is isomorphic to C_{k_1} x C_{k_2} x ... x C_{k_m}, where k_i divides k_j for i < j; then a(n) = Product_{i=1..m} gcd(7, k_i).
a(n) = A000010(n)/A293484(n). - Jianing Song, Nov 10 2019

A066500 Numbers k such that 5 divides phi(k).

Original entry on oeis.org

11, 22, 25, 31, 33, 41, 44, 50, 55, 61, 62, 66, 71, 75, 77, 82, 88, 93, 99, 100, 101, 110, 121, 122, 123, 124, 125, 131, 132, 142, 143, 150, 151, 154, 155, 164, 165, 175, 176, 181, 183, 186, 187, 191, 198, 200, 202, 205, 209, 211, 213, 217, 220, 225, 231, 241

Offset: 1

Benoit Cloitre, Jan 04 2002

nonn

Related to the equation x^5 == 1 (mod k): sequence gives values of k such there are solutions 1 < x < k of x^5 == 1 (mod k).
If k is a term of this sequence, then G =  is a non-abelian group of order 5k, where 1 < r < n and r^5 == 1 (mod k). For example, G can be the subgroup of GL(2, Z_k) generated by x = {{1, 1}, {0, 1}} and y = {{r, 0}, {0, 1}}. - Jianing Song, Sep 17 2019
The asymptotic density of this sequence is 1 (Dressler, 1975). - Amiram Eldar, May 23 2022

			x^5 == 1 (mod 11) has solutions 1 < x < 11, namely {3,4,5,9}.

Harry J. Smith, Table of n, a(n) for n = 1..1000
Robert E. Dressler, A property of the phi and sigma_j functions, Compositio Mathematica, Vol. 31, No. 2 (1975), pp. 115-118.

Cf. A000010, A045453, A066498, A066499, A066501, A066502.

Column k=3 of A277915.

Select[Range[250], Divisible[EulerPhi[#], 5] &] (* Amiram Eldar, May 23 2022 *)

isok(k) = { eulerphi(k)%5 == 0 } \\ Harry J. Smith, Feb 18 2010

a(n) are the numbers generated by 5^2 = 25 and all primes congruent to 1 mod 5 (A045453). Hence sequence gives all k such that k == 0 (mod A045453(n)) for some n > 1 or k == 0 (mod 25).

Simpler definition from Yuval Dekel (dekelyuval(AT)hotmail.com), Oct 25 2003

Extended by Ray Chandler, Nov 06 2003

A066499 Numbers k such that phi(k) == 2 (mod 4).

Original entry on oeis.org

3, 4, 6, 7, 9, 11, 14, 18, 19, 22, 23, 27, 31, 38, 43, 46, 47, 49, 54, 59, 62, 67, 71, 79, 81, 83, 86, 94, 98, 103, 107, 118, 121, 127, 131, 134, 139, 142, 151, 158, 162, 163, 166, 167, 179, 191, 199, 206, 211, 214, 223, 227, 239, 242, 243, 251, 254, 262, 263, 271

Offset: 1

Benoit Cloitre, Jan 04 2002

nonn

Related to the equation x^4 = 1 (mod y): sequence gives values of n such x^4 = 1 (mod n) has no solution 1 < x < n-1.
k is of the form p^m or 2*p^m where p is A002145 (with the exception of a(2)=4).
All prime numbers here belong also to A002145, prime numbers of the form 4n+3. - Enrique Pérez Herrero, Sep 07 2011

W. J. LeVeque, Fundamentals of Number Theory, pp. 57 Problem 15, Dover NY 1996.

Harry J. Smith, Table of n, a(n) for n = 1..1000

Cf. A066498, A066500, A066501, A066502, A000010.
Essentially the same as A097987.
Cf. A002145.

Select[Range[300],Mod[EulerPhi[#],4]==2&] (* Harvey P. Dale, Feb 18 2018 *)

isok(k) = { eulerphi(k)%4 == 2 } \\ Harry J. Smith, Feb 18 2010

Simpler definition from Lekraj Beedassy, Jul 21 2003

Corrected and extended by Ray Chandler, Nov 06 2003

A277915 A(n,k) is the n-th number m such that a nontrivial prime(k)-th root of unity modulo m exists; square array A(n,k), n>=1, k>=1, read by antidiagonals.

Original entry on oeis.org

8, 7, 12, 11, 9, 15, 29, 22, 13, 16, 23, 43, 25, 14, 20, 53, 46, 49, 31, 18, 21, 103, 79, 67, 58, 33, 19, 24, 191, 137, 106, 69, 71, 41, 21, 28, 47, 229, 206, 131, 89, 86, 44, 26, 30, 59, 94, 361, 239, 157, 92, 87, 50, 27, 32, 311, 118, 139, 382, 274, 158, 115, 98, 55, 28, 33

Offset: 1

Alois P. Heinz, Nov 03 2016

The trivial square roots of unity modulo m are {1, m-1} and for an odd prime p the trivial p-th root of unity modulo m is 1.
There is no prime in the first column.
Column k>1 contains prime(k)^2.

			Square array A(n,k) begins:
:  8,  7, 11, 29,  23,  53, 103, 191, ...
: 12,  9, 22, 43,  46,  79, 137, 229, ...
: 15, 13, 25, 49,  67, 106, 206, 361, ...
: 16, 14, 31, 58,  69, 131, 239, 382, ...
: 20, 18, 33, 71,  89, 157, 274, 419, ...
: 21, 19, 41, 86,  92, 158, 289, 457, ...
: 24, 21, 44, 87, 115, 159, 307, 458, ...
: 28, 26, 50, 98, 121, 169, 309, 571, ...

Alois P. Heinz, Antidiagonals n = 1..200, flattened
Wikipedia, Root of unity modulo n

Columns k=1-4 give: A033949, A066498, A066500, A066502.
Row n=1 gives A066674 for k>1.
Main diagonal gives A305828.
Cf. A000010, A000040, A002322.

with(numtheory):
A:= proc() local j, l; l:= proc() [] end;
      proc(n, k)
        while nops(l(k)) lambda(j) or k>1 and
                  irem(phi(j), ithprime(k))=0 then
                  l(k):= [l(k)[], j]; break fi
          od
        od: l(k)[n]
      end
    end():
seq(seq(A(n, 1+d-n), n=1..d), d=1..15);

A[n_, k_] := Module[{j, l = {}}, While[Length[l]CarmichaelLambda[j] || k>1 && Mod[EulerPhi[j], Prime[k]]==0, AppendTo[l, j]; Break[]]]]; l[[n]]];
Table[A[n, 1 + d - n], {d, 1, 15}, {n, 1, d}] // Flatten (* Jean-François Alcover, May 29 2018, from Maple *)

A066501 Numbers k such that x^6 == 1 (mod(k)) has no solution 1 < x < k-1.

Original entry on oeis.org

1, 2, 3, 4, 5, 6, 10, 11, 17, 22, 23, 25, 29, 34, 41, 46, 47, 50, 53, 58, 59, 71, 82, 83, 89, 94, 101, 106, 107, 113, 118, 121, 125, 131, 137, 142, 149, 166, 167, 173, 178, 179, 191, 197, 202, 214, 226, 227, 233, 239, 242, 250, 251, 257, 262, 263, 269, 274, 281, 289, 293

Offset: 1

Benoit Cloitre, Jan 04 2002

nonn

Cf. A045309, A066498, A066499, A066500, A066502, A000010.

isok(n) = {for (x=2, n-2, if ((Mod(x, n)^6) == Mod(1, n), return (0));); return (1);} \\ Michel Marcus, Nov 20 2013

Sequence consists of the numbers 4, 6 and for all k > 1, A045309(k), 2*A045309(k), A045309(k)^2, 2*A045309(k)^2.

Extended by Ray Chandler, Nov 06 2003

Terms 1, 2 and 3 prepended by Michel Marcus, Nov 20 2013

A172019 Numbers k such that 4 divides phi(k) (i.e., A000010(k)).

Original entry on oeis.org

5, 8, 10, 12, 13, 15, 16, 17, 20, 21, 24, 25, 26, 28, 29, 30, 32, 33, 34, 35, 36, 37, 39, 40, 41, 42, 44, 45, 48, 50, 51, 52, 53, 55, 56, 57, 58, 60, 61, 63, 64, 65, 66, 68, 69, 70, 72, 73, 74, 75, 76, 77, 78, 80, 82, 84, 85, 87, 88, 89, 90, 91, 92, 93, 95, 96, 97, 99, 100, 101

Offset: 1

Giovanni Teofilatto, Jan 22 2010

Complement of A097987.

The asymptotic density of this sequence is 1 (Dressler, 1975). - Amiram Eldar, Feb 12 2021

Rémy Sigrist, Table of n, a(n) for n = 1..10000
Robert E. Dressler, A property of the phi and sigma_j functions, Compositio Mathematica, Vol. 31, No. 2 (1975), pp. 115-118.

Cf. A000010, A097987, A066499, A066498, A066500, A066502.

Select[Range[200], Mod[EulerPhi[#], 4] == 0 &] (* Geoffrey Critzer, Nov 30 2014 *)

is(n)=my(o=valuation(n, 2), p); (o>1 || !isprimepower(n>>o, &p) || p%4<2) && n>4 \\ Charles R Greathouse IV, Mar 05 2013

A045465 Primes congruent to {0, 1} mod 7.

Original entry on oeis.org

7, 29, 43, 71, 113, 127, 197, 211, 239, 281, 337, 379, 421, 449, 463, 491, 547, 617, 631, 659, 673, 701, 743, 757, 827, 883, 911, 953, 967, 1009, 1051, 1093, 1163, 1289, 1303, 1373, 1429, 1471, 1499, 1583

Offset: 1

N. J. A. Sloane

Vincenzo Librandi, Table of n, a(n) for n = 1..1000

Cf. A000040, A066502, A034167, A042969.

[ p: p in PrimesUpTo(2000) | p mod 7 in {0, 1} ]; // Vincenzo Librandi, Aug 13 2012

Select[Prime[Range[200]],MemberQ[{0,1},Mod[#,7]]&] (* Vincenzo Librandi, Aug 13 2012 *)

A358043 Numbers k such that phi(k) is a multiple of 8.

Original entry on oeis.org

15, 16, 17, 20, 24, 30, 32, 34, 35, 39, 40, 41, 45, 48, 51, 52, 55, 56, 60, 64, 65, 68, 70, 72, 73, 75, 78, 80, 82, 84, 85, 87, 88, 89, 90, 91, 95, 96, 97, 100, 102, 104, 105, 110, 111, 112, 113, 115, 116, 117, 119, 120, 123, 128, 130, 132, 135, 136, 137, 140, 143

Offset: 1

Darío Clavijo, Oct 26 2022

nonn

Cf. A000010 (phi), A053574 (its 2-adic valuation), A037074 (a subsequence).

Totient multiples: A066498 (3), A172019 (4), A066500 (5), A066502 (7), A332512 (12).

Select[Range[150], Divisible[EulerPhi[#], 8] &] (* Amiram Eldar, Oct 27 2022 *)

isok(k) = Mod(eulerphi(k), 8) == 0; \\ Michel Marcus, Oct 27 2022

from sympy.ntheory import totient
def isok(n): return totient(n) % 8 == 0

A000010(a(n)) == 0 (mod 8).

cp's OEIS Frontend

A066498 Numbers k such that 3 divides phi(k).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Extensions

A319101 Number of solutions to x^7 == 1 (mod n).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A066500 Numbers k such that 5 divides phi(k).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions

A066499 Numbers k such that phi(k) == 2 (mod 4).

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Mathematica

PARI

Extensions

A277915 A(n,k) is the n-th number m such that a nontrivial prime(k)-th root of unity modulo m exists; square array A(n,k), n>=1, k>=1, read by antidiagonals.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

A066501 Numbers k such that x^6 == 1 (mod(k)) has no solution 1 < x < k-1.

Views

Author

Keywords

Crossrefs

Programs

PARI

Formula

Extensions

A172019 Numbers k such that 4 divides phi(k) (i.e., A000010(k)).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI