A033949 -id:A033949 - cp's OEIS frontend

A279401 Irregular triangle read by rows. Row n gives the orders of the primes of row n of the irregular triangle A279399 modulo A033949(n).

2, 2, 2, 2, 2, 2, 4, 4, 2, 4, 4, 4, 2, 4, 4, 4, 4, 2, 4, 4, 2, 6, 6, 6, 2, 6, 6, 2, 2, 2, 2, 2, 2, 2, 6, 6, 6, 2, 6, 6, 6, 4, 2, 4, 4, 2, 4, 2, 8, 8, 4, 8, 8, 2, 8, 4, 8, 2, 10, 10, 10, 10, 10, 10, 2, 10, 5, 12, 12, 3, 4, 12, 6, 12, 2, 6, 6, 6, 6, 3, 2, 2, 6, 6, 6, 12, 4, 12, 12, 6, 12, 6, 6, 4, 12, 4, 4, 2, 4, 4, 2, 4, 2, 2, 4

Offset: 1

Wolfdieter Lang, Jan 30 2017

The length of row n is given by A279400(n).
See the A279399 comments.
The entries in row n are proper divisors of phi(A033949(n)), where phi(n) = A000010(n).
  This is because no A033949 number has a primitive root.

			The irregular triangle T(n, k) begins (here N = A033949(n)):
n,   N \ k 1  2  3  4  5  6  7  8  9 10 ...
1,   8:    2  2  2
2,  12:    2  2  2
3,  15:    4  4  2  4
4,  16:    4  4  2  4  4
5,  20:    4  4  2  4  4  2
6,  21:    6  6  6  2  6  6
7,  24:    2  2  2  2  2  2  2
8,  28:    6  6  6  2  6  6  6
9,  30:    4  2  4  4  2  4  2
10, 32:    8  8  4  8  8  2  8  4  8  2
11, 33:   10 10 10 10 10 10  2 10  5
12, 35:   12 12  3  4 12  6 12  2  6
13, 36:    6  6  6  3  2  2  6  6  6
14, 39:   12  4 12 12  6 12  6  6  4 12
15, 40:    4  4  2  4  4  2  4  2  2  4
...
The sequence of phi(N) begins: 4, 4, 8, 8, 8, 12, 8, 12, 8, 16, 20, 24, 12, 24, 16, ...
n = 2, N = 12:  5^2 == 7^2 == 11^2 == 1 (mod 12), therefore 2 is the least positive power k for each of the three primes p of row 2 of A279399 which satisfies p^k == 1 (mod A033949(2)).

Cf. A000010, A033949, A279399, A279400.

T(n, k) = order(A279399(n, k)) (mod A033949(n)), n >= 1, k = 1..A279400(n).

A033948 Numbers that have a primitive root (the multiplicative group modulo n is cyclic).

Original entry on oeis.org

1, 2, 3, 4, 5, 6, 7, 9, 10, 11, 13, 14, 17, 18, 19, 22, 23, 25, 26, 27, 29, 31, 34, 37, 38, 41, 43, 46, 47, 49, 50, 53, 54, 58, 59, 61, 62, 67, 71, 73, 74, 79, 81, 82, 83, 86, 89, 94, 97, 98, 101, 103, 106, 107, 109, 113, 118, 121, 122, 125, 127, 131, 134, 137, 139

Offset: 1

Calculated by Jud McCranie, entered by N. J. A. Sloane

nonn

The sequence consists of 1, 2, 4 and numbers of the form p^i and 2p^i, where p is an odd prime and i >= 1.
Sequence gives values of n such that x^2 == 1 (mod n) has no solution with 1 < x < n-1. - Benoit Cloitre, Jan 04 2002
Gaussian criterion for terms of the sequence: n is in the sequence iff Product_{1<=i<=n-1, gcd(i,n)=1} i == -1 (mod n), see example. - Vladimir Shevelev, Jan 11 2011
For the criterion used above see the Hardy and Wright reference, Theorem 129. p. 102, a consequence of Bauer's theorem. See also T. D. Noe's comment with the Nagell reference on A060594 and also A160377. - Wolfdieter Lang, Feb 16 2012
Also numbers n such that phi(n) = lambda(n) (or numbers with A034380(n)=1), where phi is A000010, and lambda is Carmichael's lambda: A002322. - Enrique Pérez Herrero, Jun 04 2013
All values of n>2 are given when there are exactly two solutions for n*j+1 is a square, 0 <= j < n, which are j = {0, n-2}. See Mathematica examples. - Richard R. Forberg, Mar 26 2016
Numbers n such that the Galois group of the cyclotomic field with the n-th roots of unity is a cyclic group. [Van der Waerden, p. 55, Th. 4.11.; Corwin, 1967] - N. J. A. Sloane, Nov 26 2016

			Gaussian product for n=9 is 1*2*4*5*7*8=2240. Since 2240==-1(mod 9), then 9 is in the sequence. - _Vladimir Shevelev_, Jan 11 2011

G. H. Hardy and E. M. Wright, An Introduction to the Theory of Numbers, Fifth ed., Clarendon Press, Oxford, 2003, Theorem 129, p. 102.
I. Niven and H. S. Zuckerman, An Introduction to the Theory of Numbers, 4th edition, page 62, Theorem 2.25.
B. L. van der Waerden, Modern Algebra, 2nd. ed., Ungar, NY, Vol. I, 1948.

T. D. Noe, Table of n, a(n) for n = 1..10000
Anonymous, Notes on Number Theory:Primitive Roots [broken link]
Joerg Arndt, Matters Computational (The Fxtbook), p. 778.
L. J. Corwin, Irreducible polynomials over the integers which factor mod p for every p, Unpublished Bell Labs Memo, Sep 07 1967 [Annotated scanned copy]
Math Reference Project, Primitive Root
Jorma K. Merikoski, Pentti Haukkanen, and Timo Tossavainen, The congruence x^n = -a^n (mod m): Solvability and related OEIS sequences, Notes. Num. Theor. Disc. Math. (2024) Vol. 30, No. 3, 516-529. See p. 519.
Eric Weisstein's World of Mathematics, Primitive Root
Eric Weisstein's World of Mathematics, Modulo Multiplication Group
Wolfram Research, Prime Roots

Cf. A033949 (complement), A072209, A001783 (Gaussian products used in the V. Shevelev example).
Cf. also A002322, A060594, A062373, A034380, A160377.
Union of 1, 2, 4, A061345, A278568.

m := proc(n) local k, r; r := 1; if n = 2 then return false fi;
for k from 1 to n do if igcd(n,k) = 1 then r := modp(r*k,n) fi od; r end:
select(n -> m(n) <> 1, [$1..139]); # Peter Luschny, May 25 2017

Join[{1}, Select[ Range[140], IntegerQ[ PrimitiveRoot[#]] &]] (* Jean-François Alcover, Sep 27 2011 *)
Select[Range[139], EulerPhi[#] == CarmichaelLambda[#] &] (* T. D. Noe, Jun 04 2013 *)
result = {}; Do[count = 0;
Do[If[Mod[j^2, n] == 1, count++], {j, 2, n - 2}];
If[count == 0, AppendTo[result, n]], {n, 1, 200}]; result (* Richard R. Forberg, Mar 26 2016 *)
result = {}; Do[count = 0;
Do[ r = Sqrt[n*j + 1]; If[IntegerQ[r], count++], {j, 0, n}];
If[count == 2, AppendTo[result, n]], {n, 0, 200}]; result  (* missing{1,2} Richard R. Forberg, Mar 26 2016 *)

is(n)=if(n%2, isprimepower(n) || n==1, n==2 || n==4 || (isprimepower(n/2,&n) && n>2)) \\ Charles R Greathouse IV, Apr 16 2015

from sympy import primepi, integer_nthroot
def A033948(n):
    def bisection(f,kmin=0,kmax=1):
        while f(kmax) > kmax: kmax <<= 1
        kmin = kmax >> 1
        while kmax-kmin > 1:
            kmid = kmax+kmin>>1
            if f(kmid) <= kmid:
                kmax = kmid
            else:
                kmin = kmid
        return kmax
    def f(x): return int(n-1+x-(x>=2)-(x>=4)-sum(primepi(integer_nthroot(x,k)[0])-1 for k in range(1,x.bit_length()))-sum(primepi(integer_nthroot(x>>1,k)[0])-1 for k in range(1,x.bit_length()-1)))
    return bisection(f,n,n) # Chai Wah Wu, Feb 24 2025

A046144 Number of primitive roots modulo n.

Original entry on oeis.org

1, 1, 1, 1, 2, 1, 2, 0, 2, 2, 4, 0, 4, 2, 0, 0, 8, 2, 6, 0, 0, 4, 10, 0, 8, 4, 6, 0, 12, 0, 8, 0, 0, 8, 0, 0, 12, 6, 0, 0, 16, 0, 12, 0, 0, 10, 22, 0, 12, 8, 0, 0, 24, 6, 0, 0, 0, 12, 28, 0, 16, 8, 0, 0, 0, 0, 20, 0, 0, 0, 24, 0, 24, 12, 0, 0, 0, 0, 24, 0, 18, 16, 40, 0, 0, 12, 0, 0, 40, 0, 0

Offset: 1

Eric W. Weisstein

nonn

T. D. Noe, Table of n, a(n) for n = 1..10000
S. R. Finch, Idempotents and Nilpotents Modulo n, arXiv:math/0605019 [math.NT], 2006-2017.
Eric Weisstein's World of Mathematics, Primitive Root.

Cf. A001918, A010554, A033949, A046145, A046146, A008330, A002233, A071894, A219027.

A046144 := proc(n)
    local a,eulphi,m;
    if n = 1 then
        return 1;
    end if;
    eulphi := numtheory[phi](n) ;
    a := 0 ;
    for m from 0 to n-1 do
        if numtheory[order](m,n) = eulphi then
            a := a + 1 ;
        end if;
    end do:
    a;
end proc: # R. J. Mathar, Jan 12 2016

Prepend[ Table[ If[ IntegerQ[ PrimitiveRoot[n]] , EulerPhi[ EulerPhi[n]], 0], {n, 2, 91}],1] (* Jean-François Alcover, Sep 13 2011 *)

for(i=1, 100, p=0; for(q=1, i, if(gcd(q,i)==1 && znorder(Mod(q,i)) == eulerphi(i), p++)); print1(p, ", ")) /* V. Raman, Nov 22 2012 */

a(n) = my(s=znstar(n)); if(#(s.cyc)>1, 0, eulerphi(s.no)) \\ Jeppe Stig Nielsen, Oct 18 2019

use ntheory ":all"; my @A = map { !defined znprimroot($) ? 0 : euler_phi(euler_phi($)); } 0..10000; say "$ $A[$]" for 1..$#A; # Dana Jacobsen, Apr 28 2017

a(n) is equal to A010554(n) unless n is a term of A033949, in which case a(n)=0.

A034380 Ratio of totient to Carmichael's lambda function: a(n) = A000010(n) / A002322(n).

Original entry on oeis.org

1, 1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 2, 1, 1, 2, 2, 1, 1, 1, 2, 2, 1, 1, 4, 1, 1, 1, 2, 1, 2, 1, 2, 2, 1, 2, 2, 1, 1, 2, 4, 1, 2, 1, 2, 2, 1, 1, 4, 1, 1, 2, 2, 1, 1, 2, 4, 2, 1, 1, 4, 1, 1, 6, 2, 4, 2, 1, 2, 2, 2, 1, 4, 1, 1, 2, 2, 2, 2, 1, 8, 1, 1, 1, 4, 4, 1, 2, 4, 1, 2, 6, 2, 2, 1, 2, 4, 1, 1, 2, 2, 1, 2, 1, 4, 4

Offset: 1

Alex Fink

nonn

a(n)=1 if and only if the multiplicative group modulo n is cyclic (that is, if n is either 1, 2, 4, or of the form p^k or 2*p^k where p is an odd prime). In other words: a(n)=1 if n is a term of A033948, otherwise a(n) > 1 (and n is a term of A033949). - Joerg Arndt, Jul 14 2012

T. D. Noe, Table of n, a(n) for n = 1..10000
W. D. Banks and F. Luca, On integers with a special divisibility property, Archivum Mathematicum (BRNO) 42 (2006) pp 31-42.

Cf. A000010, A002322, A033948, A033949, A062373-A062377, A080400, A289624.

a034380 n = a000010 n `div` a002322 n
-- Reinhard Zumkeller, Sep 02 2014

[1] cat [EulerPhi(n) div CarmichaelLambda(n): n in [2..100]]; // Vincenzo Librandi, Jul 18 2017

Maple
```
A034380 := n-> phi(n) / lambda(n);
```

Table[EulerPhi[n]/CarmichaelLambda[n], {n, 1, 200}] (* Geoffrey Critzer, Dec 23 2014 *)

eulerphi(n)/lcm(znstar(n)[2]) \\ Charles R Greathouse IV, Feb 01 2013

a(n) = A000010(n) / A002322(n).
a(A033948(n)) = 1 [Banks & Luca]. - R. J. Mathar, Jul 29 2007
A002322(n)/A007947(a(n)) = A289624(n). - Antti Karttunen, Jul 17 2017

A070667 Smallest m in range 2..n-1 such that m^2 == 1 mod n, or 1 if no such number exists.

Original entry on oeis.org

1, 1, 2, 3, 4, 5, 6, 3, 8, 9, 10, 5, 12, 13, 4, 7, 16, 17, 18, 9, 8, 21, 22, 5, 24, 25, 26, 13, 28, 11, 30, 15, 10, 33, 6, 17, 36, 37, 14, 9, 40, 13, 42, 21, 19, 45, 46, 7, 48, 49, 16, 25, 52, 53, 21, 13, 20, 57, 58, 11, 60, 61, 8, 31, 14, 23, 66, 33, 22, 29

Offset: 1

N. J. A. Sloane, May 08 2002

nonn

If n has a primitive root (i.e. if n is in A033948(n)) then a(n)=n-1, if not (i.e. if n is in A033949(n)), a(n)A000961(m), then a(n)=n/2-1. Questions : for which n does the equation A070667(x)=x-n have at least one solution, does always A070667(x)=x-p have at least one solution when p is prime =>5? - Benoit Cloitre, May 12 2002

Alois P. Heinz, Table of n, a(n) for n = 1..10000

Cf. A033948, A033949, A000961.

a:= proc(n) local k; for k from 2 do if 1=k*k mod n
      then return k elif k>=n then return 1 fi od
    end:
seq(a(n), n=1..100);  # Alois P. Heinz, Oct 30 2016

Join[{1,1},Flatten[Table[Select[Range[2,n-1],PowerMod[#,2,n]==1&,1],{n,70}]]] (* Harvey P. Dale, May 01 2012 *)

A090129 Smallest exponent such that -1 + 3^a(n) is divisible by 2^n.

Original entry on oeis.org

1, 2, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096, 8192, 16384, 32768, 65536, 131072, 262144, 524288, 1048576, 2097152, 4194304, 8388608, 16777216, 33554432, 67108864, 134217728, 268435456, 536870912, 1073741824, 2147483648, 4294967296, 8589934592, 17179869184

Offset: 1

Labos Elemer and Ralf Stephan, Jan 19 2004

A131577 and A011782 are companions, A131577(n) + A011782(n) = 2^n, (and differences each other). - Paul Curtz, Jan 18 2009
A090127 with offset 0: (1, 2, 2, 4, 8, ...) = A(x) / A(x^2), when A(x) = (1 + 2x + 4x^2 + 8x^3 + ...). - Gary W. Adamson, Feb 20 2010
From Wolfdieter Lang, Apr 18 2012: (Start)
a(n) is the order of 3 modulo 2^n. For n=1 and 2 this is obviously 1 and 2, respectively, and for n >= 3 it is 2^(n-2).
For a proof see, e.g., the Graeme McRae link under A068531, the section 'A Different Approach', proposed by Alexander Monnas, the first part, where the result from the expansion of (4-1)^(2^(k-2)) holds only for k >= 3. See also the Charles R Greathouse IV program below where this result has been used.
This means that the cycle generated by 3, taken modulo 2^n, has length a(n), and that 3 is not a primitive root modulo 2^n, if n >= 3 (because Euler's phi(2^n) = 2^(n-1), n >= 1, see A000010).
(End)
Let r(x) = (1 + 2x + 2x^2 + 4x^3 + ...). Then (1 + 2x + 4x^2 + 8x^3 + ...) = (r(x) * r(x^2) * r(x)^4 * r(x^8) * ...). - Gary W. Adamson, Sep 13 2016

			a(1) = 1 since -1 + 3 = 2 is divisible by 2^1;
a(2) = a(3) = 2 since -1 + 9 = 8 is divisible by 4 = 2^2 and also by 8 = 2^3;
a(5) = 8 since -1 + 6561 = 6560 = 32*205 is divisible by 2^5.
From _Wolfdieter Lang_, Apr 18 2012: (Start)
n=3: the order of 3 (mod 8) is a(3)=2 because the cycle generated by 3 is [3, 3^2==1 (mod 8)].
n=5: a(5) = 2^3 = 8 because the cycle generated by 3 is [3^1=3, 3^2=9, 3^3=27, 17, 19, 25, 11, 1] (mod 32).
  The multiplicative group mod 32 is non-cyclic (see A033949(10)) with the additional four cycles  [5, 25, 29, 17, 21, 9, 13, 1], [7, 17, 23, 1], [15, 1], and [31, 1]. This is the cycle structure of the (Abelian) group Z_8 x Z_2 (see one of the cycle graphs shown in the Wikipedia link 'List of small groups' for the order phi(32)=16, given under A192005).
(End)

Index to divisibility sequences

Cf. A068531, A069895, A088660, A090739, A090740, A091512.

Essentially the same as A000079.

t=Table[Part[Flatten[FactorInteger[ -1+3^(n)]], 2], {n, 1, 130}] Table[Min[Flatten[Position[t, j]]], {j, 1, 10}]
Join[{1,2},2^Range[30]] (* or *) Join[{1,2},NestList[2#&,2,30]] (* Harvey P. Dale, Nov 08 2012 *)

a(n)=2^(n+(n<3)-2) \\ Charles R Greathouse IV, Apr 09 2012

def A090129(n): return n if n<3 else 1<Chai Wah Wu, Jul 11 2022

a(n) = 2^(n-2) if n >= 3, 1 for n=1 and 2 for n=2 (see the order comment above).

a(n+2) = A152046(n) + A152046(n+1) = 2*A011782(n). - Paul Curtz, Jan 18 2009

a(11) through a(20) from R. J. Mathar, Aug 08 2008

More terms (powers of 2, see a comment above) from Wolfdieter Lang, Apr 18 2012

A076942 Smallest k > 0 such that n*k+1 is a square.

Original entry on oeis.org

3, 4, 1, 2, 3, 4, 5, 1, 7, 8, 9, 2, 11, 12, 1, 3, 15, 16, 17, 4, 3, 20, 21, 1, 23, 24, 25, 6, 27, 4, 29, 7, 3, 32, 1, 8, 35, 36, 5, 2, 39, 4, 41, 10, 8, 44, 45, 1, 47, 48, 5, 12, 51, 52, 8, 3, 7, 56, 57, 2, 59, 60, 1, 15, 3, 8, 65, 16, 7, 12, 69, 4, 71, 72, 9, 18, 15, 8, 77, 1, 79, 80, 81

Offset: 1

Amarnath Murthy, Oct 19 2002

nonn

a(n) <= n-2 for n > 2; a(p) = p-2 if p is a prime > 2. [Comment corrected by Floris P. van Doorn, Jan 31 2009]

a(n) = n - 2 precisely when n > 2 has a primitive root; that is, for 4, and p^k and 2*p^k for p an odd prime and k > 0. - Franklin T. Adams-Watters, Apr 13 2009

Floris P. van Doorn, Table of n, a(n) for n = 1..10000
Dorin Andrica and Vlad Crişan, The Smallest Nontrivial Solution to x^k == 1 (mod n) and Related Sequences, Amer. Math. Monthly, Vol. 126, No. 2 (2019), pp. 173-178.

Cf. A033948, A033949, A215653. [From Franklin T. Adams-Watters, Apr 13 2009]

Do[k = 1; While[ !IntegerQ[Sqrt[n*k + 1]], k++ ]; Print[k], {n, 1, 85}]

a(n) = {my(m = n + 1, k = 1); while(!issquare(m), m += n; k++); k;} \\ Amiram Eldar, Mar 16 2025

a(n) = ((A215653(n))^2-1)/n.

Edited and extended by Robert G. Wilson v, Oct 21 2002

A327818 Square array read by ascending antidiagonals: T(n,m) is the number of irreducible factors in the factorization of the m-th cyclotomic polynomial over GF(k), k = A246655(n) (counted with multiplicity).

Original entry on oeis.org

1, 1, 1, 1, 1, 1, 1, 1, 2, 2, 1, 1, 2, 1, 1, 1, 1, 1, 2, 1, 1, 1, 1, 2, 2, 2, 2, 2, 1, 1, 1, 1, 4, 2, 1, 4, 1, 1, 2, 2, 1, 1, 2, 2, 1, 1, 1, 1, 2, 1, 2, 1, 4, 6, 1, 1, 1, 2, 1, 2, 1, 6, 2, 2, 1, 1, 1, 1, 2, 2, 4, 2, 6, 2, 1, 2, 2, 2, 1, 1, 1, 2, 1, 1, 2, 4, 2, 4, 2, 2, 1

Offset: 1

Jianing Song, Sep 26 2019

T(n,m) = 1 if and only if (let k = A246655(n)):
(a) gcd(m,k) = 1, and k is a primitive root modulo m;
(b) k is a power of 2, m == 2 (mod 4), and k is a primitive root modulo m/2.
As a result, T(n,m) > 1 if at least one of the following holds:
(i) There is no primitive root modulo m, that is, m is in A033949;
(ii) k is a square number and m > 2.
If p = A246655(n) is prime, then T(n,m) is also the number of irreducible factors in the factorization of the ideal (p) in Z[zeta_m], zeta_m = exp(2*Pi*i/m). Actually, if the m-th cyclotomic polynomial factors as Product_{i=1..T(n,m)} F_i(x) over GF(p), then the factorization of (p) in Z[zeta_m] is (p) = Product_{i=1..T(n,m)} (p,F_i(zeta_m)). As a result, p remains inert in Q(zeta_m) <=> T(n,m) = 1. See Page 47-48, Proposition 8.3 and Page 61-62, Proposition 10.3 of the Neukirch link for a proof. - Jianing Song, Sep 13 2022

			Table starts
  n  A246655(n)  m=1  2  3  4  5  6  7  8  9  10
  1       2       1   1  1  2  1  1  2  4  1   1
  2       3       1   1  2  1  1  2  1  2  6   1
  3       4       1   1  2  2  2  2  2  4  2   2
  4       5       1   1  1  2  4  1  1  2  1   4
  5       7       1   1  2  1  1  2  6  2  2   1
  6       8       1   1  1  2  1  1  6  4  3   1
  7       9       1   1  2  2  2  2  2  4  6   2
  8      11       1   1  1  1  4  1  2  2  1   4

Amiram Eldar, Table of n, a(n) for n = 1..10011 (antidiagonals n = 1..141, flattened)
Jürgen Neukirch, Algebraic_number_theory.
Jianing Song, My notes on the factorization of cyclotomic polynomials over finite fields.
Hongfeng Wu, Li Zhu, Rongquan Feng, and Siman Yang, Explicit factorizations of cyclotomic polynomials over finite fields, Des. Codes Cryptogr. 83, 197-217 (2017).

Cf. A246655, A000010, A033949.

Rows 1..7 give: A318622, A327812, A327813, A327814, A327815, A327816, A327817.

T[max_] := Module[{pp = Select[Range[max], PrimePowerQ], m, t}, m = Length[pp]; t[i_, j_] := Module[{p = FactorInteger[pp[[j]]][[1, 1]]}, EulerPhi[i] / MultiplicativeOrder[pp[[j]], i/p^IntegerExponent[i, p]]]; Table[t[j, i - j + 1], {i, 1, m}, {j, 1, i}] // Flatten]; T[24] (* Amiram Eldar, Jul 21 2024 *)

f(k,m) = if(isprimepower(k), my(p=factor(k)[1,1], s=m/p^valuation(m,p)); eulerphi(m)/znorder(Mod(k,s)))
A246655(n) = my(i=0); for(t=1, oo, if(isprimepower(t), i++); if(i==n, return(t)))
a(n,m) = f(A246655(n),m)

Let m = p^e*s, where p is the prime factor of k = A246655(n), gcd(p,s) = 1, then T(n,m) = phi(m)/ord(k,s), where phi = A000010, ord(k,s) is the multiplicative order of k modulo s. Proof:
(a) First consider the case e = 0. Let F be the algebraic closure of GF(k), then Phi_s(x) = 0 has solutions in F, where Phi_s(x) is the s-th cyclotomic polynomial. Let a be any of the solution.
    In F, a belongs to GF(k^d) <=> a^(k^d-1) = 1 <=> s|(k^d-1) (note that in F, s is the smallest integer such that a^s = 1). As a result, a belongs to GF(k^ord(k,s)) but not to GF(k^d) for any d < ord(k,s), that is to say, a has algebraic degree ord(k,s) over GF(k). Because a is any of the roots of Phi_s(x) in F, every irreducible factor of Phi_s(x) over GF(k) is of degree ord(k,s), so the number of irreducible factors is phi(s)/ord(k,s);
(b) If e > 0, we can see from the Moebius inversion formula such that Phi_m(x) = (Phi_s(x))^phi(p^e), that the number of irreducible factors is phi(m)/ord(k,s).
The Introduction part in Page 2 and Lemma 1 in Page 3 of Hongfeng Wu's paper (see Links section) also mentions part (a) of this result.

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 *)

A206552 Moduli n for which the multiplicative group Modd n is non-cyclic (acyclic).

Original entry on oeis.org

12, 20, 24, 28, 30, 36, 40, 42, 44, 48, 52, 56, 60, 63, 65, 66, 68, 70, 72, 76, 78, 80, 84, 85, 88, 90, 91, 92, 96, 100, 102, 104, 105, 108, 110, 112, 114, 116, 117, 120, 124, 126, 130, 132, 133, 136, 138, 140, 144, 145, 148, 150, 152, 154, 156, 160, 164, 165

Offset: 1

Wolfdieter Lang, Mar 27 2012

nonn

For Modd n (not to be confused with mod n) see a comment on A203571.
Precisely these numbers n (only the ones <=165 are shown above) have no primitive root Modd n. See the zero entries of A206550, except A206550(1) = 0 which stands for a primitive root 0.
The multiplicative Modd n group is the Galois group Gal(Q(rho(n))/Q), with the algebraic number rho(n) := 2*cos(Pi/n) with minimal polynomial C(n,x), whose coefficients are given in A187360.

			a(1) = 12 because A206550(12) = 0 for the first time, not counting A206550(1) = 0. The cycle structure of the multiplicative Modd 12 group is [[5,1],[7,1],[11,1]]. This is the (abelian, non-cyclic) group Z_2 x Z_2 (isomorphic to the Klein group V_4 or Dih_2).
a(2) = 20 because A206550(20) = 0 for the second time, not counting A206550(1) = 0. The cycle structure of the multiplicative Modd 20 group is [[3,9,13,1],[7,9,17,1],[11,1],[19,1]]. This is the (abelian, non-cyclic) group Z_4 x Z_2.

Cf. A206550, A206551, A033949 (mod n case).

A206550(a(n)) = 0, n>=1.

cp's OEIS Frontend

A279401 Irregular triangle read by rows. Row n gives the orders of the primes of row n of the irregular triangle A279399 modulo A033949(n).

Views

Author

Keywords

Comments

Examples

Crossrefs

Formula

A033948 Numbers that have a primitive root (the multiplicative group modulo n is cyclic).

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Python

A046144 Number of primitive roots modulo n.

Views

Author

Keywords

Links

Crossrefs

Programs

Maple

Mathematica

PARI

PARI

Perl

Formula

A034380 Ratio of totient to Carmichael's lambda function: a(n) = A000010(n) / A002322(n).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Haskell

Magma

Maple

Mathematica

PARI

Formula

A070667 Smallest m in range 2..n-1 such that m^2 == 1 mod n, or 1 if no such number exists.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

A090129 Smallest exponent such that -1 + 3^a(n) is divisible by 2^n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Python

Formula

Extensions

A076942 Smallest k > 0 such that n*k+1 is a square.

Views

Author

Keywords

Comments

Links