Wikipedia:Reference desk/Archives/Mathematics/2023 December 11

Welcome to the Wikipedia Mathematics Reference Desk Archives
The page you are currently viewing is a transcluded archive page. While you can leave answers for any questions shown below, please ask new questions on one of the current reference desk pages.

December 11

Does such prime always exists?

A question is: If n is a natural number not == 1 mod 3, then is there always a prime of the form 2*n^k+1 with natural number k>=1? The answer is no, and the smallest known counterexample is n = 201446503145165177. Now a have questions:

1. If n is a natural number, then is there always a prime of the form 2*n^k-1 with natural number k>=1?
2. If n is an even natural number, then is there always a prime of the form 3*n^k+1 with natural number k>=1?
3. If n is an even natural number, then is there always a prime of the form 3*n^k-1 with natural number k>=1?
4. If n is a natural number neither == 1 mod 5 nor == 14 mod 15, then is there always a prime of the form 4*n^k+1 with natural number k>=1?
5. If n is a nonsquare natural number neither == 1 mod 3 nor == 14 mod 15, then is there always a prime of the form 4*n^k-1 with natural number k>=1?
6. If n is an even natural number not == 1 mod 3, then is there always a prime of the form 5*n^k+1 with natural number k>=1?
7. If n is an even natural number, then is there always a prime of the form 5*n^k-1 with natural number k>=1?
8. If n is a natural number neither == 1 mod 7 nor == 34 mod 35, then is there always a prime of the form 6*n^k+1 with natural number k>=1?
9. If n is a natural number neither == 1 mod 5 nor == 34 mod 35, then is there always a prime of the form 6*n^k-1 with natural number k>=1?
10. If n is an even natural number, then is there always a prime of the form 7*n^k+1 with natural number k>=1?
11. If n is an even natural number not == 1 mod 3, then is there always a prime of the form 7*n^k-1 with natural number k>=1?
12. If n is a noncube natural number neither == 1 mod 3 nor == 20 mod 21, then is there always a prime of the form 8*n^k+1 with natural number k>=1?
13. If n is a noncube natural number neither == 1 mod 7 nor == 20 mod 21, then is there always a prime of the form 8*n^k-1 with natural number k>=1?
14. If n is an even natural number, then is there always a prime of the form 9*n^k+1 with natural number k>=1?
15. If n is an nonsquare even natural number, then is there always a prime of the form 9*n^k-1 with natural number k>=1?
16. If n is a natural number neither == 1 mod 11 nor == 32 mod 33, then is there always a prime of the form 10*n^k+1 with natural number k>=1?
17. If n is a natural number neither == 1 mod 3 nor == 32 mod 33, then is there always a prime of the form 10*n^k-1 with natural number k>=1?
18. If n is a natural number, then is there always a prime of the form (n-1)*n^k-1 with natural number k>=1?
19. If n is a natural number, then is there always a prime of the form (n-1)*n^k+1 with natural number k>=1?
20. If n is a natural number, then is there always a prime of the form (n+1)*n^k-1 with natural number k>=1?
21. If n is a natural number not == 1 mod 3, then is there always a prime of the form (n+1)*n^k+1 with natural number k>=1?

118.170.14.48 (talk) 10:43, 11 December 2023 (UTC)

1. The sequence $a(n)=k$ of smallest $k$ such that $2n^{k}-1$ is prime is given in OEIS A119591. Based on the comments, it is apparently not known whether or not every $n$ admits such a value of $k$. GalacticShoe (talk) 22:13, 11 December 2023 (UTC)

4. $4*23^{k}+1$ is, according to WolframAlpha, composite up through $k=200$. I have not bothered checking more values since WolframAlpha is starting to struggle to factorize some of the numbers (in particular, $k=134,194$ were listed as composite, but no factorization was found in time.) One can show a number of congruences that make checking for primes easier; notably, the only $k$ that this might be prime for are those congruent to $2,6\!\!\!{\pmod {12}}$. I have not found a covering set, and as such I must deign to someone else to see if there are any primes of this form, however. GalacticShoe (talk) 23:46, 11 December 2023 (UTC)

However $4*23^{342}+1$ is prime, according to Lucas primality test with $a=2$ --2A0D:6FC2:4C21:7400:F581:4CA1:68EC:AEC5 (talk) 22:00, 15 December 2023 (UTC)

Ah, thank you very much for finding this. GalacticShoe (talk) 00:16, 16 December 2023 (UTC)

6. Daniel Krywaruczenko's paper on the reverse Sierpiński number problem shows that $5*140324348^{k}+1$ is covered by $\{3,13,17,313,11489\}$, so $n=140324348$ serves as a counterexample to your question. His construction can be applied to other non-Mersenne bases, but the results are not listed on the actual paper itself; I will try to get around to finding some explicit covers myself later. GalacticShoe (talk) 14:17, 12 December 2023 (UTC)

Note that $3$ is a factor when $k\equiv 0\!\!\!{\pmod {2}}$, $13$ is a factor when $k\equiv 3\!\!\!{\pmod {4}}$, $313$ is a factor when $k\equiv 5\!\!\!{\pmod {8}}$, $11489$ is a factor when $k\equiv 1\!\!\!{\pmod {16}}$, and $17$ is a factor when $k\equiv 9\!\!\!{\pmod {16}}$. GalacticShoe (talk) 23:31, 17 December 2023 (UTC)

8. Applying Krywaruczenko's paper, using a period of $16$, one gets $n=99931382025$ where $6*99931382025^{k}+1$ is covered by $\{7,17,37,1297,98801\}$. GalacticShoe (talk) 03:20, 18 December 2023 (UTC)

9. Modifying Krywaruczenko's paper to work with Riesel numbers rather than Sierpiński numbers, using a period of $6$, one gets $n=11259$ where $6*11259^{k}-1$ is covered by $\{5,7,31,43\}$. GalacticShoe (talk) 15:31, 18 December 2023 (UTC)

12. Again applying Krywaruczenko's paper, using a period of $4$, one gets $n=47$ where $8*47^{k}+1$ is covered by $\{3,5,13\}$. GalacticShoe (talk) 03:49, 18 December 2023 (UTC)

14. According to OEIS A263500, which references the Krywaruczenko paper, $177744$ has the property that $9*177744^{k}+1$ is always composite. I have not verified what the covering set is, however. Note that it is the only other value in this sequence that doesn't coincide with one of your forbidden congruences. GalacticShoe (talk) 14:31, 12 December 2023 (UTC)

The covering set is $\{5,17,41,193\}$. $5$ is a factor when $k\equiv 0\!\!\!{\pmod {2}}$, $41$ is a factor when $k\equiv 1\!\!\!{\pmod {4}}$, $17$ is a factor when $k\equiv 3\!\!\!{\pmod {8}}$, and $193$ is a factor when $k\equiv 7\!\!\!{\pmod {8}}$. GalacticShoe (talk) 00:18, 16 December 2023 (UTC)

16. Using a period of $8$, one gets $n=1622070$ where $10*1622070^{k}+1$ is covered by $\{11,73,101,137\}$. GalacticShoe (talk) 03:57, 18 December 2023 (UTC)