# Why do all primes $n>3$ satisfy $\,309\mid 20^n-13^n-7^n$

Solve the following... $$309|(20^n-13^n-7^n)$$ in $$\mathbb{Z}^+$$. 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!

• Is it false that it generates all the primes? – user665856 Apr 23 at 16:33
• It is easy to picture why there might be a solution for all prime $n$. However, the interesting part of the pattern is that $n=5\cdot 5$ and $n=5\cdot 7$ both appear, yet neither $n=3\cdot 3$ nor $n=5\cdot 5$ appear. Which odd composites admit solutions? – Mark Fischler Apr 23 at 16:38
• There are no even numbers .. – user665856 Apr 23 at 16:39
• It seems like $n \equiv \pm1 \pmod 6$. – md2perpe Apr 23 at 16:46
• Yeah right but why do only specific composites arrive? – user665856 Apr 23 at 16:47

$$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$$, ...

• +1 really cool. – user665856 Apr 23 at 17:12
• @ShamimAkhtar If you had entered your sequence $\,5,7,11,13,\ldots, 65$ into OEIS you'd obtain a unique match: A007310 = Numbers congruent to $1$ or $5$ mod $6$. Once you know that the rest is easy. That's the first method one should try on problems like this (when the pattern is not already clear from prior knowledge). – Bill Dubuque Apr 23 at 19:53
• At mathoverflow.net/questions/328782/… there is a proof that in general $(a^2-ab+b^2)$ divides $a^{6k+r} -b^{6k+r} -(a-b)^{6k+r}$ for $r = 1, 5$. The question at hand is a particular case with $a=20, b=13$ where $(a^2-ab+b^2)=309$ – Mark Fischler Apr 23 at 22:04
• @Mark We can also proceed analogously as I do here. (iirc this specific case is done in some other question here). – Bill Dubuque Apr 23 at 22:38

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.

• Can you explain why this works? – user665856 Apr 23 at 16:36
• I'm afraid I canot – Michael Stachowsky Apr 23 at 16:40
• Is this a standard question in mse? I too am afraid if any moderator marks this as off topic – user665856 Apr 23 at 16:41
• It's a perfectly acceptable question, although it's probably much more difficult to answer than we think. As a result, you're probably either not going to get an answer or get a very strange one. I could be wrong, number theory isn't my thing. – Michael Stachowsky Apr 23 at 16:46

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.

• How can you verify? – user665856 Apr 23 at 17:06
• Mathematica is very fast in determining residues mod 309. – Mark Fischler Apr 23 at 17:11