Roots on a Circle

Let $r$ be a root of the polynomial $x^n + x^m + 1$ on the unit circle. Then $|r|=1 \Rightarrow |r^m|=|r^n|=1$ . Since $r^n + r^m + 1 = 0$ and $|r^m|=|r^n|=1$ , we can visualize the equation in an Argand diagram where three vectors of length $1$ add up to give $0$ , i.e. lining up the three vectors gives an equilateral triangle. Given that one of the vectors is $1$ , then $r^m$ and $r^n$ must be $e^{i(\frac{2\pi}{3})}$ and $e^{i(\frac{4\pi}{3})}$ in some order. So $m \arg (r)$ and $n \arg (r)$ must be $\frac{2\pi}{3}+2a\pi$ and $\frac{4\pi}{3}+2b\pi$ in some order, where $a$ and $b$ are integers. So either $\frac{m}{n}$ or $\frac{n}{m}$ is equal to $\dfrac{\frac{2\pi}{3}+2a\pi}{\frac{4\pi}{3}+2b\pi} = \frac{1+3a}{2+3b}$ . Here, we see that either $m$ and $n$ are congruent to $1$ and $2$ modulo $3$ (in some order), or $m$ and $n$ can both be divided by $3^c$ (where $c$ is a positive integer) to obtain $m'$ and $n'$ which are congruent to $1$ and $2$ modulo $3$ (in some order). Note that the first case can be seen as part of the second case, with $c = 0$ . We also observe that the converse of this is true. As long as $m$ and $n$ can both be divided by $3^c$ (where $c$ is a non-negative integer) to obtain $m'$ and $n'$ which are congruent to $1$ and $2$ modulo $3$ (in some order), then we can find the appropriate $a$ and $b$ and thus find an appropriate root $r$ that has modulus $1$ . Now we shall calculate how many pairs $(n,m)$ fit the conditions.

When $c = 0$ , there are $34$ numbers which are $1 \pmod{3}$ and $33$ numbers which are $2 \pmod{3}$ . So there are altogether $34 \cdot 33 = 1122$ pairs. When $c=1$ , there are $11 \cdot 11 = 121$ pairs. When $c=2$ , there are $4 \cdot 4 = 16$ pairs. When $c=3$ , there is $1 \cdot 1 = 1$ pair. We cannot have $c \geq 4$ , so there are altogether $1122 + 121 + 16 + 1 = 1260$ pairs. So $N=1260$ and the last three digits of $N$ is $260$ .

Since the number is on the unit circle, it is of the form e^{ix(pi)} for some x belons to [0,2) . Thus the equation we want to solve is e^{inx(pi)} + e^{imx(pi)} = -1 .

Note that the imaginary part of the equation is 0. Given that both terms on the LHS lie on the unit circle, the only way that their sum is real is if they are negatives or conjugates of each other. But since their sum is nonzero, they cannot be negatives of each other. Hence we obtain that e^{inx(pi)} = e^{(-i)mx(pi)} . . Hence, e^{i(n + m)x(pi)} = 1 .

Also, we can use e^{(-i)nx(pi)} = e^{imx(pi)} to reduce the original equation to e^{inx(pi)} + e^{(-i)nx(pi)} = 2\cos {nx(pi)} = -1

Thus we have 2 possibilities:

e^{inx(pi)} = (-1/2 , (\sqrt{3})/2) = e^{2i(pi/3)} , e^{imx(pi)} = e^{-2i(pi/3)} or, e^{inx(pi)} = e^{-2i(pi/3)} , e^{imx(pi)} = e^{2i(pi/3)}

Case 1 :

nx = 2/3 + 2k , mx = 4/3 + 2l
Hence, for every n>m with the ratio (1 + 3k) : (2 + 3l ) we have a solution.

Case 2 :

nx = 4/3 + 2k , mx = 2/3 + 2l
Hence, for every n>m with the ratio (2 + 3k) : (1 + 3l ) we have a solution.

It can be seen that (n,m) is a valid pair iff

The largest power of 3 in n and m should be equal. This is because 3k+1 and 3k+2 are both not divisible by 3. Hence any power of 3 in m and n should come from the multiplicant of the ratio and should be equal.

On cancelling off the largest power of 3 from both m and n, numbers should leave different remainders with 3.

There are 34 numbers <= 100 which are 1 mod 3 and 33 which are 2 mod 3. These give a total of 33 34 valid (m,n) pairs. There are 11 numbers <=100 which are 3 mod 9 and 11 which are 6 mod 9. These give 11 11 valid pairs. There are 4 numbers <=100 which are 9 mod 27 and 4 which are 18 mod 27. These give 4*4 valid pairs. (54,27) is another valid pair.

Thus the total number of (m,n) pairs which satisfy the conditions is 33 34 + 11 11 + 4*4 + 1 = 1260

Hence , N = 260

Since $x^m$ and $x^n$ are on the unit circle and sum to -1, they must equal $\omega$ and $\omega^2$ in some order, where $\omega = {\rm exp}(2\pi i/3)$ . Now let $d = {\rm gcd}(m,n)$ . Then $x^{3m} = x^{3n} = 1$ implies $x^{3d} = 1$ . So $x^d = \omega$ or $\omega^2$ . And it's a root of $x^{m/d} + x^{n/d} + 1$ , which happens if and only if $m/d + n/d \equiv 0$ mod 3. It's not hard to see that this is a necessary and sufficient condition on $m,n$ .

Such pairs are all uniquely expressible as $(3^a b, 3^a c)$ where $b$ and $c$ are $1$ and $2$ mod $3$ respectively. Counting these up gives $34 \cdot 33 + 11 \cdot 11 + 4 \cdot 4 + 1 \cdot 1 = 1260.$

Since $|x| = 1$ , then we can assume that $x = cis a$ . Where a in degrees. So, from the equation, we obtain that :

$(cis a)^n + (cis a)^m + 1 = 0 \implies cis an + cis am + 1 = 0$ $(\cos an + \cos am + 1) + i(\sin an + \sin am) = 0 = 0 + i. 0$ , implies that :

$\cos an + \cos am + 1 = 0 \implies 2 \cos \frac{an + am}{2}. \cos \frac{an - am}{2} + 1 = 0 \ldots \ldots (1)$ and $\sin an + \sin am = 0 \implies 2 \sin \frac{an + am}{2}. \cos \frac{an - am}{2} = 0 \ldots \ldots (2)$

From (2), we obtain that $\sin \frac{an + am}{2} = 0 or \cos \frac{an - am}{2} = 0$ . But, if we input $\cos \frac{an - am}{2} = 0$ to equation (1), we obtain that $1 = 0$ , which is completely wrong. Implies that,

$\sin \frac{an + am}{2} = 0 \ldots \ldots (3)$

And, we get two solution for equation (3), that is $\frac{an + am}{2} = 360k$ or $360k + 180$ . Where $k$ is integer. Then, we divide into $2$ cases, that is :

Case 1 : $\frac{an + am}{2} = 360k \implies an + am = 720k$

$\implies \cos \frac{an+am}{2} = 1$ . Then, subtitute it into the first equation. Then, we obtain : $\cos \frac {an - am}{2} = \frac{-1}{2}$ . So, for this one we obtain the solution $\frac{an - am}{2} = 360l + 120$ or $360l + 240 \implies an - am = 720l + 240$ or $720l + 480$ .

From this case, we obtain $an + am = 720k$ , and $an - am = 720l + 240$ or $720l + 480$ . So, add both equation and subtract both equation. We obtain :

$an = 360k + 360l + 120 or 360k + 360l + 240$ $am = 360k - 360l - 120 or 360k - 360l - 240$ , then

$\frac{n}{m} = \frac{3(k+l) + 1}{3(k-l) - 1}$ or $\frac{3(k+l) + 2}{3(k-l) - 2}$ , but since $k$ and $l$ are integer. We can assume that $k$ and $l$ both are non - negative or both both non - positive, we can cancel for negative one and positive one because it doesn't affect at all (Because we can set $k : k - l$ , and $l : 0$ ). And, for both non positive, we can change $k : -k$ and $l : -l$ , such that $k$ and $l$ both positive. So, $$

$\frac{m}{n} = \frac{n}{m} = \frac{3(k+l) + 1}{3(k-l) - 1}$ or $\frac{3(k+l) - 1}{3(k-l) + 1}$ or $\frac{3(k+l) + 2}{3(k-l) - 2}$ or $\frac{3(k+l) - 2}{3(k-l) + 2}$ , where $k$ and $l$ both non - negative.

Case 2 : $\frac{an + am}{2} = 360k + 180 \implies an + am = 720k + 360$

$\implies \cos \frac{an+am}{2} = -1$ . Then, subtitute it into the first equation. Then, we obtain : $\cos \frac {an - am}{2} = \frac{1}{2}$ . So, for this one we obtain the solution $\frac{an - am}{2} = 360l + 60 or 360l + 300 \implies an - am = 720l + 120$ or $720l + 600$ .

From this case, we obtain $an + am = 720k + 360$ , and $an - am = 720l + 120$ or $720l + 600$ . So, add both equation and subtract both equation. We obtain :

$$ $an = 360k + 360l + 240$ or $360k + 360l + 480$ $$ $am = 360k - 360l + 120$ or $360k - 360l - 120$ , then

$\frac{n}{m} = \frac{3(k+l) + 2}{3(k-l) + 1}$ or $\frac{3(k+l) + 4}{3(k-l) - 1}$ , but since $k$ and $l$ are integer. We can assume that $k$ and $l$ both are non - negative or both both non - positive, we can cancel for negative one and positive one because it doesn't affect at all (Because we can set $k : k - l$ , and $l : 0$ ). And, for both non positive, we can change $k : -k$ and $l : -l$ , such that $k$ and $l$ both positive. So,

$\frac{m}{n} = \frac{n}{m} = \frac{3(k+l + 1) - 1}{3(k-l) + 1}$ or $\frac{3(k+l) + 1}{3(k-l + 1) - 1}$ or $\frac{3(k+l+1) + 1}{3(k-l) - 1}$ or $\frac{3(k+l)-1}{3(k-l+1) + 1}$ , where $k$ and $l$ both non - negative.

From, both case, since m and n both positive integers, then we implies all of pairs $(n, m)$ such that $m+n|3$ , where $3 \nmid n$ and $3 \nmid m$ , also if $3 | n$ and $3|m$ , then there are $c$ such that $3^c || n$ and $3^c || m$ , and $3| \frac{n}{3^c} + \frac{m}{3^c}$ .

Proof : It's easy to see that, $k + l$ and $k - l$ has the same parity.

if $\frac{m}{n} = \frac{3(\text{odd or even}) - 1 \text{or} 1}{3(\text{odd or even}) - 1 \text{or} 1}$ , then use case $1$ , it wil be satisfy, but if

$\frac{m}{n} = \frac{3(\text{odd or even}) - 1 \text{or} 1}{3(\text{even or odd}) - 1 \text{or} 1}$ , then use case $2$ , it wil be satisfy. So, proved.

So, now we only find if $n \equiv 1 \pmod{3}$ , then $n \equiv 2 \pmod{3}$ , and $n \equiv 2 \pmod{3}$ , then $n \equiv 1 \pmod{3}$ , where $100 \ge n > m \ge 1$ .Since there are $33$ number that remainder $2$ when divide by $3$ . And there are $34$ number that remainder $1$ when divide by $3$ . So, there are $33. 34 = 1122$ .

Now, the other possibilities are $3 | n$ and $3|m$ , then there are $c$ such that $3^c || n$ and $3^c || m$ , and $3| \frac{n}{3^c} + \frac{m}{3^c}$ . Then, we can list like the first one. That is $11. 11 + 4. 4 + 1. 1 = 138$

Add them, we obtain : $N \equiv \boxed{260} \pmod{1000}$

Supposing that $\psi$ is a complex root of $x^m + x^n + 1$ that is on the unit circle, ie $|\psi|=1$ . Then $\psi^m + \psi^n + 1 = 0$ . Noting that $|\psi^k| = |\psi|^k = 1$ , we can say that $\psi^n$ and $\psi^m$ are also on the unit circle.

These two cannot be equal to $1$ or $-1$ and still make the above equation equal to $0$ , so they must be complex numbers; further, they must be complex conjugates of each other, since there is no imaginary part in their sum. Their real parts must sum to $-1$ , but they are equal, being complex conjugates, so their real parts must both be $-\frac{1}{2}$ . The constraint of being on the unit circle means that they must be, in some order, equal to $\frac{-1+i\sqrt{3}}{2}, \frac{-1-i\sqrt{3}}{2}$ , which are the cubic roots of unity.

Since the cubic roots of unity are involved, we'll use the principal root $\omega = \frac{-1+i\sqrt{3}}{2}$ , with $\omega^2 = \frac{-1-i\sqrt{3}}{2}, \omega^3 = 1, \omega^2 + \omega + 1 = 0$ .

Now, we know that either $\psi^n = \omega^2, \psi^m = \omega\:$ or $\:\psi^n = \omega, \psi^m = \omega^2$ . This means that $\psi^{n+m}=\omega^3=1$ . Since $\psi$ is either a cube root of unity or something of the form $\sqrt[3k]{-1}$ , $n+m$ must be a multiple of $3$ .

This is in fact a sufficient condition, so long as $n$ and $m$ aren't multiples of $3$ individually - as long as they aren't, then $\omega$ is a root of the equation. This is because $\omega^{3k+1} = \omega^{3k} \times \omega = \omega$ , and $\omega^{3k+2} = \omega^2$ . Then, if $n+m$ is a multiple of $3$ and neither are multiples themselves, then one will be of the form $3k+1$ and the other will be like $3k+2$ , so that $\omega^n + \omega^m + 1 = \omega^2 + \omega + 1 = 0$ as required.

If $m$ and $n$ are multiples of $3$ , then this can't be used. What can be done is to change the equation form, like so -

$x^6 + x^3 + 1 = (x^3)^2 + (x^3) + 1$

This is like $x^2 + x + 1$ , and shares the fact of having roots on the unit circle. Here you let $x^3 = \omega$ , which makes $x$ a ninth root of unity, $\sqrt[9]{-1}$ .

However, $x^9 + x^3 + 1$ , although $n+m$ is a multiple of three, doesn't work, as it reduces to $(x^3)^3 + (x^3) + 1$ , which is like $x^3 + x + 1$ ; this equation doesn't work as $3 + 1$ is not a multiple of $3$ . Special consideration needs to be made of these cases, but it can be seen that if $n$ and $m$ are multiples of $3$ , then it is necessary to divide out their common factors of $3$ and check them then. For example, $(24,3)$ reduces to $(8,1)$ which works, but $(24,9)$ becomes $(8,3)$ , which doesn't.

Numbers which are of the form $3k+1$ can be matched with any of the form $3k+2$ to make $(m,n)$ - for example, $(1,2)$ , $(1,5)$ , $(2,4)$ and $(4,5)$ all work. There are $34$ of the first type under $100$ and $33$ of the second, so there are $33 \times 34 = 1122$ combinations.

With numbers that are multiples of $3$ , a similar strategy can be used, considering multiples of $3, 9, 27$ and so on separately.

For multiples of $3$ , numbers like $3(3k+1) = 9k+3$ must be matched with those of $3(3k+2) = 9k + 6$ . There are $11$ of each of these under $100$ , so there are $11 \times 11 = 121$ combinations.

For multiples of $9$ , numbers like $9(3k+1) = 27k+9$ must be matched with those of $9(3k+2) = 27k + 18$ . There are $4$ of each of these under $100$ , so there are $4 \times 4 = 16$ combinations.

For multiples of $27$ , only one combination is possible - $(27, 54)$ - as any other is too high. Similarly, no combinations exist for $81$ or any higher power of $3$ .

The total number of combinations is therefore $1122 + 121 + 16 + 1 = 1260$ , thus the last three digits are $\underline{260}$

Since the root like on the unit circle, the root to the equation X^n + X^m + 1 = 0 : "X" can be replaced with X = e^(i * pi * x)

So

(e^(i pi x))^n + (e^(i pi m))^m + 1 = 0, since the imaginary part of the equation is zero, so the sum of the two exponents [ (e^(i pi x))^n, (e^(i pi m))^m ] must be real. They must either must addictive inverse of one another or complex conjugates of one another.

Suppose that they are addictive inverse of one another, then the equation simplifies to 1 = 0 which is absurd. Thus the relationship between the two exponents must be conjugates to one another.

(e^(i pi x))^n = conjugate [ (e^(i pi m))^m ]

Since conjugate of e^(ix) = cosx + isinx

is

cosx - isinx = cos(-x) + i sin(-x) = e^(-ix)

So (e^(i pi x))^n = (e^(-i pi m))^m

Let A = (e^(i pi x))^n, the equation becomes

A + 1/A + 1 =0, solve via quadratic formula: A = -1/2 +/- i * sqrt(3) /2

e^(n * i pi x) = e^(2pi/3 + 2 i *pi * k), (4pi/3 + 4 i *pi * k) , where k is an integer

n * pi * x = 2pi/3 + 2pi * k, 4pi/3 + 2pi * k, cycle of 3

Similarly,

m * pi * x = 4pi/3 + 2pi * k, 2pi/3 + 2pi * k, cycle of 3

[ Note that n * m is real ]

---

For m such that m mod 3 != 0, any amount of increment of 3 (because cycle 3) yields a value of n ==> n-m=3k

we start with m = 1, we get n = 4, 7, .., 100 << 33 numbers

then m = 2, we get 2, 5, 8, ... 99 << 33 numbers

then m = 4, we get 7, 10, ... 100 << 32 numbers

and so on til m = 97, we get n = 99 << 1 number

and m = 98, we get n = 99 << 1 number

In this case, the total number of such pairs is ( (33+33) + (32+32) + ... (1+1) ) = (1/2) * 2 * 33 * (33+1) = 1122

---

If m mod 3 = n mod 3 = 0, but n mod 9 != 0 or m mod 9 != 0,

then n mod 9 = 3 and m mod 9 = 6 or vice versa Numbers of n mod 9 = 3, given n<=100 is 11

Numbers of m mod 9 = 6, given m<n<=100 is 11

So in this case 11*11=121

---

Similarly, if m mod 9 = n mod 9 = 0, but n mod 27 != 0 or m mod 27 != 0,

then n mod 27 = 9 and m mod 27 = 18 or vice versa

Numbers of n mod 27 = 9, given n<=100 is 4

Numbers of m mod 27 = 18, given m<n<=100 is 4

So in this case 4*4=16

---

Lastly, if mod 27 = n mod 27 = 0, but n mod 81 != 0 or m mod 81 != 0, we get n=54, m=27 as the only solution.

---

N=1122+121+16+1=1260

First observe that 1, x^n and x^m can be represented as unit vectors. As x^n + x^m + 1 = 0, they must define an equilateral triangle, implying that either x^n = e^(i(2pi/3)) and x^m = e^(i(pi/3)) or vice versa.

let x = e^it. we now have either:

nt = (k)(2pi) + 2pi/3

mt = (l)(2pi) + pi/3

n/m = (3k+2)/(3l+1)

OR

nt = (k)(2pi) + pi/3

mt = (l)(2pi) + 2pi/3

n/m = (3k+1)/(3l+2)

We are thus interested in (n,m) pairs which reduce to a/b where a and b are of opposite congruence (1 and 2, in whatever order) modulo 3.

we can thus let n = (3^j)(a) and m = (3^j)(b), and hammer away.

When j = 0, you have (34)(33) solutions

(there are 34 numbers congruent to 1 mod 3, and 33 congruent to 2 mod 3; each pair corresponds to 1 solution depending on which is larger).

When j = 1, you have (11)(11) solutions

When j = 2, you have (4)(4) solutions

When j = 3, you have 1 solution.

All values of j > 3 have no solutions, pretty obviously.

This gives you a total of 1122 + 121 + 16 + 1 = 1260

Since a root lies on the unit circle, we may assume the root is $x = \cos{\theta} + i \sin{\theta}$ . Substituting in the original equation, we get: $cis^n{\theta} + cis^m{\theta} + 1 =0$ .

By De Moivre's theorem, $(\cos{n\theta} + i \sin{n\theta}) + (\cos{m\theta} + i \sin{m\theta}) = 1$

Thus, $( \cos{n \theta} + \cos{m \theta}) + i( \sin{n \theta} + \sin{m \theta}) = -1$

$\Rightarrow \cos{\frac{(n+m) \theta}{2}} \cos{\frac{(n-m) \theta}{2}} + i \sin{\frac{(n+m) \theta}{2}} \cos{\frac{(n-m) \theta}{2}} = - \frac{1}{2}$ $(*)$ .

Equating real coefficients, we get: $\sin{\frac{(n+m) \theta}{2}} = 0 \Rightarrow$ $\theta = \frac{2k \pi}{n+m}$ .

Also, $\cos{\frac{(n-m) \theta}{2}} = -\frac{1}{2}$ $\Rightarrow \theta= \frac{4\pi(3k' +1)}{3n-3m}$ .

From the two above relations, $\frac{n+m}{n-m} = \frac{3k}{6k'+2} \Rightarrow \frac{n}{m} = \frac{3(k+2k')+2}{3(k-2k')-2} = \frac{3r_1+2}{3r_2+1}$ for integers $r_i$ .

Thus, $n \equiv 2 \pmod{3} ; m \equiv 1 \pmod{3}$ or $(n,m)$ when normalized/reduced by a factor of power of $3$ , say $3^w$ , result into numbers of the previously stated form (i.e. $n = 3^w(3a+2)$ , $m=3^w(3b+1)$ ). The result also holds if $(m,n)$ is also of above forms. (depending on step $(*)$ )

• If $w=0$ , number of pairs satisfying $\{ 1 \pmod{3} , 2 \pmod{3}\}$ are $34\times 33$ .

• If $w=1,2,3$ , numbers of pairs satisfying are respectively $11^2 + 4^2 + 1$ . $w \geq 4$ doesn't hold.

Thus, total number of pairs is $1260$ .

The conditions are equivalent to saying that there exists $x$ such that $\{x^n,x^m,1\}$ are the three (distinct) cube roots of unity.

Now write:

$n=3^p \nu$ and $m=3^{\hat{p}} \mu$

where $p,\hat p, \nu,\mu$ are integers and $3 \not | \nu\mu$ .

Then if $x$ is a solution, the fact that $1 \ne (x^n)^\mu = x^{\nu\mu\cdot 3^p}$ and 1 \ne (x^m)^\nu = x^{\nu\mu\cdot 3^\hat p} means that $\hat p = p$ . On the other hand, the fact that $1 = x^{n+m} = x^{(\nu+\mu) 3^p}$ implies that $3|(\nu+\mu)$ .

But conversely, if $\hat p = p$ and $3|(\nu+\mu)$ then $x=e^{\pi/3^{p+1}}$ is a solution.

Therefore, we can compute $N$ by noting that the number of $(\nu,\mu)$ pairs (such that the conditions are satisfied, including $\mu <\nu$ ) is $33*34, 11*11, 4*4, 1*1$ respectively for $p=0,1,2,3$ (and $0$ for $p\ge 4$ ). So $N=1260$ , and the final answer is $260$ .

x^n + x^m + 1 = 0

Because the equation has at least a root r on the unit circle, then we may assume that x = r = e^(iθ) (∵ θ ≠ 0)

As a result, we can get:

r^n + r^m + 1 = 0

e^(iθ n) + e^(iθ m) + 1 = 0

(cos(nθ) + cos(mθ) + 1) + i(sin(nθ) + sin(mθ)) = 0

Then,

sin(nθ) + sin(mθ) = 0 ···· ❶

cos(nθ) + cos(mθ) + 1 = 0 ···· ❷

Consider x = n + m and y = n – m

❶ sin(xθ/2)cos(yθ/2) = 0

Divide into two cases,

If sin(xθ/2) = 0

x = 2kπ/θ

If cos(yθ/2) = 0

y = (2k + 1)π/θ

❷ 2cos(xθ/2)cos(yθ/2) + 1 = 0

If cos(yθ/2)=0,

2cos(yθ/2)*0 + 1 = 1 ≠ 0

Thus this second case is not satisfy. So we have S=2kπ/θ.

Then,

2cos(xθ/2)cos(yθ/2) + 1 = 0

2cos(kπ)cos(yθ/2) + 1 = 0

Since cos(kπ) = ±1, we have:

±2cos(yθ/2) + 1 = 0

cos(yθ/2) = ±½

cos(yθ/2) = cos(±π/3 + k'π)

Let's define θ = απ/3 then,

y = 2(3k' ± 1)/α

n = (3k + 3k' ± 1)/α

m = (3k – 3k' ∓ 1)/α

n = m(3k + 3k' ± 1)/(3k – 3k' ∓ 1) (0 < m < n, k > k' >0)

We may see that (3k + 3k' ± 1)/(3k – 3k' ∓ 1) is not divisible by 3. Then the solution (n, m) is (n/3, m/3). We can get 260 solutions.