cp's OEIS Frontend

For multiplication Modd n (not to be confused with multiplication mod n) see a comment on A203571.

The trivial solution of x^2 == 1 (Modd n) is x = 1 (Modd n). Note that x = -1 (Modd n) == +1 (Modd n). In the ordinary mod n case the trivial solution is 1 (mod 2) for n=2 (-1 == +1 (mod 2)) and if n>2 the two trivial solutions are 1 (mod n) and the noncongruent -1 (mod n) == n-1 (mod n).

Here multiplication on the reduced residue system Modd p, p an odd prime, with only odd numbers is considered (which is possible, contrary to mod p). In order to have inverses one has to exclude all reduced residue classes Modd p with even numbers. The (p-1)/2 residue classes are then [1],[3],...,[p-2]. For m=1,3,...,p-2, the class [m] Modd p is the union of the ordinary reduced residue classes mod 2p: [m] and [-m]=[2p-m]. Besides the trivial solution x=+1 (Modd p) (note that -1 == +1 (Modd p)) there is a further nontrivial solution if and only if (p-1)/2 is even, i.e. p=A002144(n) (primes of the form 4*k+1), n>=1. The present sequence entry a(n) gives the smallest positive representative for this nontrivial solution Modd A002144(n).

This result uses the fact that every finite group of prime order p is the cyclic group Z_p (Corollary to Lagrange's or also Cauchy's theorem on finite groups or see A000688 for abelian groups). Here for the multiplicative group Modd p (on the odd residue classes) which has order (p-1)/2, for p an odd prime. This turns out to be the Galois group for the minimal polynomial C(p,x), whose coefficients are found in A187360. The sequence {a(n)} arises if one asks for the smallest positive members of the odd restricted residue system Modd p, namely [1],[3],...,[p-2], which are their own inverses besides the trivial element 1 (Modd p).

The row a(n) has in the table for the multiplicative group Modd A002144(n) a 1 on the diagonal, if the table is written for the odd representatives 1,3,...,p-2. The only other diagonal entry 1 appears for the element 1. Note that in the ordinary mod p case, p an odd prime, one always has for the multiplicative group mod p (which has p-1 residue classes) in the multiplication table the diagonal entry 1 only for the representatives 1 and p-1, but p-1 == -1 (mod p) is a trivial solution of x^2 == 1 (mod p).

Equivalently, primes of the form (K^2 + (K+1)^2)/5. The connection to the primes of the form (m^2+1)/10 is given by m=2*K+1 (m is necessarily odd). The corresponsding m=m(n) values are given in A002733(n).

Equivalently, primes of the form (4*T(K)+1)/5, with the corresponding triangular numbers T(K):=A000217(K), for K(n)=(m(n)-1)/2, given in A207339(n).

For n>=2 the smallest positive representative of the class of nontrivial solutions of the congruence x^2==1 (Modd a(n)) is x=m(n). The trivial solution is the class with representative x=1, which also includes -1. For the prime a(1)=5 the smallest positive nontrivial solution is 3 (see A027862(1) with A002731(1)). Such a nontrivial smallest positive representative exists for each unique class of solutions of this congruence Modd p for any prime p of the form 4*k+1, given in A002144. Here the subset with k=k(n)=(a(n)-1)/4 appears, namely 1, 4, 7, 13, 18, 27, 34, 70,... For Modd n see a comment on A203571.

Sequence consists of 2 and the union of the Mersenne primes (A000668) and the Fermat primes (A019434).

a(18) has 157 digits and is too large to include. - Ray Chandler, Jun 22 2009

From Wolfdieter Lang, Mar 28 2012: (Start)

The sequence of exponents k of 2 for these Mersenne or Fermat primes is k=[0, 1, 2, 3, 4, 5, 7, 8, 13, 16, 17, 19, 31, 61, 89, 107, 127,...], n>=1, if 3 is considered as Fermat prime.

The second exponent is 2 if 3 is considered as Mersenne prime. The next exponent k(18)=521 for the Mersenne prime a(18).

r(a(n)) := sqrt(a(n)*2^(k(n)+2) + 1) is a solution of the congruence x^2 == 1 (mod a(n)*2^(k(n)+1)), n>=1. The sequence k is given in the preceding comment. If n=2 then, besides r(3) = 5, also sqrt(3*2^(2+2) + 1) = 7 is an incongruent solution mod 12 if the exponent 2 is chosen. For n=2 there are altogether four incongruent solutions of x^2 == 1 (mod 12), namely 1, 12-1 = 11, r(3)=5 and 12-5 = 7. If n=1 there are altogether two incongruent solutions, namely 1 and r(2) = 3 = 4-1 (a trivial solution == -1 (mod 4)). For n>=3 there are eight incongruent solutions, and besides the trivial (positive) ones, 1 and a(n)*2^(k(n)+1) - 1, one has a nontrivial pair r(a(n)) and a(n)*2^(k(n)+1) - r(a(n)). For the number of incongruent solutions of the congruence x^2 == 1 (mod n) see A060594. For the r(a(n)) values see A210844.

r(a(n)), n>=1, also solves the congruence x^2 == 1 (Modd a(n)*2^(k(n)+1)), because floor((r(a(n))^2)/(a(n)*2^(k(n)+1)) is even. For Modd n (not to be confused with mod n) see a comment on A203571.

(End)

This sequence can be continued periodically for negative values of n.

See a comment on A203571 where a k-family of 2k-periodic sequences P_k has been defined. The present sequence is P_4. - Wolfdieter Lang, Feb 02 2012

The length of row n is delta(n) = A055034(n).

Here the smallest nonnegative complete system modulo n is used: {0,1,...,n-1}, and the reduced residue system modulo n (A038566) is the set of numbers k from this set which satisfy gcd(k, n) = 1. The present array lists only the odd numbers. For n = 1 one should take 0 because gcd(0, 1) = 1, but because 1 == 0 (mod 1) we prefer the odd 1.

This is the sub-array obtained from A038566 by deleting the even numbers.

In the multiplicative group Modd n (see a comment in A203571) each of the delta(n) members of row n forms a reduced residue class Modd n with only odd numbers. E.g., n=4 (only the positive members are listed, the negative members should be amended): [1] = {1, 7, 9, 15, 17, 23, 25, 31, 33, 39,...}; [3] = {3, 5, 11, 13, 19, 21, 27, 29, 35, 37...}. Multiplication Modd n can be done class-wise: 7*15 == 1*1 (Modd 4) = 1; 11*13 ==3*3 (Modd 4) = 1; 7*5 == 1*3 (Modd 4) = 3.

The orders 'Moddulo' n of the elements in row n are given in A216320.

This sequence can be continued periodically for negative values of n, and then a(-n) = a(n).

This is the seventh sequence of a k-family of sequences P_k, k>=1, which starts with A000007(n+1), n>=0, (the 0-sequence), A000035, A193680, A193682, A203572, A for k=1..6, respectively.

See a comment on A203571 for the general case of the P_k sequences. For a(n)=P_7(n) the nonnegative members of the equivalence classes [0], [1],...,[6], defined by p==q iff P_7(p)=P_7(q), are found in the array A113807 if there the last class [7], starting with 7, is replaced by 0,7,14,..., to become the first class [0] (nonnegative part).

For multiplication Modd n (not to be confused with mod n) see a comment on A203571.

The 0 for n=1 is a primitive root Modd 1, the other zeros indicate that there is no primitive root for this n.

Iff a(n)>0, for n>=2, then the Galois group Gal(Q(2*cos(Pi/n))/Q), which is the multiplicative group of odd reduced residue classes Modd n (hence the notation Modd) is cyclic. For n=1 this group is also cyclic. See A206551 (cyclic moduli n) and A206552 (acyclic, i.e. non-cyclic, moduli n). [Changed by Wolfdieter Lang, Apr 04 2012]

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.

The length of row n is delta(n):=A055034(n).

For the multiplicative group Modd n see a comment on A203571, and also on A216319.

A216319(n,k)^a(n,k) == +1 (Modd n), n >= 1.

If the Modd n order of an (odd) element from row n of A216319 is delta(n) (the row length) then this element is a primitive root Modd n. There is no primitive root Modd n if no such element of order delta(n) exists. For example, n = 12, 20, ... (see A206552 for more of these n values). There are phi(delta(n)) = A216321(n) such primitive roots Modd n if there exists one, where phi=A000010 (Euler's totient). The multiplicative group Modd n is cyclic if and only if there exists a primitive root Modd n. The multiplicative group Modd n is isomorphic to the Galois group G(Q(rho(n))/Q) with the algebraic number rho(n) := 2*cos(Pi/n), n>=1.

Contribution from Wolfdieter Lang, Feb 27 2012: (Start)

The corresponding primes (n^2 + 1)/10 are given in A207337(n).

a(n) is the smallest positive representative of the class of nontrivial solutions of the congruence x^2 == 1 (Modd A207337(n)), if n >= 2. The trivial solution is the class with representative x=1, which also includes -1. For Modd n see a comment on A203571. For n=1: a(1) = 7 == 3 (Modd 5), and 3 is the smallest positive solution > 1.

The unique class of nontrivial solutions of the congruence x^2 == 1 (Modd p), with p an odd prime, exists for any p of the form 4*k+1, given in A002144. Here a subset of these primes is covered, the ones for k = k(n) = (a(n)^2 - 9)/40. These k-values are [1, 4, 7, 13, 18, 27, 34, 70, 99, 112, ...].

(End)