Denotes each flag by a $n$-th root of unity corresponding to its position on the unit circle and each color by $c_j$ for some integer $1\leq j\leq k$ where $k$ is a number of colors used to paint all flags. Observe that flags of each color form a set of all roots of a polynomial $x^d-r$ for some integer $d>1$ and $n$-th root of unity $r$. Let the color $c_j$ have a corresponding polynomial $P_j(x) = x^{d_j}-r_j$. Note that there are $\frac n{\deg P_j}$ flags of the color $c_j$. Note that the product of all polynomials $P_j(x)$ have all $n$-th root of unity as its root, so \[\prod_{j=1}^k P_j(x) = x^n-1.\]Take the derivative of both sides and divide by the product, \[\sum_{j=1}^k \frac{P'_j(x)}{P_j(x)} = \sum_{j=1}^k \frac{d_jx^{d_j-1}}{x^{d_j}-r_j} = \frac{nx^{n-1}}{x^n-1}.\] The above identity is equivalent to a certain polynomial identity. Let $m$ be the smallest value of $d_j$. Note that $m<n$. Divide the equation by $x^{d_j-1}$ and plug in $x = 0$, we get \[\sum_{d_j = m}\frac{d_j}{-r_j} = 0.\]Hence, there are at least two indices $j$ such that $d_j = m$. However, if there are only two terms $j_1,j_2$, then $r_{j_1} = -r_{j_2}$, meaning that $z$ and $-z$ are both roots of $x^n-1$ for some $z$ which is impossible because $n$ is odd. Therefore, there is at least three colors $c_j$ of which the number of flags painted with this color is $\frac nm$.