Peter wrote: Prove that $1280000401$ is composite. $a^7+a^2+1=(a^2+a+1)(a^5-a^4+a^2-a+1)$ so every number that can be expresed in this form is composite. Therefore,$1280000401=20^7+20^2+1$ is composite!

Tiks wrote: $ a^7 + a^2 + 1 = (a^2 + a + 1)(a^5 - a^4 + a^2 - a + 1)$ How did you realize this factorization?

It's a known and useful 'trick': let $ p(x)=\sum_{i=0}^{n-1} x^{a_i} \in Z[x]$, where $ a_i$ are non-negative integers. If they form a reduced residue system, $ p(x)$ is divisible by $ g(x)=\sum_{i=0}^{n-1} x^{i}$. In our case, $ 0, 7, 2 \equiv 0, 1, 2 \pmod 3$, thus $ 1+x+x^2 | x^7+x^2+1$, and long division yields the factorization. Proof of the lemma - $ g$'s roots are the n'th roots of unity, except for 1, and are all distinct (follows from $ g(x)(x-1)=x^n-1$). Thus, to show divisibility, one just have to plug the roots in $ p$ and check whether it yields 0. Because the roots satisfy $ x^n=1$, we get that $ x^i$ is only dependent on the residue of $ i$ modulo $ n$. It follows, from the fact that $ 0,1,\cdots,n-1$ is a reduced residue system mod $ n$ (and because the n'th roots of unity, excluding 1, are of the form $ a,a^2,\cdots,a^{n-1}$ where $ a=e^{\frac{2i\pi}{n}}$), that $ p(x)=g(x)=0$.

I think you mean a complete set of residue classes (a complete set of residues), not a reduced set of residue classes.

bambaman wrote: It's a known and useful 'trick': let $ p(x) = \sum_{i = 0}^{n - 1} x^{a_i} \in Z[x]$, where $ a_i$ are non-negative integers. If they form a reduced residue system, $ p(x)$ is divisible by $ g(x) = \sum_{i = 0}^{n - 1} x^{i}$. In our case, $ 0, 7, 2 \equiv 0, 1, 2 \pmod 3$, thus $ 1 + x + x^2 | x^7 + x^2 + 1$, and long division yields the factorization. Proof of the lemma - $ g$'s roots are the n'th roots of unity, except for 1, and are all distinct (follows from $ g(x)(x - 1) = x^n - 1$). Thus, to show divisibility, one just have to plug the roots in $ p$ and check whether it yields 0. Because the roots satisfy $ x^n = 1$, we get that $ x^i$ is only dependent on the residue of $ i$ modulo $ n$. It follows, from the fact that $ 0,1,\cdots,n - 1$ is a reduced residue system mod $ n$ (and because the n'th roots of unity, excluding 1, are of the form $ a,a^2,\cdots,a^{n - 1}$ where $ a = e^{\frac {2i\pi}{n}}$), that $ p(x) = g(x) = 0$. This is really helpful! I wonder why I've never seen this beautiful lemma before.

bambaman wrote: It's a known and useful 'trick': let $ p(x)=\sum_{i=0}^{n-1} x^{a_i} \in Z[x]$, where $ a_i$ are non-negative integers. If they form a reduced residue system, $ p(x)$ is divisible by $ g(x)=\sum_{i=0}^{n-1} x^{i}$. In our case, $ 0, 7, 2 \equiv 0, 1, 2 \pmod 3$, thus $ 1+x+x^2 | x^7+x^2+1$, and long division yields the factorization. Proof of the lemma - $ g$'s roots are the n'th roots of unity, except for 1, and are all distinct (follows from $ g(x)(x-1)=x^n-1$). Thus, to show divisibility, one just have to plug the roots in $ p$ and check whether it yields 0. Because the roots satisfy $ x^n=1$, we get that $ x^i$ is only dependent on the residue of $ i$ modulo $ n$. It follows, from the fact that $ 0,1,\cdots,n-1$ is a reduced residue system mod $ n$ (and because the n'th roots of unity, excluding 1, are of the form $ a,a^2,\cdots,a^{n-1}$ where $ a=e^{\frac{2i\pi}{n}}$), that $ p(x)=g(x)=0$. Can somebody post an other proof or explain that proof for me? I can't understand the above proof

Then tell us what exactly is unclear instead of expecting us to explain everything.

persya wrote: bambaman wrote: It's a known and useful 'trick': let $ p(x)=\sum_{i=0}^{n-1} x^{a_i} \in Z[x]$, where $ a_i$ are non-negative integers. If they form a reduced residue system, $ p(x)$ is divisible by $ g(x)=\sum_{i=0}^{n-1} x^{i}$. In our case, $ 0, 7, 2 \equiv 0, 1, 2 \pmod 3$, thus $ 1+x+x^2 | x^7+x^2+1$, and long division yields the factorization. Proof of the lemma - $ g$'s roots are the n'th roots of unity, except for 1, and are all distinct (follows from $ g(x)(x-1)=x^n-1$). Thus, to show divisibility, one just have to plug the roots in $ p$ and check whether it yields 0. Because the roots satisfy $ x^n=1$, we get that $ x^i$ is only dependent on the residue of $ i$ modulo $ n$. It follows, from the fact that $ 0,1,\cdots,n-1$ is a reduced residue system mod $ n$ (and because the n'th roots of unity, excluding 1, are of the form $ a,a^2,\cdots,a^{n-1}$ where $ a=e^{\frac{2i\pi}{n}}$), that $ p(x)=g(x)=0$. Can somebody post an other proof or explain that proof for me? I can't understand the above proof Note that $x - \omega$ and $x - \omega^2$ are the roots of $P_1(x)=x^2 + x + 1=0$ at $x= \omega, \omega^2$, where $\omega^3 = 1$. So those 2 linear polynomials are the factors of $P_1$. Also, $\omega \neq 1$ and the $x - \omega$ and $x - \omega^2$ also divide $P_2(x)=x^7 + x^2 + 1$. Thus, all the factors of $P_1$ are also factors of $P_2$, so $P_1$ itself must divide $P_2$.

Is there another way to solve this problem without using this lemma and the factorization from it?

Tiks wrote: Peter wrote: Prove that $1280000401$ is composite. $a^7+a^2+1=(a^2+a+1)(a^5-a^4+a^2-a+1)$ so every number that can be expresed in this form is composite. Therefore,$1280000401=20^7+20^2+1$ is composite! How???