Code:

[n,u]=[231, 65];Mod([1,1;1,u],n)^n==[u,-1;-1,1]
1

Theorem 1 also works for composites. Testing (n-1)/2 times with different u is infeasible for large n.

Theorem 2 is ill-defined. What are a(u) and c(u). Can you give a numerical example how this works?