[seqfan] Re: 2X2 -n..n with inverse in -n..n and totient function?

[Max Alekseyev]

On Sat, Feb 4, 2012 at 10:54 AM, Max Alekseyev <maxale at gmail.com> wrote:
> On Sat, Feb 4, 2012 at 9:43 AM, Ron Hardin <rhhardin at att.net> wrote:
>> Toying around with 2X2 -n..n matrices whose determinant divides every entry, is
>> this obvious?  Not to me.
>
> This is the same as having determinant equal +1 or -1. Choosing
> between +1 and -1 gives factor of 2 in counting.
>
> ...
>
>> Another mystery is why the original series was divisible by 8 in the first
>> place.
>
> Putting aside matrices that have either of diagonals zero (there are 8
> such matrices, which is divisible by 8), we get another factor of 2 by
> simultaneously changing sign of all elements, and the third factor of
> 2 by changing sign of elements just on the main diagonal.

Now about getting the totient:

On Sat, Feb 4, 2012 at 9:43 AM, Ron Hardin <rhhardin at att.net> wrote:

> first differences
>
>  8 16 16 32 16 48 32 48 32 80 32 96 48 64 64 128 48 144 64 96 80 176 64 160 96
> 144 96 224 64 240 128 160 128 192
>
> first differences / 8
>
> 1 2 2 4 2 6 4 6 4 10 4 12 6 8 8 16 6 18 8 12 10 22 8 20 12 18 12 28 8 30 16 20
> 16 24 12 36 18 24 16 40 12 42 20
>
> = A000010(n+1)

The first difference of the original sequence a(n+1) - a(n) counts
matrices where at least one of the elements is +/- (n+1) of
determinant +/- 1. It is easy to see that there can be only one such
element.

This leads to the equation
(n+1) x - yz = +/- 1
where x, y, z are the other three elements of a matrix. It implies
(n+1) and y are co-prime and as soon as y is fixed, there are only 2
solutions for x,z (since z is uniquely determined modulo (n+1) and
must be in the interval [-n,n]).

So the first difference is
2*A000010(n+1) (number of choices for y)
times 2 (number of choices for x,z)
times 4 (number of positions for (n+1))
times 2 (number of choices for sign of (n+1))
times 2 (number of choices for sign of determinant)

Overall we have 64*A000010(n+1) and cancelling two times factor of 8
gives us A000010(n+1).

Regards,
Max