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

%I #27 Jun 11 2015 19:56:08

%S 1,4,9,28,25,36,49,112,153,100,121,252,169,196,225,640,289,612,361,

%T 700,441,484,529,1008,1225,676,1377,1372,841,900,961,2560,1089,1156,

%U 1225,4284,1369,1444,1521,2800,1681,1764,1849,3388,3825,2116,2209,5760,4753,4900,2601,4732

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

%C Conjecture: a(n)=n^2 if and only if n is squarefree. [_Ben Branman_, Mar 22 2013]

%C Preceding conjecture is true in the case where n is squarefree. - _Eric M. Schmidt_, Mar 23 2013

%C 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

%C A proof of the formula for k=1 can be done easily (see pdf). - _Manfred Scheucher_, Jun 10 2015

%H Manfred Scheucher, <a href="/A087726/b087726.txt">Table of n, a(n) for n = 1..1000</a>

%H Manfred Scheucher, <a href="/A087726/a087726_4.pdf">A proof of the formula for k=1</a>

%p f:= proc(n)

%p local tot, S, a, mult, sa, d, ad, g, cands;

%p tot:= 0;

%p S:= ListTools:-Classify(t -> t^2 mod n, [$0..n-1]);

%p for a in numtheory:-divisors(n) do

%p mult:= numtheory:-phi(n/a);

%p sa:= a^2 mod n;

%p for d in S[sa] do

%p g:= igcd(a+d,n);

%p cands:= [seq(i*n/g, i=0..g-1)];

%p tot:= tot + mult * numboccur(sa,[seq(seq(s*t,s=cands),t=cands)] mod n);

%p od

%p od;

%p tot

%p end proc:

%p map(f, [$1..100]); # _Robert Israel_, Jun 09 2015

%t 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 *)

%o (C)

%o #include<stdio.h>

%o #include<stdlib.h>

%o int main(int argc,char** argv)

%o {

%o long ct = 0;

%o int n = atoi(argv[1]);

%o int a,b,c,d;

%o for(a=0;a<n;a++)

%o {

%o for(b=0;b<n;b++)

%o {

%o for(c=0;c<n;c++)

%o {

%o if((a*a+b*c)%n != 0) continue;

%o for(d=0;d<n;d++)

%o {

%o if((b*c+d*d)%n != 0) continue;

%o if((a*b+b*d)%n != 0) continue;

%o if((c*a+d*c)%n != 0) continue;

%o ct++;

%o }

%o }

%o }

%o }

%o printf("%d %ld\n",n,ct);

%o return 0;

%o }

%o /* _Manfred Scheucher_, Jun 09 2015 */

%Y Cf. A066907, A000188.

%K mult,nonn

%O 1,2

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

%E More terms from _Ben Branman_, Mar 22 2013

%E More terms from _Manfred Scheucher_, Jun 09 2015