Root of unity modulo n

A **root of unity** modulo \( n \) refers to an integer \( k \) such that \( k^m \equiv 1 \mod n \) for some positive integer \( m \). In other words, \( k \) is a root of unity if it raises to some integer power \( m \) and gives a result of 1 when taken modulo \( n \).