A087726 Number of elements X in the matrix ring M_2(Z_n) such that X^2 == 0 mod n.

1, 4, 9, 28, 25, 36, 49, 112, 153, 100, 121, 252, 169, 196, 225, 640, 289, 612, 361, 700, 441, 484, 529, 1008, 1225, 676, 1377, 1372, 841, 900, 961, 2560, 1089, 1156, 1225, 4284, 1369, 1444, 1521, 2800, 1681, 1764, 1849, 3388, 3825, 2116, 2209, 5760, 4753, 4900, 2601, 4732

Offset

1,2

Comments

Conjecture: a(n)=n^2 if and only if n is squarefree. [Ben Branman, Mar 22 2013]

Preceding conjecture is true in the case where n is squarefree. - Eric M. Schmidt, Mar 23 2013

It appears that a(p^k) = (1+3*p^2 + 2*k*(p^2-1) + (-1)^k*(p^2-1))*p^(2*k-2)/4 for primes p. Since the sequence is multiplicative, this would imply the conjecture. - Robert Israel, Jun 10 2015

A proof of the formula for k=1 can be done easily (see pdf). - Manfred Scheucher, Jun 10 2015

Links

Manfred Scheucher, Table of n, a(n) for n = 1..1000

Manfred Scheucher, A proof of the formula for k=1

Maple

f:= proc(n)
  local tot, S, a, mult, sa, d, ad, g, cands;
  tot:= 0;
  S:= ListTools:-Classify(t -> t^2 mod n, [$0..n-1]);
  for a in numtheory:-divisors(n) do
    mult:= numtheory:-phi(n/a);
    sa:= a^2 mod n;
    for d in S[sa] do
       g:= igcd(a+d, n);
       cands:= [seq(i*n/g, i=0..g-1)];
       tot:= tot + mult * numboccur(sa, [seq(seq(s*t, s=cands), t=cands)] mod n);
    od
  od;
  tot
end proc:
map(f, [$1..100]); # Robert Israel, Jun 09 2015

Mathematica

a[m_] := Count[Table[Mod[MatrixPower[Partition[IntegerDigits[n, m, 4], 2], 2], m] == {{0, 0}, {0, 0}}, {n, 0, m^4 - 1}], True]; Table[a[n], {n, 2, 30}] (* Ben Branman, Mar 22 2013 *)

Prog

(C)
#include<stdio.h>
#include<stdlib.h>
int main(int argc, char** argv)
{
  long ct = 0;
  int n = atoi(argv[1]);
  int a, b, c, d;
  for(a=0; a<n; a++)
  {
    for(b=0; b<n; b++)
    {
      for(c=0; c<n; c++)
      {
if((a*a+b*c)%n != 0) continue;
for(d=0; d<n; d++)
{
if((b*c+d*d)%n != 0) continue;
if((a*b+b*d)%n != 0) continue;
if((c*a+d*c)%n != 0) continue;
ct++;
}
      }
    }
  }
  printf("%d %ld\n", n, ct);
  return 0;
}
/* Manfred Scheucher, Jun 09 2015 */

Crossrefs

Cf. A066907, A000188.

Sequence in context: A272089 A270720 A272280 * A270891 A272313 A239668

Adjacent sequences: A087723 A087724 A087725 * A087727 A087728 A087729

Keyword

mult,nonn

Author

Yuval Dekel (dekelyuval(AT)hotmail.com), Sep 28 2003

Extensions

More terms from Ben Branman, Mar 22 2013

More terms from Manfred Scheucher, Jun 09 2015

Status

approved