Key ingredient for the cyclotomic primality test

Let $n$ be a natural number. Let $q$ be a prime not dividing $n$, let $r$ be a power of a prime number $l$ not dividing n and let map the character $\chi:(\mathbb{Z}/q\mathbb{Z})^*\to\mu_r$.
If:

1. for every prime $p$ dividing $n$ there exists $\lambda_p$ in $l$-adic integers such that $$p^{l-1}=n^{(l-1)\lambda_p}$$ in multiplicative group of $l$-adic integers;
2. the Gaussian sum $\tau(\chi)$ satisfies $$\tau(\chi)^{\sigma_n-n}\in \langle\xi_r\rangle, \text{ in the ring } \mathbb{Z}[\xi_r,\xi_q]/(n) .$$ there $\langle\xi_r\rangle=$ cyclic subgroup of $(\mathbb{Z}[\xi_r]/(n))^*$ of order $r$ generated by  $\xi_r$.

Then we have $$\chi(p)= \chi(n)^{\lambda_l}$$ for every prime divisor $p$ of $n$.

By $\mu_r$ we denote subgroup of $r$-th roots of unity of $\bar{\mathbb{Q}}^*$.

Four primality testing algorithms