A206549 Nontrivial solution of x^2 == 1 (Modd p), where p is the n-th prime of the form 4*k+1, for odd restricted residue classes Modd p.

3, 5, 13, 17, 31, 9, 23, 11, 27, 55, 75, 91, 33, 15, 37, 105, 129, 93, 19, 81, 183, 107, 89, 177, 241, 187, 217, 53, 155, 25, 203, 189, 213, 311, 269, 115, 63, 381, 143, 29, 179, 67, 109, 413, 301, 235, 489, 439, 483, 553

Offset: 1

Author

Wolfdieter Lang, Feb 13 2012

Keywords

• nonn

Comments

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

Examples

			a(6)=9 because the corresponding prime is A002144(6)=41, 9^2 = 81, and 81 Modd 41 is per definition -81 mod 2*41 = +1 (the definition uses the parity of floor(81/41) = 1 being odd, hence the - sign), thus 9^2 == 1 (Modd 41), and 9 is not congruent to 1 (Modd 41) (or -1 (Modd 41)), hence a nontrivial solution.
A002144(n):  5, 13, 17, 29, 37, 41, 53, 61, 73, 89, 97, ...
a(n):        3,  5, 13, 17, 31,  9, 23, 11, 27, 55, 75, ...
3^2 = 9, 9 Modd 5 := -9 mod 10 = 1, the smallest positive representative of the class 1 (Modd 5) = {+-1,+-9,+-11,+-19,...}.
5^2 = 25, 25 Modd 13 := -25 mod 26 = 1.
13^2 = 169, 169 Modd 17 := -169 mod 34 = 1.
17^2 = 289, 289 Modd 29 := -289 mod 2*29 = 1.
...
E.g., for the odd prime 7, not in A002144, there are no self-inverse elements in the multiplicative group Modd 7 (on the odd numbers) except the trivial 1. The inverse of 3 is 5 (Modd 7) and vice versa, since 3*5 = 15 and 15 Modd 7 := 15 mod 14 = 1. (*)
From _Rémi Guillaume_, Sep 08 2024: (Start)
(*) The finite multiplicative group Modd 7 (on the odd residue classes) is of odd order: (7-1)/2 = 3, and is isomorphic to the additive cyclic group Z_3. Moreover, Z_3 has two generating elements: [1] and [2] (mod 3), and no nontrivial self-opposite elements -- since [1]+[2] = [0] (mod 3); likewise, {[1],[3],[5]} (Modd 7) has two generating elements: [3] and [5] (Modd 7), and no nontrivial self-inverse elements -- since [3]*[5] = [1] (Modd 7).
13 is an odd prime in A002144; the finite multiplicative group Modd 13 (on the odd residue classes) is of even order: (13-1)/2 = 6 = 2*3, and is isomorphic to the additive cyclic group Z_6. Moreover, Z_6 has two generating elements: [1] and [5] (mod 6), and one nontrivial self-opposite element: 3*[1] = 3*[5] = [3] (mod 6) -- since [1]+[5] = [2]+[4] = 2*[3] = [0] (mod 6); likewise, {[1],[3],[5],[7],[9],[11]} (Modd 13) has two generating elements: [7] and [11] (Modd 13), and one nontrivial self-inverse element: [7]^3 = [11]^3 = [5] (Modd 13) -- since [3]*[9] = [5]^2 = [7]*[11] = [1] (Modd 13).
17 is an odd prime in A002144; the finite multiplicative group Modd 17 (on the odd residue classes) is of even order: (17-1)/2 = 8 = 2*4, and is isomorphic to the additive cyclic group Z_8. Moreover, Z_8 has four generating elements: [1], [3], [5], [7] (mod 8), and one nontrivial self-opposite element: 4*[1] = 4*[3] = 4*[5] = 4*[7] = [4] (mod 8) -- since [1]+[7] = [2]+[6] = [3]+[5] = 2*[4] = [0] (mod 8); likewise, {[1],[3],[5],[7],[9],[11],[13],[15]} (Modd 17) has four generating elements: [3], [5], [7], [11] (Modd 17), and one nontrivial self-inverse element: [3]^4 = [5]^4 = [7]^4 = [11]^4 = [13] (Modd 17) -- since [3]*[11] = [5]*[7] = [9]*[15] = [13]^2 = [1] (Modd 17).
(End)
		

Links

• Rémi Guillaume, Calculations supporting my examples & showing that multiplication can be done class-wise

Crossrefs

See A203571 for Modd n, A002144 for corresponding primes.

Formula

a(n)^2 == 1 (Modd A002144(n)), n>=1, a(n) the smallest positive solution not 1. For Modd p, p an odd prime, see the comment section and the examples.