Robert Gerbicz wrote: If $ p > 3$ is a prime number then $ p = 6*k + 1$ or $ p = 6*k - 1$ for some positive integer k. In the first case: \[ {7}^{p} - {6}^{p} - 1 = {7}^{6*k + 1} - {6}^{6*k + 1} - 1 \equiv 7*({7}^{6})^{k} - 6*({6}^{6})^{k} - 1 \equiv 7 - 6 - 1 \equiv 0\pmod{43} \] using : $ 7^{6}\equiv 6^{6}\equiv 1\pmod{43}$. In the second case: \[ {7}^{p} - {6}^{p} - 1 = {7}^{6*k - 1} - {6}^{6*k - 1} - 1 \equiv{7}^{5}*({7}^{6})^{k - 1} - {6}^{5}*({6}^{6})^{k - 1} - 1 \equiv 37 - 36 - 1 \equiv 0\pmod{43} \] This proves the statment.

By the well-known fact that $ x^2 + x + 1|x^{2k} + x^k + 1$ for every $ k\equiv 1,2 \pmod{3}$ we have that $ 6^2 + 6 + 1|6^{2p} + 6^p + 1$ because 3 does not divide p. So $ 6^{2p} + 6^p + 1\equiv 0 \pmod{43}$. Also we have that $ 6\cdot 7\equiv - 1\pmod{43}$ so $ (6\cdot 7)^p\equiv - 1\pmod{43}$ because p is odd. $ 6^{2p} + 6^p + 1\equiv6^{2p} + 6^p - (6*7)^p\equiv6^p*(6^p + 1 - 7^p)\equiv0\pmod{43}$ Because $ \gcd(6,43) = 1$ we have that $ 43|7^p - 6^p - 1$

It is spesialiast problem about $ A_n=a^n+b^n+c^n, a=7, b=-6,c=-1,a+b+c=0$.

Can you be more specific, Rust? Do you have a generalisation (with proof)?

Peter wrote: Can you be more specific, Rust? Do you have a generalisation (with proof)? Let $ x_1,x_2$ are roots $ x^2 + ax + b = 0,a,b\in Z$ and ab -even (if $ x_1,x_2$ are integers, then always $ ab = - (x_1 + x_2)x_1x_2$ even). Let $ A_n = x_1^n + x_2^n + a^n, P = a^2 - b$. Then $ (2P)|A_{3k - 1}, \ (2P^2)|A_{3k + 1}.$ In your case $ P = 43$ and prime $ p > 3$ is $ p = \pm 1\mod 3$. If $ ab$ odd we can prove only $ P|A_{3k - 1}, \ P^2|A_{3k + 1}$. Generalized. Let $ x_1,x_2,...,x_k$ roots of $ x^k=ax+b, \ a,b\in Z$ and $ A_n=x_1^n+x_2^n+...+x_k^n$. Then $ A_{n+k}=aA_{n+1}+bA_n,A_0=k,A_1=A_2=...=A_{k-2}=0,$ and $ A_{k-1}=(k-1)!(-1)^{k}a, A_k=bk.$ Therefore $ A_{nk}=kc_nb^n+k!c_{n+1-k}b^{n+1-k}a^k+k!c_{n+2-2k}b^{n+2-2k}a^{2k}+...$ $ A_{nk-i}=k!c_{n-i}b^{n-i}a^i+k!c_{n+1-i-k}b^{n+1-i-k}a^{i+k}+...$ Therefore $ a^i|A_{nk-i}$.

Rust could you make you generalization clearer?I get confused with the expressions you name $ A_n$.. Thank you.

If $ A_n = x_1^n + x_2^n + .. + x_k^n$, then it may be defineed by recurent $ A_{n + k} = \sigma_1 A_{n + k - 1} - \sigma_2 A_{n + k - 2} + ... + ( - 1)^{k - 1}\sigma_kA_n$, were $ \sigma_1 = x_1 + x_2 + ... + x_k,\sigma_2 = \sum_{i < j}x_ix_j,...$ $ x_1,x_2,..,x_k$ roots of $ x^k - \sigma_1x^{k - 1} + \sigma_2x^{k - 2} - ... + ( - 1)^k\sigma_k = 0$. If all $ \sigma_i$ are integer, then $ A_n = P_n(\sigma_1,...,\sigma_k )$ are integer for all natural n. Consider case, when ${ \sigma_1 = \sigma_2 = \sigma_{k - 2} = 0,\sigma_{k - 1}( - 1)^k = a,\sigma_k ( - 1)^k - 1} = b$. Then $ A_{n + k} = aA_{n + 1} + bA_n$ and $ A_1 = ... = A_{k - 2} = 0, A_{k - 1} = aA_0 + bA_{ - 1} = (k - 1)a, A_k = bk.$ In these case $ A_n = P_n(a,b)$, were $ P_n$ is polinom with common degree n for all members, $ deg(a) = k - 1,deg(b) = k$. $ P_n(a,b) = aP_{n - k + 1}(a,b) + P_{n - k}b,P_{k - 1}(a,b) = (k - 1)a,P_k(a,b) = kb$. Therefore $ A_{n} = P_n(a,b) = \sum_{i,ik + j(k - 1) = n} B(n,i,j)b^ia^j$. For coefficients $ B(n,i,j)$ we had $ B((k - 1)j,0,j) = k - 1,B(ki,i,0) = k,$ $ B(ki + (k - 1)j,i,j) = k\binom{i - 1 + j}{j} + (k - 1)\binom{i + j - 1}{i} = \frac {n(i + j - 1)!}{i!j!}$. For case $ k = 3,x_1 = 7,x_2 = - 6,x_3 = - 1,\sigma_1 = 0,\sigma_2 = - 43,a = 43,\sigma_3 = 42 = b$ we had $ 7^n + ( - 6)^n + ( - 1)^n = n\sum_{3i + 2j = n}\frac {(i + j - 1)!}{i!j!}a^ib^j$ If $ n$ odd, then $ i$ -odd, therefore $ a|P_n(a,b)$.

Such heavy machinery is not needed. The powers of 7 mod 43 follow the pattern $7, 6, -1, -7, -6, 1, 7$, ... The powers of 6 mod 43 follow the pattern $6, -7, 1, 6$, ... All primes greater than 3 are 1 or 5 mod 6. Thus the expression $7^p - 6^p - 1$ must be either $(7 - 6 - 1)$ or $(-6 -(-7) - 1)$ mod 43.

Since $7 \equiv -6^{-1} \pmod{43}$, hence it suffices to show $6^{p}+6^{-p}+1 \equiv 0 \pmod{43} \Leftrightarrow 6^{2p}+6^p+1 \equiv 0 \pmod{43}$ . Now since $ord_{43}(6)=3$ and $p>3$, hence $6^{p} \not\equiv 1 \pmod{43}$. Hence $(6^p-1)\left(6^{2p}+6^p+1\right)=6^{3p}-1=216^p-1 \equiv 0 \pmod{43}$ yields the result. $\square$