A046144 -id:A046144 - cp's OEIS frontend

A277776 Triangle T(n,k) in which the n-th row contains the increasing list of nontrivial square roots of unity mod n; n>=1.

3, 5, 5, 7, 4, 11, 7, 9, 9, 11, 8, 13, 5, 7, 11, 13, 17, 19, 13, 15, 11, 19, 15, 17, 10, 23, 6, 29, 17, 19, 14, 25, 9, 11, 19, 21, 29, 31, 13, 29, 21, 23, 19, 26, 7, 17, 23, 25, 31, 41, 16, 35, 25, 27, 21, 34, 13, 15, 27, 29, 41, 43, 20, 37, 11, 19, 29, 31, 41

Offset: 1

Alois P. Heinz, Oct 30 2016

Rows with indices n in A033948 (or with A046144(n)=0) are empty.  Indices of nonempty rows are given by A033949.
This is A228179 without the trivial square roots {1, n-1}.
The number of terms in each nonempty row n is even: A060594(n)-2.

			Row n=8 contains 3 and 5 because 3*3 = 9 == 1 mod 8 and 5*5 = 25 == 1 mod 8.
Triangle T(n,k) begins:
08 :   3,  5;
12 :   5,  7;
15 :   4, 11;
16 :   7,  9;
20 :   9, 11;
21 :   8, 13;
24 :   5,  7, 11, 13, 17, 19;
28 :  13, 15;
30 :  11, 19;

Alois P. Heinz, Rows n = 1..5300, flattened

Columns k=1-2 give: A082568, A357099.
Last elements of nonempty rows give A277777.
Cf. A033948, A033949, A046144, A060594, A228179.

T:= n-> seq(`if`(i*i mod n=1, i, [][]), i=2..n-2):
seq(T(n), n=1..100);
# second Maple program:
T:= n-> ({numtheory[rootsunity](2, n)} minus {1, n-1})[]:
seq(T(n), n=1..100);

T[n_] := Table[If[Mod[i^2, n] == 1, i, Nothing], {i, 2, n-2}];
Select[Array[T, 100], # != {}&] // Flatten (* Jean-François Alcover, Jun 18 2018, from first Maple program *)

from itertools import chain, count, islice
from sympy.ntheory import sqrt_mod_iter
def A277776_gen(): # generator of terms
    return chain.from_iterable((sorted(filter(lambda m:1A277776_list = list(islice(A277776_gen(),30)) # Chai Wah Wu, Oct 26 2022

A302257 Number of minimal generating sets {x_1, x_2, ..., x_r} of (Z/nZ)* such that Product_{i=1..r} (x_i)^(e_i) == 1 (mod n) implies that (x_i)^(e_i) == 1 (mod n) for 1 <= i <= r. Here (Z/nZ)* is the multiplicative group of integers modulo n.

Original entry on oeis.org

1, 1, 1, 1, 2, 1, 2, 3, 2, 2, 4, 3, 4, 2, 8, 8, 8, 2, 6, 8, 12, 4, 10, 28, 8, 4, 6, 12, 12, 8, 8, 16, 24, 8, 32, 12, 12, 6, 32, 96, 16, 12, 12, 24, 32, 10, 22, 96, 12, 8, 32, 32, 24, 6, 64, 168, 36, 12, 28, 96, 16, 8, 144, 32, 192, 24, 20, 32, 60, 32, 24, 168, 24, 12, 64, 36, 96, 32

Offset: 1

Jianing Song, Apr 04 2018

nonn

Originally named "Decompose the multiplicative group of integers modulo n as a product of cyclic groups C_{k_1} X C_{k_2} X ... X C_{k_m}, where k_i divides k_j for i < j, then a(n) is the number of generating sets {x_k_i} where x_k_i generates C_{k_i}", which is incorrect for n = 35, 39, 45, 52, 55, ...
A minimal generating set of a finitely generated group G is defined as a generating set of G with the least elements. For n >= 3, the number of elements in the minimal generating sets of (Z/nZ)* (denoted by rank((Z/nZ)*)) is given in A046072. The multiplicative group of integers modulo 1 or 2 is the trivial group (has rank 0). The minimal generating set of it is the empty set, which also meets the condition by the convention empty product is 1. - Jianing Song, Jun 27 2018
Equivalently, number of sets {x_1, x_2, ..., x_r} (r = rank((Z/nZ)*)) such that a one-to-one mapping can be set between all products of the form Product_{i=1..r} (x_i)^(e_i) and the elements in (Z/nZ)*, where 0 <= e_i < ord(x_i,n) for 1 <= i <= r (so a necessary condition is that (Z/nZ)* = C_{ord(x_1,n)} X C_{ord(x_2,n)} X ... X C_{ord(x_r,n)}). Here ord(x,n) is the multiplicative order of x modulo n. Such sets are generalizations of primitive roots modulo n (for r = 1). For an element g in (Z/nZ)*, the corresponding e_1, e_2, ..., e_r can be seen as index of g under a given such set {x_1, x_2, ..., x_r} modulo n. For example, for n = 16 and a given such set {3, 15}, we have: 1 == 3^0 * 15^0 (mod 16), 3 == 3^1 * 15^0 (mod 16), 5 == 3^3 * 15^1 (mod 16), 7 == 3^2 * 15^1 (mod 16), 9 == 3^2 * 15^0 (mod 16), 11 == 3^3 * 15^0 (mod 16), 13 == 3^1 * 15^1 (mod 16), 15 == 3^0 * 15^1 (mod 16).
For any finite abelian multiplicative group G and a generating set (not necessarily minimal) S = {x_1, x_2, ..., x_m}, the property "Product_{i=1..m} (x_i)^(e_i) = o implies that (x_i)^(e_i) = o for i = 1..m" (o is the group identity) can be stated as "the elements in S are multiplicatively independent". If G is viewed as an additive group, then the corresponding property is "Sum_{i=1..m} (e_i)*(x_i) = o implies that (e_i)*(x_i) = o for i = 1..m", which can be stated as "the elements in S are linearly independent". For convenience, if the elements in S are multiplicatively independent, we call S a MIS. The link below lists some more general results for MISs. They concern only on finite abelian multiplicative groups but they also have their versions on additive groups. - Jianing Song, Mar 16 2019
Let S = {x_1, x_2, ..., x_r} be a minimal generating set of (Z/nZ)*, then S is a MIS iff all Dirichlet characters modulo n are generated when Chi(x_1), Chi(x_2), ..., Chi(x_r) run through their all possible values. If so, for an element g in (Z/nZ)*, g == Product_{i=1..r} (x_i)^(e_i) (mod n), we have Chi(g) = Product_{i=1..r} Chi(x_i)^(e_i). For example, if we choose {3, 15} as a minimal generating set of (Z/16Z)*, then all 8 Dirichlet characters modulo 16 are generated when Chi(3) runs through {1, -1, i, -i} and Chi(15) runs through {1, -1}. On the other hand, if S is not a MIS, it implies that some values for Chi(x_1), Chi(x_2), ..., Chi(x_r) cannot be taken. Since (x_i)^(e_i) == 1 (mod n) doesn't imply that (x_i)^(e_i) == 1 (mod n) for 1 <= i <= r, suppose that (x_1)^(e_1) !== 1 (mod n), letting Chi(x_1) = exp(2*Pi*i/ord(x_1,n)) and Chi(x_2) = Chi(x_3) = ... = Chi(x_r) = 1 results in 1 = Chi(1) = Product_{i=1..r} Chi(x_i)^(e_i) = Chi(x_1)^(e_1) = exp(2e_1*Pi*i/ord(x_1,n)) != 1, a contradiction. - Jianing Song, Jun 27 2018 [Revised by Jianing Song, Mar 16 2019]
The elements in one MIS that is minimal of (Z/nZ)* is given in the n-th row of A323021. All other such sets can be obtained using group isomorphisms and automorphisms. See Theorem 3 in the link. - Jianing Song, Mar 16 2019

			For n = 16, we're looking for generating sets {x_1, x_2} such that (x_1)^(e_1) * (x_2)^(e_2) == 1 (mod 16) implies (x_1)^(e_1) == (x_2)^(e_2) == 1 (mod 16). Since (Z/16Z)* = C_2 X C_4, we can suppose that ord(x_1,16) = 4 and ord(x_2,16) = 2, which gives a total of 8 sets: {3, 7}, {5, 7}, {11, 7}, {13, 7}, {3, 15}, {5, 15}, {11, 15} and {13, 15}, so a(16) = 8. Note that {3, 5} is not what we want because 3^2 * 5^2 == 1 (mod 16) but 3^2 == 5^2 == 9 (mod 16).
For n = 35, we're looking for generating sets {x_1, x_2} such that (x_1)^(e_1) * (x_2)^(e_2) == 1 (mod 35) implies (x_1)^(e_1) == (x_2)^(e_2) == 1 (mod 35). Since (Z/35Z)* = C_2 X C_12 = C_4 X C_6, we can suppose that ord(x_1,35) = 12 and ord(x_2,35) = 2 (for example {2, 6}), or ord(x_1,35) = 6 and ord(x_2,35) = 4 (for example {19, 8}), which gives a total of 32 sets, so a(35) = 32.

Jianing Song, Table of n, a(n) for n = 1..10000
Jianing Song, Some notes on the generating sets whose elements are multiplicatively independent (MISs)
Wikipedia, Multiplicative group of integers modulo n

Cf. A033948, A046072, A046144, A258615, A316089, A323021.

a(n) = A258615(n) * A316089(n) / (#znstar(n)[2])! \\ See A258615 and A316089 for their programs

For a given n, let r = rank((Z/nZ)*) (= A046072(n) for n >= 3), then a(n) = A258615(n)*A316089(n)/r!. See these two sequences for explicit formulae. - Jianing Song, Jun 27 2018

If n is a term in A033948 (i.e., (Z/nZ)* is cyclic; rank((Z/nZ)*) = 0 or 1), then a(n) = phi(A033948(n)) = A000010(A033948(n)) = A046144(n).

Typo corrected by Jianing Song, Jun 30 2018

More terms from Jianing Song, Jul 03 2018

A103336 Numbers whose largest primitive root (A046146) is not prime.

Original entry on oeis.org

1, 2, 11, 17, 19, 23, 29, 31, 37, 38, 41, 43, 47, 53, 58, 59, 62, 67, 71, 73, 74, 79, 81, 82, 83, 86, 89, 94, 97, 101, 107, 113, 118, 121, 122, 125, 127, 131, 134, 137, 139, 146, 149, 151, 157, 158, 162, 163, 167, 173, 178, 179, 191, 193, 194, 197, 211, 218, 223

Offset: 1

Harry J. Smith, Jan 31 2005

nonn

Amiram Eldar, Table of n, a(n) for n = 1..10000
Eric Weisstein's World of Mathematics, Primitive Root.

Cf. A001918, A046144, A046145, A046146, A103309, A103310, A103335, A103337, A103338.

Select[Range[250], #==1 || ((p = PrimitiveRootList[#]) != {} && ! PrimeQ[Max @ p]) &] (* Amiram Eldar, Sep 25 2021 *)

Offset corrected by Amiram Eldar, Sep 25 2021

A103337 Smallest primitive root of numbers in sequence A103335.

Original entry on oeis.org

0, 1, 6, 6, 6, 6, 6, 6, 10, 10, 21, 6, 21, 15, 15, 15, 15, 6, 6, 21, 15, 6, 6, 10, 14, 6, 6, 10, 6, 6, 6, 14, 6, 6, 10, 6, 6, 14, 10, 6, 21, 10, 35, 6, 6, 6, 15, 6, 6, 10, 21, 14, 6, 33, 6, 6, 10, 6, 6, 6, 10, 6, 22, 15, 15, 6, 10, 12, 6, 15, 15, 10, 14, 21, 6, 15, 6, 6, 6, 6, 6, 6, 6, 10, 10, 6

Offset: 1

Harry J. Smith, Jan 31 2005

nonn

Robert Israel, Table of n, a(n) for n = 1..10000
Eric Weisstein's World of Mathematics, Primitive Root.

Cf. A001918, A046144, A046145, A046146, A103309, A103310, A103335, A103336, A103338.

# given list A103335 as at that sequence
[0,seq(numtheory:-primroot(A103335[i]),i=2..nops(A103335))]; # Robert Israel, Sep 08 2020

Offset changed by Robert Israel, Sep 08 2020

A103338 Largest primitive root of numbers in sequence A103336.

Original entry on oeis.org

0, 1, 8, 14, 15, 21, 27, 24, 35, 33, 35, 34, 45, 51, 55, 56, 55, 63, 69, 68, 69, 77, 77, 75, 80, 77, 86, 91, 92, 99, 104, 110, 115, 117, 115, 123, 118, 128, 117, 134, 135, 141, 147, 146, 152, 153, 155, 159, 165, 171, 175, 176, 189, 188, 189, 195, 207, 207, 214

Offset: 1

Harry J. Smith, Jan 31 2005

nonn

Robert Israel, Table of n, a(n) for n = 1..10000
Eric Weisstein's World of Mathematics, Primitive Root.

Cf. A001918, A046144, A046145, A046146, A103309, A103310, A103335, A103336, A103337.

f:= proc(n) local m; uses NumberTheory;
  if n::odd then
    if NumberOfPrimeFactors(n,distinct) > 1 then return NULL fi;
  elif n mod 4 = 0 or NumberOfPrimeFactors(n,distinct) > 2 then return NULL
  fi;
  m:= PrimitiveRoot(n, ith=Totient(Totient(n)));
  if isprime(m) then NULL else m fi
end proc:
f(1):= 0:map(f, [$1..300]); # Robert Israel, Dec 01 2024

Offset changed by Robert Israel, Dec 01 2024

A219029 a(n) = n - 1 - phi(phi(n)).

Original entry on oeis.org

-1, 0, 1, 2, 2, 4, 4, 5, 6, 7, 6, 9, 8, 11, 10, 11, 8, 15, 12, 15, 16, 17, 12, 19, 16, 21, 20, 23, 16, 25, 22, 23, 24, 25, 26, 31, 24, 31, 30, 31, 24, 37, 30, 35, 36, 35, 24, 39, 36, 41, 34, 43, 28, 47, 38, 47, 44, 45, 30, 51, 44, 53, 50, 47, 48, 57, 46, 51, 48

Offset: 1

V. Raman, Nov 10 2012

sign

There are exactly n - 1 - phi(phi(n)) non-primitive roots for n, less than n, if n is prime.

a(n) will be the same as A219027(n) except when n is a member of A033949 or n = 1, i.e., n is not 2, 4, prime, power of a prime, twice a prime, or twice a prime power.

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

Cf. A008330 (number of primitive roots for the n-th prime).
Cf. A046144 (number of primitive roots for n).
Cf. A010554 (value of phi(phi(n))).
Cf. A219027, A219428.

[(n - 1 - EulerPhi(EulerPhi(n))): n in [1..70] ]; // Vincenzo Librandi, Jan 26 2013

Table[n - (EulerPhi[EulerPhi[n]] + 1), {n, 75}] (* Alonso del Arte, Nov 17 2012 *)

for(n=1,100,print1(n-1-eulerphi(eulerphi(n))","))

a(n) = n - 1 - A010554(n). - V. Raman, Nov 22 2012

A231772 Smallest positive number which has exactly n primitive roots, or 0 if no such number exists.

Original entry on oeis.org

8, 1, 5, 0, 11, 0, 19, 0, 17, 0, 23, 0, 29, 0, 0, 0, 41, 0, 81, 0, 67, 0, 47, 0, 53, 0, 0, 0, 59, 0, 0, 0, 97, 0, 0, 0, 109, 0, 0, 0, 83, 0, 0, 0, 139, 0, 0, 0, 113, 0, 0, 0, 107, 0, 163, 0, 0, 0, 0, 0, 199, 0, 0, 0, 137, 0, 0, 0, 0, 0, 0, 0, 149, 0, 0, 0, 0, 0

Offset: 0

Arkadiusz Wesolowski, Nov 13 2013

nonn

If n >= 3 and n is odd, then a(n) = 0.

T. D. Noe, Table of n, a(n) for n = 0..10000
Eric Weisstein's World of Mathematics, Primitive Root

Cf. A007617, A010554, A046144, A231773.

nn = 100; t = Join[{1}, Table[p = PrimitiveRoot[n]; If[IntegerQ[p], EulerPhi[EulerPhi[n]], 0], {n, 2, 2*nn}]]; Table[s = Position[t, n, 1, 1]; If[s == {}, 0, s[[1, 1]]], {n, 0, nn}] (* T. D. Noe, Nov 14 2013 *)

r=77; print1(8, ", ", 1, ", "); for(n=2, r, m=0; for(c=2*n+1, n^2+1, if(n%2==1, break); e=eulerphi(c); if(e==lcm(znstar(c)[2])&&eulerphi(e)==n, m=1; print1(c, ", "); break)); if(m==0, print1(0, ", ")));

A247176 Largest number of maximal order mod n.

Original entry on oeis.org

0, 1, 2, 3, 3, 5, 5, 7, 5, 7, 8, 11, 11, 5, 13, 13, 14, 11, 15, 17, 19, 19, 21, 23, 23, 19, 23, 23, 27, 23, 24, 29, 29, 31, 33, 31, 35, 33, 37, 37, 35, 31, 34, 41, 43, 43, 45, 43, 47, 47, 46, 45, 51, 47, 53, 53, 53, 55, 56, 53, 59, 55, 61, 61, 63, 61, 63, 65, 67, 67, 69, 67

Offset: 1

Eric Chen, Nov 29 2014

			a(18) = 11 because the largest possible order mod 18 is 6, and because 16, 15, 14, and 12 are not coprime to 18, and the orders of 17 and 13 to mod 18 are 2 and 3, not the largest possible order, and the order of 11 to mod 18 is 6, so a(18) = 11.

Eric Chen, Table of n, a(n) for n = 1..1000

Cf. A002322 (orders), same as A046146 for n with primitive roots, A071894 (for primes).

Cf. A111076, A111725, A046145, A046144, A001918, A008330.

prms={}; f[n_] = Block[If[MultiplicativeOrder[p, n]=CarmichaelLambda[n], Join[prms, p]]; prms[-1]]; Array[f, 128]

carmichaellambda(n)=lcm(znstar(n)[2]);
for(i=1, 128, p=0; for(q=1, i-1, if(gcd(q, i)==1&&znorder(Mod(q, i))==carmichaellambda(i), p=q)); print1(p", "))

a(68) corrected by Eric Chen, Jun 01 2015

A072209 Number of primitive roots of those integers with at least one primitive root.

Original entry on oeis.org

1, 1, 1, 1, 2, 1, 2, 2, 2, 4, 4, 2, 8, 2, 6, 4, 10, 8, 4, 6, 12, 8, 8, 12, 6, 16, 12, 10, 22, 12, 8, 24, 6, 12, 28, 16, 8, 20, 24, 24, 12, 24, 18, 16, 40, 12, 40, 22, 32, 12, 40, 32, 24, 52, 36, 48, 28, 40, 16, 40, 36, 48, 20, 64, 44, 24, 24, 72, 40, 48, 24, 18, 54

Offset: 1

Lekraj Beedassy, Jul 03 2002

Essentially sequence A046144 with all zero entries deleted.

T. D. Noe, Table of n, a(n) for n = 1..10000

Cf. A033948, A046144.

Reap[ Do[ If[n == 1, Sow[1], If[ IntegerQ[ PrimitiveRoot[n]], Sow[ EulerPhi[ EulerPhi[n]]]]] , {n, 1, 100}]][[2, 1]] (* Jean-François Alcover, Feb 24 2012 *)
Join[{1},(Length/@PrimitiveRootList[Range[300]])/.(0->Nothing)] (* Harvey P. Dale, Oct 01 2024 *)

is(n)=if(n%2, isprimepower(n) || n==1, n==2 || n==4 || (isprimepower(n/2, &n) && n>2));
lista(nn) = for (n=1, nn, if (is(n), print1(eulerphi(eulerphi(n)), ", "))); \\ Michel Marcus, May 12 2017

from sympy import primepi, integer_nthroot, totient
def A072209(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 totient(totient(bisection(f,n,n))) # Chai Wah Wu, Feb 24 2025

a(n) = phi(phi(A033948(n))).

A219028 Number of non-primitive roots for prime(n), less than prime(n).

Original entry on oeis.org

0, 1, 2, 4, 6, 8, 8, 12, 12, 16, 22, 24, 24, 30, 24, 28, 30, 44, 46, 46, 48, 54, 42, 48, 64, 60, 70, 54, 72, 64, 90, 82, 72, 94, 76, 110, 108, 108, 84, 88, 90, 132, 118, 128, 112, 138, 162, 150, 114, 156, 120, 142, 176, 150, 128, 132, 136, 198, 188, 184, 190

Offset: 1

V. Raman, Nov 10 2012

nonn

Harvey P. Dale, Table of n, a(n) for n = 1..1000

Cf. A008330 (number of primitive roots for the n-th prime, less than n-th prime).
Cf. A046144 (number of primitive roots for n, less than n).
Cf. A010554 (value of phi(phi(n))).

Table[c=Prime[n];c-1-EulerPhi[EulerPhi[c]],{n,70}] (* Harvey P. Dale, Feb 12 2013 *)

forprime(i=2,600,p=0;for(q=1,i-1,if(znorder(Mod(q,i))!=eulerphi(i),p++));print1(p","))

a(n) = p - 1 - phi(phi(p)), where p is the n-th prime.

a(n) = p - 1 - A008330(n) = p - 1 - A010554(p), where p is the n-th prime. - V. Raman, Nov 22 2012

cp's OEIS Frontend

A277776 Triangle T(n,k) in which the n-th row contains the increasing list of nontrivial square roots of unity mod n; n>=1.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Python

A302257 Number of minimal generating sets {x_1, x_2, ..., x_r} of (Z/nZ)* such that Product_{i=1..r} (x_i)^(e_i) == 1 (mod n) implies that (x_i)^(e_i) == 1 (mod n) for 1 <= i <= r. Here (Z/nZ)* is the multiplicative group of integers modulo n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

Formula

Extensions

A103336 Numbers whose largest primitive root (A046146) is not prime.

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

Extensions

A103337 Smallest primitive root of numbers in sequence A103335.

Views

Author

Keywords

Links

Crossrefs

Programs

Maple

Extensions

A103338 Largest primitive root of numbers in sequence A103336.

Views

Author

Keywords

Links

Crossrefs

Programs

Maple

Extensions

A219029 a(n) = n - 1 - phi(phi(n)).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Magma

Mathematica

PARI

Formula

A231772 Smallest positive number which has exactly n primitive roots, or 0 if no such number exists.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

A247176 Largest number of maximal order mod n.

Views

Author

Keywords

Examples

Links