A235863 -id:A235863 - cp's OEIS frontend

A235865 G-Carmichael numbers: Composite number such that A235863(n) divides A201629(n).

4, 8, 12, 15, 16, 20, 24, 32, 36, 40, 48, 56, 60, 64, 72, 80, 96, 100, 105, 108, 112, 120, 128, 132, 143, 144, 156, 160, 168, 180, 192, 200, 216, 224, 240, 255, 256, 264, 272, 280, 288, 300, 312, 320, 324, 336, 360, 380, 384, 385, 392, 396, 399, 400, 432

Offset: 1

José María Grau Ribas, Jan 16 2014

nonn

Andrew Howroyd, Table of n, a(n) for n = 1..1038
Jose María Grau, A. M. Oller-Marcen, Manuel Rodriguez and D. Sadornil, Fermat test with Gaussian base and Gaussian pseudoprimes, arXiv:1401.4708 [math.NT], 2014.

Cf. A235863, A201629.

FU[n_] := Which[Mod[n, 4] == 3, n + 1, Mod[n, 4] == 1, n - 1, True, n]; fa = FactorInteger; lam[1] = 1; lam[p_,s_] := Which[Mod[p, 4] == 3, p^(s - 1) (p + 1), Mod[p, 4] == 1, p^(s - 1) (p - 1), s ≥ 5, 2^(s -2), s > 1, 4, s == 1, 2]; lam[n_] := {aux = 1; Do[aux = LCM[aux, lam[fa[n][[i, 1]], fa[n][[i, 2]]]], {i, 1, Length[fa[n]]}]; aux}[[1]];Select[1+Range[1000], ! PrimeQ[#] && IntegerQ[FU[#]/lam[#]] &]

ok(n)={my(f=factor(n), r=n-kronecker( -4, n)); for(i=1, #f~, my([p, e]=f[i, ]); my(t=if(p==2, 2^max(e-2, min(e, 2)), p^(e-1)*if(p%4==1, p-1, p+1))); if(r%t, return(0)) ); n>1 && !isprime(n)} \\ Andrew Howroyd, Aug 06 2018

a(55) corrected by Andrew Howroyd, Aug 06 2018

A235867 G-cyclic numbers k such that A060968(k)^A060968(k) <> 1 (mod k) and A235863(k)^A235863(k) <> 1 (mod k).

Original entry on oeis.org

77, 119, 133, 187, 217, 253, 287, 301, 319, 323, 341, 391, 399, 403, 407, 413, 437, 469, 517, 551, 553, 559, 583, 589, 623, 651, 667, 707, 713, 731, 737, 749, 779, 781, 803, 817, 851, 869, 871, 889, 893, 899, 903, 913, 917, 935, 943, 959, 969, 1001, 1003

Offset: 1

José María Grau Ribas, Feb 22 2014

nonn

For G-cyclic numbers see A235866.

All terms are composite. - Bill McEachen, Jul 16 2021

Bill McEachen, Table of n, a(n) for n = 1..10000
Jose María Grau, A. M. Oller-Marcen, Manuel Rodriguez and D. Sadornil, Fermat test with Gaussian base and Gaussian pseudoprimes, arXiv:1401.4708 [math.NT], 2014.

Cf. A235866, A060968, A235863.

genit(maxx)={arr2=List();arr=List();for(ptr=1,maxx,if( gcd(ptr,A060968(ptr))==1,listput(arr,ptr)));for(ptr=2,#arr,n=arr[ptr];a=A060968(n)^A060968(n);b=A235863(n)^A235863(n);if(a%n!=1&&b%n!=1,listput(arr2,n)));}
A060968(n)={my(f=factor(n)[,1]);q=n*prod(i=if(n%2,1,2),#f,if(f[i]%4==1,1-1/f[i],1+1/f[i]))*if(n%4,1,2);return(q);} \\taken from that sequence
A235863(n)={my(f=factor(n));q=lcm(vector(#f~,i,my([p,e]=f[i,]);if(p==2,2^max(e-2,min(e,2)),p^(e-1)*if(p%4==1,p-1,p+1))));return (q);} \\taken from that sequence
\\ Bill McEachen, Jul 16 2021

A060968 Number of solutions to x^2 + y^2 == 1 (mod n).

Original entry on oeis.org

1, 2, 4, 8, 4, 8, 8, 16, 12, 8, 12, 32, 12, 16, 16, 32, 16, 24, 20, 32, 32, 24, 24, 64, 20, 24, 36, 64, 28, 32, 32, 64, 48, 32, 32, 96, 36, 40, 48, 64, 40, 64, 44, 96, 48, 48, 48, 128, 56, 40, 64, 96, 52, 72, 48, 128, 80, 56, 60, 128, 60, 64, 96, 128, 48, 96, 68, 128, 96, 64, 72

Offset: 1

Ahmed Fares (ahmedfares(AT)my-deja.com), May 09 2001

From Jianing Song, Nov 05 2019: (Start)
a(n) is also the order of the group SO(2,Z_n), i.e., the group of 2 X 2 matrices A over Z_n such that A*A^T = E = [1,0;0,1] and det(A) = 1. Elements in SO(2,Z_n) are of the form [x,y;-y,x] where x^2+y^2 == 1 (mod n). For example, SO(2,Z_4) = {[1,0;0,1], [0,1;3,0], [1,2;2,1], [2,1;3,2], [3,0;0,3], [0,3;1,0], [3,2;2,3], [2,3;1,2]}. Note that SO(2,Z_n) is abelian, and it is isomorphic to the multiplicative group G_n := {x+yi: x^2 + y^2 = 1, x,y in Z_n} where i = sqrt(-1), by the mapping [x,y;-y,x] <-> x+yi. See my link below for the group structure of SO(2,Z_n).
The exponent of SO(2,Z_n) (i.e., least e > 0 such that x^e = E for every x in SO(2,Z_n)) is given by A235863(n).
The rank of SO(2,Z_n) (i.e., the minimum number of generators) is omega(n) if n is not divisible by 4, omega(n)+1 if n is divisible by 4 but not by 8 and omega(n)+2 if n is divisible by 8, omega = A001221. (End)
In general, let R be any commutative ring with unity, O(m,R) be the group of m X m matrices A over R such that A*A^T = E and SO(m,R) be the group of m X m matrices A over R such that A*A^T = E and det(A) = 1, then O(m,R)/SO(m,R) = {square roots of unity in R*}, where R* is the multiplicative group of R. This is because if we define f(M) = det(M) for M in O(m,R), then f is a surjective homomorphism from O(m,R) to {square roots of unity in R*}, and SO(m,R) is its kernel. See also A182039. - Jianing Song, Nov 08 2019

			a(3) = 4 because the 4 solutions are (0,1), (0,2), (1,0), (2,0).

Charles R Greathouse IV, Table of n, a(n) for n = 1..10000
Jianing Song, Structure of the group SO(2,Z_n).
László Tóth, Counting solutions of quadratic congruences in several variables revisited, arXiv preprint arXiv:1404.4214 [math.NT], 2014.
László Tóth, Counting Solutions of Quadratic Congruences in Several Variables Revisited, J. Int. Seq. 17 (2014), Article 14.11.6.

Cf. A006752, A060594, A087784.
Cf. A027748, A124010.
Cf. A235863, A182039.

a060968 1 = 1
a060968 n = (if p == 2 then (if e == 1 then 2 else 2^(e+1)) else 1) *
   (product $ zipWith (*) (map (\q -> q - 2 + mod q 4) ps'')
                          (zipWith (^) ps'' (map (subtract 1) es'')))
   where (ps'', es'') = if p == 2 then (ps, es) else (ps', es')
         ps'@(p:ps) = a027748_row n; es'@(e:es) = a124010_row n
-- Reinhard Zumkeller, Aug 05 2014

fa=FactorInteger; phi[p_,s_] := Which[Mod[p,4] == 1, p^(s-1)*(p-1), Mod[p,4]==3, p^(s-1)*(p+1), s==1, 2, True, 2^(s+1)]; phi[1]=1; phi[n_] := Product[phi[fa[n][[i,1]], fa[n][[i,2]]], {i, Length[fa[n]]}]; Table[phi[n], {n,1,100}]

a(n)=my(f=factor(n)[,1]);n*prod(i=if(n%2,1,2),#f,if(f[i]%4==1, 1-1/f[i], 1+1/f[i]))*if(n%4,1,2) \\ Charles R Greathouse IV, Apr 16 2012

Multiplicative, with a(2^e) = 2 if e = 1 or 2^(e+1) if e > 1, a(p^e) = (p-1)*p^(e-1) if p == 1 (mod 4), a(p^e) = (p+1)*p^(e-1) if p == 3 (mod 4). - David W. Wilson, Jun 19 2001
a(n) = n * (Product_{prime p|n, p == 1 (mod 4)} (1 - 1/p)) * (Product_{prime p|n, p == 3 (mod 4)} (1 + 1/p)) * (1 + [4|n]) where "[ ]" is the Iverson bracket. - Ola Veshta (olaveshta(AT)my-deja.com), May 18 2001
a(n) = A182039(n)/A060594(n). - Jianing Song, Nov 08 2019
Sum_{k=1..n} a(k) ~ c * n^2 + O(n*log(n)), where c = 5/(8*G) = 0.682340..., where G is Catalan's constant (A006752) (Tóth, 2014). - Amiram Eldar, Oct 18 2022

A182039 Order of the group O(2,Z_n); number of orthogonal 2 X 2 matrices over the ring Z/nZ.

Original entry on oeis.org

1, 2, 8, 16, 8, 16, 16, 64, 24, 16, 24, 128, 24, 32, 64, 128, 32, 48, 40, 128, 128, 48, 48, 512, 40, 48, 72, 256, 56, 128, 64, 256, 192, 64, 128, 384, 72, 80, 192, 512, 80, 256, 88, 384, 192, 96, 96, 1024, 112, 80, 256, 384, 104, 144, 192, 1024, 320, 112, 120, 1024, 120, 128, 384, 512, 192, 384, 136, 512, 384, 256, 144, 1536

Offset: 1

José María Grau Ribas, Apr 07 2012

Number of matrices M = [a,b;c,d] with 0 <= a,b,c,d < n such that M*transpose(M) == [1,0;0,1] (mod n).
From Jianing Song, Nov 05 2019: (Start)
Elements in O(2,Z_n) are of the form [x,y;-ty,tx], where x^2+y^2 == 1 (mod n), t^2 == 1 (mod n). Proof: If n = Product_{i=1..k} (p_i)^(e_i), then it can be shown by the Chinese Remainder Theorem that O(2,Z_n) is isomorphic to Product_{i=1..k} O(2,Z_(p_i)^(e_i)), so we can just study the elements in O(2,Z_p^e).
Let M = [x,y;z,w] be such a matrix; according to the conditions we have x^2+y^2 == z^2+w^2 == 1 (mod p^e), x*z+y*w == 0 (mod p^e). Here at least one of x,y is coprime to p^e, otherwise x^2+y^2 cannot be congruent to 1 mod p^e. If gcd(x,p^e) = 1, let t = x^(-1)*w; if gcd(y,p^e) = 1, let t = -y^(-1)*z (if gcd(x,p^e) = gcd(y,p^e) = 1 then these two t's are the same), then M = [x,y;-ty,tx] with determinant t, so t^2 == 1 (mod p^e). Specially, the elements in SO(2,Z_n) are of the form [x,y;-y,x], as the determinant is restricted to 1 mod n. See also A060968.
Note that O(2,Z_n) is non-abelian when n > 2: [0,1;-1,0] * [-1,0;0,1] = [0,1;1,0], but [-1,0;0,1] * [0,1;-1,0] = [0,-1;-1,0].
In general, let R be any commutative ring with unity, O(m,R) be the group of m X m matrices M over R such that M*M^T = I and SO(m,R) be the group of m X m matrices M over R such that M*M^T = I and det(M) = 1, then O(m,R)/SO(m,R) is isomorphic to {square roots of unity in R*}, where R* is the multiplicative group of R. This is because if we define f(M) = det(M) for M in O(m,R), then f is a surjective homomorphism from O(m,R) to {square roots of unity in R*}, and SO(m,R) is its kernel. Here, O(2,Z_n) is the internal semiproduct of SO(2,Z_n) and {[a,0;0,1]: a^2 = 1}. As a result:
If p is an odd prime or p^e = 4, then O(2,Z_p^e) is the internal semiproduct of SO(2,Z_p^e) and {I, P}, where I = [1,0;0,1] and P = [-1,0;0,1]. For any M in SO(2,Z_p^e), we have P*M*P = M^(-1). For odd primes p, O(2,Z_p^e) is, in fact, isomorphic to the dihedral group D_(2*(p+1)*p^(e-1)) if p == 3 (mod 4) and D_(2*(p-1)*p^(e-1)) if p == 1 (mod 4), since SO(2,Z_p^e) is cyclic as discussed in A060968. O(2,Z_4) is isomorphic to D_8 X C_2.
If e >= 3, then O(2,Z_2^e) is the internal semiproduct of SO(2,Z_2^e) and {I, P, Q, P*Q}, where I = [1,0;0,1], P = [-1,0;0,1] and Q = [2^(e-1)+1,0;0,1]. For any M in SO(2,Z_2^e), we have P*M*P = M^(-1); Q*M*Q = M if the upper-right entry of M is even, (2^(e-1)+1)*M otherwise.
The exponent of O(2,Z_n) (i.e., least e > 0 such that M^e = I for every M in O(2,Z_n)) is given by A235863(n).
The rank of O(2,Z_n) (i.e., the minimum number of generators) is 2*omega(n) if n is odd, 2*omega(n)-1 if n is even but not divisible by 4, 2*omega(n)+1 if n is divisible by 4 but not by 8 and 2*omega(n)+3 if n is divisible by 8, omega = A001221.
(End) [Comment partly rewritten by Jianing Song, Oct 09 2020]

			a(1) = 1 because 1 = 0 in the zero ring, so although there only exists the zero matrix, it still equals the unit matrix.
O(2,Z_6) = {[0,1;5,0], [0,1;1,0], [0,5;1,0], [0,5;5,0], [1,0;0,1], [1,0;0,5], [2,3;3,2], [2,3;3,4], [3,2;4,3], [3,2;2,3], [3,4;2,3], [3,4;4,3], [4,3;3,4], [4,3;3,2], [5,0;0,5], [5,0;0,1]}, so a(6) = 16.
For n = 16, SO(2,Z_16) is generated by [9,0;0,9], [0,1;-1,0], and [4,1;-1,4] (see Jianing Song link in A060968), so O(2,Z_16) is generated by [-1,0;0,1], [9,0;0,1], [9,0;0,9], [0,1;-1,0], and [4,1;-1,4], which gives O(2,Z_16) is isomorphic to the semiproduct of C_2 X C_4 X C_4 and C_2 X C_2, so a(16) = 128.

Jianing Song, Table of n, a(n) for n = 1..10000 (first 1000 terms from Joerg Arndt)

Cf. A060968 (order of SO(2,Z_n)), A060594, A235863, A001221, A209411.

gg[n_]:=gg[n]=Flatten[Table[{{x,y},{z,t}},{x,n},{y,n},{t,n},{z,n}],3];
orto[1]=1;
orto[n_]:=orto[n]=Length@gg[n][[Select[Range[Length[gg[n]]],Mod[gg[n][[#]].Transpose[gg[n][[#]]],n]=={{1,0},{0,1}}&]]];
Table[Print[orto[n]];orto[n],{n,1,22}]

a(n)=
{
    my(r=1, f=factor(n));
    for(j=1, #f[, 1], my(p=f[j, 1], e=f[j, 2]);
        if(p==2 && e==1, r*=2);
        if(p==2 && e==2, r*=16);
        if(p==2 && e>=3, r*=2^(e+3));
        if(p%4==1, r*=2*(p-1)*p^(e-1));
        if(p%4==3, r*=2*(p+1)*p^(e-1));
    );
    return(r);
}
\\ Jianing Song, Nov 05 2019

From Jianing Song, Nov 05 2019: (Start)
a(n) = A060968(n) * A060594(n).
Multiplicative with a(2) = 2, a(4) = 16, a(2^e) = 2^(e+3) for e >= 3; a(p^e) = 2*(p-1)*p^(e-1) if p == 1 (mod 4), 2*(p+1)*p^(e-1) if p == 3 (mod 4).
(End)

Terms beyond a(22) from Joerg Arndt, Apr 13 2012

a(1) changed to 1 by Andrey Zabolotskiy, Nov 13 2019

A235864 G-Lehmer numbers: Composite numbers k such that A060968(k) divides A201629(k).

Original entry on oeis.org

15, 143, 255, 385, 3599, 5183, 11663, 32399, 34561, 36863, 51983, 57599, 65535, 97343, 121103, 147455, 176399, 186623, 195841, 359999, 435599, 685583, 1034881, 1040399, 1065023, 1192463, 1327103, 1742399, 2039183, 2108303, 2214143, 2585663, 2624399, 2782223, 3196943

Offset: 1

José María Grau Ribas, Jan 16 2014

nonn

Amiram Eldar, Table of n, a(n) for n = 1..1000
José María Grau, Antonio M. Oller-Marcén, Manuel Rodríguez, and Daniel Sadornil, Fermat test with Gaussian base and Gaussian pseudoprimes, Czechoslovak Mathematical Journal, Vol. 65 (2015), pp. 969-982; arXiv preprint, arXiv:1401.4708 [math.NT], 2014.

Cf. A060968, A201629, A235863, A182140.

fa=FactorInteger; phi[p_, s_] := Which[Mod[p, 4] == 1, p^(s-1)*(p-1), Mod[p, 4]==3, p^(s-1)*(p+1), s==1, 2, True, 2^(s+1)]; phi[1]=1; phi[n_] := Product[phi[fa[n][[i, 1]], fa[n][[i, 2]]], {i, Length[fa[n]]}]; Select[Range[1000], IntegerQ[FU[#]/phi[#]] && PrimeQ[#] == False &]

a(29)-a(35) from Amiram Eldar, Nov 24 2023

A235868 Union of 2 and powers of odd primes.

Original entry on oeis.org

1, 2, 3, 5, 7, 9, 11, 13, 17, 19, 23, 25, 27, 29, 31, 37, 41, 43, 47, 49, 53, 59, 61, 67, 71, 73, 79, 81, 83, 89, 97, 101, 103, 107, 109, 113, 121, 125, 127, 131, 137, 139, 149, 151, 157, 163, 167, 169, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229

Offset: 1

José María Grau Ribas, Feb 23 2014

nonn

Numbers n such that the group G_n:={x+yi: x^2+y^2==1 (mod n); 0<=x,yA060968(n) = A235863(n).

Jose María Grau, A. M. Oller-Marcen, Manuel Rodriguez and D. Sadornil, Fermat test with Gaussian base and Gaussian pseudoprimes, arXiv:1401.4708 [math.NT], 2014.

Cf. A060968, A061345, A235863.

Select[ Range[230], # == 2 || Mod[#, 2] == 1 && PrimeNu[#] < 2 &] (* and modified by Robert G. Wilson v, Dec 29 2016 *)

{2} UNION A061345. - R. J. Mathar, Jul 19 2024

cp's OEIS Frontend

A235865 G-Carmichael numbers: Composite number such that A235863(n) divides A201629(n).

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

PARI

Extensions

A235867 G-cyclic numbers k such that A060968(k)^A060968(k) <> 1 (mod k) and A235863(k)^A235863(k) <> 1 (mod k).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

PARI

A060968 Number of solutions to x^2 + y^2 == 1 (mod n).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Haskell

Mathematica

PARI

Formula

A182039 Order of the group O(2,Z_n); number of orthogonal 2 X 2 matrices over the ring Z/nZ.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions

A235864 G-Lehmer numbers: Composite numbers k such that A060968(k) divides A201629(k).

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

Extensions

A235868 Union of 2 and powers of odd primes.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

Formula