Arsthbt

Solve the following... $309|(20^n-13^n-7^n)$ in $mathbbZ^+$.
I invested lotof time to it and finally went to WolframAlpha for help by typing...
Solve $309k=20^n-13^n-7^n$ over the integers. It returned the following... Note that all the primes are generated here. Can someone please explain why? Thanks! EDIT: the formulas suggested in the answerare too complicated, but this is so simple!

$20^6 equiv 13^6 equiv 7^6 equiv 229 bmod 309$, so $20^n equiv 13^n + 7^n mod 309$ if and only if $20^n+6 equiv 13^n+6 + 7^n+6 bmod 309$. Since it does work for $n=1$ and $n=5$, but not for $0$, $2$, $3$ or $4$, we find that $20^n equiv 13^n + 7^n bmod 309$ if and only if $n equiv 1$ or $5 bmod 6$.

All primes except $2$ and $3$ are congruent to $1$ or $5 bmod 6$. $2$ or $3$ can't divide a number congruent to $1$ or $5 bmod 6$, so it's not easy for a small number of this form to be composite. The first few composites are $25 = 5^2$, $35 = 5 cdot 7$, $49 = 7 cdot 7$, $55 = 5 cdot 11$, ...

So far you have only shown evidence that some of the primes are generated here, not all of them. It's interesting how many there are, though. There are some polynomials that generate an exorbitant number of primes. Here are some examples. You will likely have to do a lot more work than just exploring the idea numerically to prove that all primes are generated. Even if you do, these functions aren't super interesting because they produce non-primes as well. You won't know whether a number that is generated is prime or not until you test it for primality, so it's not like it can be used to generate the $n^th$ prime without having to do lots more computation. Quite cool, though.

A trivial observation is that it does not generate all the odd primes: $3$ is missing.

However, I can verify that all primes up to $59359$ (other than $2$ and $3$) are represented.

This has a lot do to with the fact that $(a^2-ab+^2)$ is a apparently factor of $a^n-b^n-(a-b)^n$ for all prime $n>3$. Here, $a=20, b=13$.

But that fact is at least as interesting as your observation, and I don't know how to prove it.