Let $M$ be a square matrix with integer entries. Then **Fermat's little theorem for matrices** holds:


$$\text{tr}(M^p) \equiv \text{tr}(M) \bmod p.$$


This follows by an examination of the action of the Frobenius map on the roots of the characteristic polynomial of $M$ over a splitting field; there is also a combinatorial proof. (Incidentally, I have no idea who to credit for this result.)


This suggests the following definition generalizing the notion of Fermat pseudoprime, the notion of [Fibonacci pseudoprime](http://en.wikipedia.org/wiki/Lucas_pseudoprime) (it feels to me like the Wikipedia article has the names backwards), and the notion of [Perrin pseudoprime](http://en.wikipedia.org/wiki/Perrin_number): a **pseudoprime to base $M$** is a positive integer $n$ such that


$$\text{tr}(M^n) \equiv \text{tr}(M) \bmod n.$$


This definition appears to be related to Grantham's notion of [Frobenius pseudoprime](http://www.jstor.org/stable/10.2307/2698789), although it might be weaker. For concreteness, let $M$ be the [companion matrix](http://en.wikipedia.org/wiki/Companion_matrix) of your favorite monic irreducible polynomial over $\mathbb{Z}$. 


Anyway, this looks like a reasonable primality test to me (choose random matrices, exponentiate them, etc.), but I don't really know anything about the subject. Does this notion appear anywhere in the literature? How does it compare to other primality tests? 



Does this notion of pseudoprime relative to a matrix appear in the literature?
I think this is weaker than the notion of Frobenius pseudoprime. The trace of a matrix is the sum of the roots of its characteristic polynomial, so you're testing whether the sum of the roots remains invariant upon raising to the pth power. The Frobenius test is stronger than that.


