Find all triples

Art of Problem Solving

AoPS Online

High School Math Grades 9-12, Ages 13-18

Grades 9-12, Ages 13-18

3 M G

BBookmark VNew Topic kLocked

High School Math Grades 9-12, Ages 13-18

Grades 9-12, Ages 13-18

3 M G

BBookmark VNew Topic kLocked

No tags match your search

M

Find all triples

G H J

Reveal topic tags

L

G H BBookmark kLocked kLocked NReply

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

26 posts

#1 h Apr 19, 2025, 12:14 AM

Y by

Find all triples of positive integers $(n, r, s)$ such that $n^2 + n + 1$ divides $n^r + n^s + 1$ .

This post has been edited 2 times. Last edited by pedronis, Apr 19, 2025, 12:16 AM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

748 posts

#2 h Apr 19, 2025, 3:56 AM

Y by

i think we use roots of unity for this one
$n^2 + n + 1$ has roots of the 3rd roots

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

636 posts

#3 h Apr 20, 2025, 10:43 PM

Y by

I'll solve a slightly different problem.

Problem. Find all pairs of positive integers $(r, s)$ such that $n^2 + n + 1$ divides $n^r + n^s + 1$ for any $n$ .

Solution. We factor $n^2+n+1$ as $(n-\omega)(n-\omega^2)$ , where $\omega = \dfrac{-1+i\sqrt{3}}{2}.$ If the polynomial $P(n) = n^r + n^s + 1$ has the properties that $P(\omega) = 0$ and $P(\omega^2) = 0$ , then it satisfies the first condition. In either case, we need for
$\begin{align*} \omega^r+\omega^s = -1 \\ \omega^{2r}+\omega^{2s} = -1 \end{align*}$ to both be true. Since $\omega^3 = 1$ , we can try all residues of $r$ and $s$ modulo $3$ .
$\begin{tabular}{ c|c|c|c } $r$ & $s$ & $\omega^r+\omega^s$ & $\omega^{2r}+\omega^{2s}$ \\ \hline $0$ & $0$ & $2$ & $2$ \\ $0$ & $1$ & $-\omega^2$ & $-\omega$ \\ $0$ & $2$ & $-\omega$ & $-\omega^2$ \\ $1$ & $0$ & $-\omega^2$ & $-\omega$ \\ $1$ & $1$ & $2\omega$ & $2\omega^2$ \\ $1$ & $2$ & $-1$ & $-1$ \\ $2$ & $0$ & $-\omega$ & $-\omega^2$ \\ $2$ & $1$ & $-1$ & $-1$ \\ $2$ & $2$ & $2\omega^2$ & $2\omega$ \\ \end{tabular}$ This shows that we only have solutions for $\boxed{r \equiv 1 \pmod{3}, s \equiv 2 \pmod{3} \text{ and } r \equiv 2 \pmod{3}, s \equiv 1 \pmod{3}}$ .

This post has been edited 2 times. Last edited by Kempu33334, Apr 20, 2025, 10:44 PM

Z K Y

N Quick Reply

G

H

=

© 2025 AoPS Incorporated

a