9
$\begingroup$

Lately I've been (very casually) toying with primes in the form $n^k+n-1$, as a very far-reaching generalization of Fermat primes. (you get a Fermat prime when you set $k=2^m$ and $n=2$). I have little training in number theory, so mainly I've been just typing stuff into Wolfram and searching for patterns.

One thing I started doing was looking for the smallest $k$ such that $n^k+n-1$ is prime for any particular $n$. I've been able to find solutions for $n \leq 106$. Obviously $k=1$ and $k=2$ do a lot of heavy lifting, but there are some remarkable numbers here. The one that stunned me the most upon finding it was $32^{108}+31 \approx 3.6 \times 10^{162}$, but there's an even bigger smallest solution: $80^{194}+79 \approx 1.58 \times 10^{369}$.

For $n=107$, there are no solutions for $k \leq 495$, which is about as far as I can reliably check. Obviously any $k$ that works must be divisible by $4$.

So, three things I wonder about are:

  1. Is any solution for $n=107$ known? Does it exist for sure?
  2. In general, has it been shown that there is a solution for any $n$?
  3. For any $k$ not in the form $6m+5$, is there $n$ such that $k$ is the smallest solution?

EDIT:

Let $f(n)$ be any polynomial $\mathbb N \rightarrow \mathbb N$. Let $\text{GCD}[f]$ denote the greatest common divisor of $\{f(n): n \in \mathbb N\}$. There is this long-standing conjecture by Bouniakowsky that $f$ is irreducible iff there are infinitely many numbers $n$ such that $\frac{f(n)}{\text{GCD}[f]}$ is prime.

If we suppose this is true, then the following statement implies a positive answer to question 3:

For any $k: k \not \equiv 5 \pmod 6$ there are natural numbers $\alpha,\beta$ such that $\text{GCD}[(\alpha n+\beta)^k+(\alpha n+\beta)-1]=1$, but $\text{GCD}[(\alpha n + \beta)^m+(\alpha n + \beta)-1] \neq 1$ for any $m<k: m \not \equiv 5 \pmod 6$.

Example: for $k=3$, one can let $\alpha = 15, \beta = 2$.

To my untrained eye, this seems approachable.

$\endgroup$
11
  • 3
    $\begingroup$ Unsurprizingly, turns out the sequence is known in OEIS as A076845; but the list ends at 100 $\endgroup$
    – Michał Zapała
    Dec 28, 2020 at 22:38
  • 2
    $\begingroup$ For $n=107$ and $k=1400$ , we get a prime number (I have not yet proven the primality, but a Miller rabin test with $40$ bases was successful). I am pretty sure that $2$ and $3$ are open questions without a hope to answer them. $\endgroup$
    – Peter
    Dec 29, 2020 at 9:00
  • 1
    $\begingroup$ @MichałZapała. For $1$ to $100$ it is almost immediate. After, it takes a lot of time. $\endgroup$
    – Claude Leibovici
    Dec 29, 2020 at 9:09
  • 1
    $\begingroup$ A few more $\{2,44,2,14,3,1,1400,6,3,4,6,1,1\}$ $\endgroup$
    – Claude Leibovici
    Dec 29, 2020 at 9:12
  • 2
    $\begingroup$ @Peter, $n^{6m+5}+n-1$ is divisible by $n^2-n+1$. $\endgroup$
    – Michał Zapała
    Dec 29, 2020 at 9:39

1 Answer 1

Reset to default
4
$\begingroup$

Not a 'real' answer, but it was too big for a comment. I think that you're looking for a solution without using a calculator or PC but maybe this gives some insight. I did only a quick search with the following bounds: $1\le\text{n}\le10^3$ and $1\le\text{k}\le10$.

I wrote and ran some Mathematica-code:

In[1]:=Clear["Global`*"];
\[Alpha] = 10^3;
\[Beta] = 10^1;
ParallelTable[
  If[PrimeQ[n^k + n - 1], {n, k}, Nothing], {n, 1, \[Alpha]}, {k, 
   1, \[Beta]}] //. {} -> Nothing

Running the code gives:

Out[1]={{{2, 1}, {2, 2}, {2, 4}, {2, 8}}, {{3, 1}, {3, 2}, {3, 3}, {3, 
   4}, {3, 8}, {3, 10}}, {{4, 1}, {4, 2}, {4, 3}, {4, 6}, {4, 8}, {4, 
   9}}, {{5, 2}, {5, 6}, {5, 10}}, {{6, 1}, {6, 2}, {6, 4}, {6, 
   7}, {6, 10}}, {{7, 1}, {7, 3}}, {{8, 2}, {8, 6}, {8, 10}}, {{9, 
   1}, {9, 2}, {9, 4}, {9, 7}, {9, 10}}, {{10, 1}, {10, 2}, {10, 
   3}, {10, 4}, {10, 9}}, {{11, 2}, {11, 8}}, {{12, 1}, {12, 
   4}}, {{13, 2}, {13, 4}, {13, 10}}, {{15, 1}, {15, 2}, {15, 3}, {15,
    9}}, {{16, 1}, {16, 2}, {16, 3}, {16, 4}, {16, 8}, {16, 
   10}}, {{17, 4}, {17, 8}}, {{18, 3}, {18, 6}}, {{19, 1}, {19, 
   2}}, {{20, 2}, {20, 4}}, {{21, 1}, {21, 2}, {21, 3}}, {{22, 
   1}, {22, 7}}, {{23, 4}, {23, 6}}, {{24, 1}, {24, 2}, {24, 
   10}}, {{25, 3}, {25, 8}}, {{26, 2}, {26, 4}, {26, 10}}, {{27, 
   1}, {27, 3}, {27, 8}}, {{28, 2}, {28, 4}}, {{29, 10}}, {{30, 
   1}, {30, 2}, {30, 7}}, {{31, 1}, {31, 2}, {31, 4}, {31, 6}, {31, 
   10}}, {{33, 3}, {33, 4}}, {{34, 1}, {34, 6}}, {{35, 2}}, {{36, 
   1}, {36, 3}, {36, 6}}, {{37, 1}, {37, 7}}, {{38, 2}}, {{39, 
   2}, {39, 3}}, {{40, 1}, {40, 4}, {40, 10}}, {{41, 2}}, {{42, 
   1}}, {{43, 3}, {43, 4}}, {{44, 2}, {44, 4}}, {{45, 1}, {45, 
   2}}, {{46, 2}, {46, 3}, {46, 8}}, {{48, 2}}, {{49, 1}, {49, 
   7}, {49, 9}}, {{50, 2}, {50, 6}, {50, 8}}, {{51, 1}, {51, 3}, {51, 
   6}, {51, 10}}, {{52, 1}, {52, 3}}, {{53, 2}, {53, 6}}, {{54, 
   1}, {54, 2}, {54, 4}}, {{55, 1}, {55, 2}, {55, 3}}, {{56, 2}, {56, 
   6}}, {{57, 1}, {57, 9}}, {{58, 4}}, {{59, 2}, {59, 10}}, {{60, 
   2}, {60, 6}}, {{61, 7}, {61, 9}}, {{62, 8}}, {{63, 3}, {63, 
   6}}, {{64, 1}, {64, 2}}, {{65, 2}}, {{66, 1}, {66, 2}, {66, 
   8}, {66, 9}}, {{68, 2}, {68, 8}}, {{69, 1}, {69, 6}}, {{70, 
   1}, {70, 2}, {70, 7}, {70, 9}}, {{72, 4}}, {{73, 3}, {73, 
   6}}, {{74, 8}}, {{75, 1}, {75, 6}}, {{76, 1}, {76, 2}, {76, 
   6}, {76, 10}}, {{77, 4}, {77, 8}}, {{78, 3}}, {{79, 1}, {79, 
   9}}, {{81, 3}}, {{82, 1}}, {{83, 2}, {83, 6}}, {{84, 1}, {84, 
   8}}, {{85, 2}}, {{86, 2}}, {{87, 1}, {87, 3}, {87, 8}}, {{88, 
   8}}, {{89, 2}, {89, 10}}, {{90, 1}, {90, 10}}, {{91, 1}, {91, 
   6}}, {{92, 4}}, {{93, 2}, {93, 3}, {93, 4}, {93, 7}}, {{94, 
   2}, {94, 3}}, {{96, 1}, {96, 2}, {96, 3}, {96, 6}, {96, 10}}, {{97,
    1}}, {{98, 4}}, {{99, 1}, {99, 10}}, {{100, 1}, {100, 2}, {100, 
   3}, {100, 7}, {100, 8}}, {{101, 2}}, {{103, 2}, {103, 3}, {103, 
   10}}, {{105, 3}, {105, 4}, {105, 7}, {105, 9}}, {{106, 1}}, {{108, 
   6}}, {{109, 3}}, {{110, 4}}, {{111, 6}, {111, 8}}, {{112, 1}, {112,
    3}, {112, 9}}, {{114, 1}, {114, 2}, {114, 9}}, {{115, 1}, {115, 
   2}, {115, 3}, {115, 7}}, {{116, 6}}, {{117, 1}, {117, 3}, {117, 
   4}, {117, 8}}, {{118, 6}, {118, 7}, {118, 8}}, {{119, 4}}, {{120, 
   1}, {120, 2}, {120, 3}, {120, 4}, {120, 10}}, {{121, 1}, {121, 
   9}}, {{122, 4}, {122, 8}}, {{124, 3}, {124, 10}}, {{125, 2}, {125, 
   4}, {125, 8}}, {{126, 1}, {126, 2}, {126, 8}}, {{127, 3}}, {{129, 
   1}, {129, 3}}, {{130, 2}}, {{131, 2}}, {{132, 1}, {132, 4}, {132, 
   7}, {132, 8}}, {{133, 8}}, {{134, 2}, {134, 10}}, {{135, 1}, {135, 
   3}, {135, 6}}, {{136, 1}}, {{138, 2}}, {{139, 1}, {139, 3}}, {{140,
    2}, {140, 8}}, {{141, 1}, {141, 2}}, {{142, 1}, {142, 7}, {142, 
   9}}, {{143, 4}, {143, 6}}, {{144, 2}, {144, 9}}, {{145, 2}, {145, 
   3}}, {{146, 8}}, {{147, 1}, {147, 9}}, {{148, 2}, {148, 6}}, {{149,
    2}, {149, 8}}, {{150, 3}}, {{151, 3}}, {{153, 2}, {153, 
   8}}, {{154, 1}, {154, 2}}, {{155, 2}, {155, 10}}, {{156, 
   1}}, {{157, 1}, {157, 4}}, {{158, 2}}, {{159, 1}, {159, 2}, {159, 
   6}, {159, 7}}, {{160, 2}, {160, 8}}, {{162, 8}}, {{163, 2}, {163, 
   7}}, {{164, 2}, {164, 4}, {164, 8}, {164, 10}}, {{165, 3}, {165, 
   8}, {165, 9}}, {{166, 1}, {166, 3}, {166, 9}}, {{168, 8}, {168, 
   10}}, {{169, 1}, {169, 2}, {169, 7}}, {{171, 2}, {171, 3}, {171, 
   8}}, {{172, 9}}, {{174, 1}, {174, 2}, {174, 9}}, {{175, 1}}, {{176,
    2}}, {{177, 1}}, {{178, 3}, {178, 10}}, {{180, 1}, {180, 2}, {180,
    7}, {180, 8}}, {{181, 2}, {181, 8}}, {{182, 4}}, {{183, 6}, {183, 
   8}}, {{184, 1}, {184, 2}, {184, 7}}, {{185, 10}}, {{186, 
   2}}, {{187, 1}}, {{188, 2}, {188, 6}, {188, 8}}, {{189, 3}, {189, 
   6}}, {{190, 1}}, {{191, 2}, {191, 6}}, {{192, 1}, {192, 3}}, {{193,
    2}}, {{195, 1}, {195, 2}}, {{196, 2}, {196, 7}}, {{198, 
   3}}, {{199, 1}, {199, 2}, {199, 3}, {199, 9}}, {{201, 1}, {201, 
   4}, {201, 6}}, {{202, 3}}, {{203, 2}}, {{204, 3}, {204, 4}}, {{205,
    1}, {205, 4}}, {{206, 2}, {206, 6}}, {{208, 7}}, {{209, 2}, {209, 
   8}}, {{210, 1}}, {{211, 1}, {211, 7}}, {{215, 2}}, {{216, 1}, {216,
    3}, {216, 8}, {216, 9}}, {{217, 1}}, {{218, 2}}, {{219, 
   2}}, {{220, 1}, {220, 2}}, {{221, 8}}, {{222, 1}}, {{223, 
   3}}, {{225, 1}, {225, 2}}, {{228, 3}}, {{229, 1}, {229, 4}, {229, 
   9}}, {{230, 2}, {230, 6}, {230, 8}, {230, 10}}, {{231, 1}, {231, 
   2}, {231, 4}, {231, 6}}, {{232, 1}}, {{233, 2}}, {{234, 1}, {234, 
   6}}, {{235, 8}}, {{236, 2}}, {{240, 1}, {240, 2}}, {{241, 2}, {241,
    3}}, {{243, 3}}, {{244, 1}, {244, 2}, {244, 9}}, {{246, 1}, {246, 
   2}, {246, 3}}, {{247, 7}}, {{248, 2}, {248, 6}, {248, 8}}, {{250, 
   1}}, {{252, 1}}, {{253, 8}}, {{254, 6}, {254, 8}}, {{255, 1}, {255,
    6}, {255, 7}}, {{256, 9}}, {{258, 2}, {258, 3}}, {{259, 2}, {259, 
   3}, {259, 7}}, {{260, 6}, {260, 8}}, {{261, 1}}, {{262, 1}}, {{263,
    2}}, {{264, 2}}, {{265, 2}, {265, 8}}, {{266, 4}}, {{268, 
   2}}, {{271, 1}, {271, 6}}, {{274, 1}}, {{275, 4}}, {{276, 
   7}}, {{279, 1}, {279, 4}}, {{280, 8}}, {{281, 2}}, {{282, 
   1}}, {{283, 3}}, {{285, 1}, {285, 2}, {285, 3}}, {{286, 1}, {286, 
   3}, {286, 4}}, {{288, 2}, {288, 4}}, {{289, 1}, {289, 6}}, {{290, 
   2}, {290, 4}, {290, 8}}, {{291, 9}}, {{292, 4}, {292, 8}}, {{293, 
   4}}, {{294, 1}, {294, 2}}, {{296, 2}}, {{297, 1}}, {{298, 
   2}}, {{300, 1}, {300, 3}}, {{301, 1}, {301, 2}}, {{303, 2}}, {{304,
    1}, {304, 4}}, {{305, 2}, {305, 6}}, {{306, 2}}, {{307, 1}, {307, 
   7}}, {{308, 10}}, {{309, 1}, {309, 2}, {309, 4}}, {{310, 1}, {310, 
   3}, {310, 8}}, {{312, 8}}, {{313, 3}}, {{314, 2}}, {{316, 1}, {316,
    3}}, {{318, 4}}, {{319, 2}, {319, 3}}, {{321, 1}, {321, 
   4}}, {{322, 1}, {322, 4}}, {{323, 2}, {323, 6}}, {{324, 1}, {324, 
   10}}, {{326, 8}}, {{327, 1}, {327, 7}, {327, 8}}, {{328, 
   6}}, {{329, 4}}, {{330, 1}, {330, 2}, {330, 4}, {330, 9}}, {{331, 
   1}, {331, 2}, {331, 6}}, {{334, 3}, {334, 4}}, {{335, 2}}, {{336, 
   10}}, {{337, 1}}, {{339, 1}, {339, 2}, {339, 10}}, {{342, 
   1}}, {{343, 2}, {343, 3}}, {{344, 4}}, {{346, 1}, {346, 9}}, {{348,
    3}, {348, 6}}, {{349, 2}, {349, 6}}, {{350, 2}, {350, 4}}, {{351, 
   1}, {351, 2}, {351, 4}, {351, 10}}, {{352, 3}, {352, 7}}, {{353, 
   4}}, {{354, 2}}, {{355, 1}}, {{356, 8}}, {{358, 2}}, {{360, 
   1}, {360, 2}, {360, 3}, {360, 8}}, {{361, 2}}, {{363, 4}}, {{364, 
   1}, {364, 2}}, {{366, 3}, {366, 4}, {366, 10}}, {{367, 1}, {367, 
   3}, {367, 8}}, {{370, 1}, {370, 9}}, {{371, 6}}, {{372, 1}}, {{373,
    2}, {373, 4}, {373, 6}}, {{374, 2}}, {{375, 6}}, {{376, 1}, {376, 
   3}}, {{378, 2}}, {{379, 1}, {379, 3}}, {{380, 2}, {380, 6}}, {{381,
    1}, {381, 3}, {381, 7}}, {{385, 1}, {385, 2}, {385, 6}, {385, 
   7}, {385, 8}}, {{386, 2}, {386, 6}}, {{387, 1}, {387, 7}, {387, 
   9}}, {{390, 4}}, {{391, 2}, {391, 3}}, {{393, 2}, {393, 6}, {393, 
   8}}, {{394, 1}}, {{395, 2}, {395, 10}}, {{396, 2}}, {{397, 
   4}}, {{398, 4}, {398, 8}}, {{399, 1}, {399, 4}}, {{401, 2}, {401, 
   6}}, {{405, 1}, {405, 2}}, {{406, 1}, {406, 4}, {406, 7}}, {{407, 
   4}}, {{408, 2}, {408, 4}, {408, 7}}, {{409, 4}, {409, 8}}, {{411, 
   1}}, {{412, 1}, {412, 3}}, {{414, 1}, {414, 6}}, {{415, 1}}, {{417,
    3}}, {{418, 2}, {418, 3}}, {{419, 2}}, {{420, 1}, {420, 2}, {420, 
   6}}, {{421, 3}}, {{423, 2}, {423, 8}}, {{424, 3}, {424, 8}}, {{426,
    3}, {426, 8}}, {{427, 1}}, {{428, 2}}, {{429, 1}, {429, 3}, {429, 
   8}}, {{430, 1}, {430, 3}}, {{431, 2}}, {{432, 1}, {432, 3}}, {{433,
    2}}, {{434, 8}}, {{435, 9}}, {{437, 8}}, {{438, 6}}, {{439, 
   1}, {439, 10}}, {{440, 8}}, {{441, 1}}, {{442, 1}}, {{443, 
   6}}, {{444, 1}, {444, 3}}, {{445, 2}}, {{446, 8}}, {{447, 
   8}}, {{448, 2}}, {{449, 2}}, {{450, 2}, {450, 3}}, {{451, 
   8}}, {{453, 2}}, {{454, 1}, {454, 3}}, {{455, 2}, {455, 4}}, {{456,
    1}, {456, 2}, {456, 7}}, {{459, 3}}, {{460, 1}, {460, 4}, {460, 
   6}}, {{461, 2}}, {{462, 7}}, {{463, 2}, {463, 4}}, {{465, 
   1}}, {{466, 3}, {466, 6}}, {{468, 2}, {468, 3}}, {{469, 1}, {469, 
   3}, {469, 4}, {469, 6}}, {{471, 1}, {471, 2}, {471, 6}}, {{472, 
   3}, {472, 4}, {472, 9}}, {{473, 2}, {473, 8}}, {{474, 1}, {474, 
   2}}, {{475, 2}}, {{477, 1}}, {{478, 2}}, {{481, 2}, {481, 
   3}}, {{482, 4}}, {{483, 4}, {483, 7}}, {{484, 1}, {484, 3}}, {{486,
    1}, {486, 2}, {486, 3}, {486, 9}}, {{489, 1}, {489, 3}, {489, 
   9}, {489, 10}}, {{490, 2}}, {{492, 1}}, {{493, 6}}, {{494, 
   2}, {494, 6}}, {{495, 2}, {495, 9}}, {{496, 1}, {496, 2}}, {{499, 
   1}, {499, 2}, {499, 7}}, {{500, 2}}, {{501, 2}}, {{502, 4}}, {{504,
    2}}, {{505, 1}, {505, 3}}, {{506, 2}, {506, 4}}, {{507, 1}, {507, 
   4}}, {{508, 6}}, {{510, 1}, {510, 2}, {510, 3}}, {{511, 1}, {511, 
   2}}, {{513, 4}}, {{514, 3}, {514, 10}}, {{515, 2}, {515, 
   6}}, {{516, 1}, {516, 4}}, {{517, 1}}, {{518, 2}}, {{519, 2}, {519,
    8}}, {{520, 1}, {520, 4}, {520, 6}}, {{521, 4}, {521, 10}}, {{522,
    3}}, {{524, 4}}, {{525, 1}, {525, 6}}, {{526, 1}}, {{528, 
   2}, {528, 3}, {528, 7}, {528, 10}}, {{529, 9}}, {{530, 2}}, {{531, 
   1}}, {{532, 1}, {532, 3}, {532, 7}}, {{534, 4}}, {{535, 1}, {535, 
   3}, {535, 4}}, {{537, 9}}, {{538, 3}, {538, 4}, {538, 7}}, {{539, 
   4}}, {{540, 6}, {540, 7}}, {{541, 2}, {541, 3}}, {{542, 4}}, {{543,
    8}}, {{544, 1}, {544, 2}, {544, 6}, {544, 8}, {544, 9}, {544, 
   10}}, {{546, 1}, {546, 7}}, {{547, 1}}, {{548, 2}}, {{549, 
   1}, {549, 2}}, {{550, 2}}, {{551, 2}, {551, 6}}, {{552, 1}}, {{553,
    3}, {553, 4}}, {{554, 4}, {554, 8}}, {{555, 1}, {555, 4}, {555, 
   6}, {555, 8}}, {{556, 4}}, {{558, 3}, {558, 10}}, {{559, 1}, {559, 
   6}, {559, 9}}, {{560, 2}}, {{561, 2}, {561, 4}}, {{562, 1}, {562, 
   3}, {562, 4}}, {{564, 9}}, {{565, 1}, {565, 8}}, {{566, 
   10}}, {{567, 4}, {567, 8}}, {{568, 3}}, {{569, 2}}, {{571, 
   2}}, {{572, 4}}, {{573, 2}, {573, 4}}, {{574, 3}, {574, 4}}, {{576,
    1}}, {{577, 1}, {577, 4}}, {{578, 2}}, {{579, 3}}, {{580, 
   8}, {580, 10}}, {{581, 2}, {581, 4}}, {{582, 1}, {582, 3}}, {{585, 
   6}}, {{586, 1}, {586, 9}, {586, 10}}, {{588, 2}}, {{589, 
   2}}, {{590, 4}}, {{591, 1}, {591, 2}}, {{593, 10}}, {{594, 
   1}, {594, 2}, {594, 7}, {594, 10}}, {{595, 2}, {595, 8}}, {{596, 
   2}}, {{597, 1}}, {{598, 2}, {598, 4}}, {{599, 8}}, {{601, 1}, {601,
    10}}, {{604, 2}}, {{605, 4}}, {{606, 2}}, {{607, 1}}, {{608, 
   4}, {608, 10}}, {{609, 1}, {609, 10}}, {{610, 2}, {610, 3}}, {{612,
    1}, {612, 4}, {612, 9}}, {{613, 8}}, {{615, 1}, {615, 3}, {615, 
   8}}, {{616, 1}, {616, 2}, {616, 10}}, {{618, 2}}, {{619, 1}, {619, 
   4}}, {{623, 4}, {623, 6}}, {{624, 2}, {624, 9}}, {{625, 1}, {625, 
   2}, {625, 4}, {625, 9}, {625, 10}}, {{628, 6}}, {{629, 2}, {629, 
   4}, {629, 10}}, {{630, 1}, {630, 8}, {630, 9}}, {{631, 3}, {631, 
   10}}, {{633, 2}}, {{634, 6}}, {{635, 10}}, {{637, 8}}, {{639, 
   1}, {639, 2}, {639, 4}}, {{640, 1}, {640, 2}}, {{641, 8}}, {{642, 
   1}, {642, 3}}, {{643, 8}}, {{644, 2}, {644, 4}}, {{645, 1}, {645, 
   7}}, {{646, 1}, {646, 2}}, {{648, 2}}, {{649, 1}, {649, 7}, {649, 
   10}}, {{651, 1}, {651, 2}, {651, 8}}, {{652, 1}, {652, 4}}, {{654, 
   1}, {654, 2}}, {{655, 2}}, {{656, 6}}, {{658, 7}}, {{659, 2}, {659,
    6}, {659, 8}}, {{660, 1}, {660, 3}, {660, 6}}, {{661, 1}, {661, 
   3}}, {{663, 6}}, {{664, 1}, {664, 4}}, {{665, 10}}, {{666, 
   3}, {666, 4}, {666, 7}}, {{667, 3}}, {{668, 2}, {668, 6}}, {{670, 
   2}, {670, 6}, {670, 9}}, {{673, 2}}, {{674, 10}}, {{675, 
   8}}, {{676, 2}, {676, 8}, {676, 9}}, {{681, 1}, {681, 10}}, {{683, 
   2}}, {{684, 1}, {684, 3}, {684, 4}, {684, 7}}, {{685, 3}}, {{686, 
   2}, {686, 10}}, {{687, 1}, {687, 3}}, {{688, 3}, {688, 4}, {688, 
   6}, {688, 10}}, {{690, 3}, {690, 8}}, {{691, 1}, {691, 2}}, {{693, 
   2}, {693, 10}}, {{694, 3}}, {{695, 2}}, {{697, 3}}, {{699, 
   2}}, {{700, 1}}, {{703, 6}}, {{705, 1}, {705, 2}}, {{706, 2}, {706,
    8}}, {{708, 2}}, {{709, 2}}, {{710, 10}}, {{711, 9}}, {{712, 
   1}}, {{714, 1}, {714, 4}, {714, 8}}, {{715, 1}, {715, 2}, {715, 
   7}}, {{716, 2}}, {{717, 1}, {717, 4}}, {{720, 1}, {720, 2}}, {{721,
    4}, {721, 8}}, {{722, 4}}, {{723, 3}}, {{724, 1}, {724, 
   2}}, {{726, 1}, {726, 3}}, {{727, 1}, {727, 4}}, {{728, 2}, {728, 
   10}}, {{730, 1}, {730, 10}}, {{731, 4}, {731, 10}}, {{733, 
   3}}, {{736, 1}}, {{738, 10}}, {{739, 2}, {739, 3}, {739, 
   9}}, {{741, 1}, {741, 4}, {741, 7}}, {{742, 1}, {742, 3}}, {{743, 
   2}, {743, 4}}, {{744, 1}}, {{745, 1}}, {{746, 2}}, {{747, 
   1}}, {{748, 4}}, {{750, 1}, {750, 2}, {750, 3}}, {{751, 3}, {751, 
   8}}, {{753, 2}, {753, 3}}, {{754, 2}}, {{755, 10}}, {{756, 
   1}}, {{757, 7}}, {{759, 7}}, {{761, 2}}, {{762, 1}, {762, 
   4}}, {{763, 2}, {763, 3}, {763, 4}, {763, 8}}, {{765, 2}}, {{766, 
   1}, {766, 6}}, {{768, 10}}, {{769, 2}, {769, 3}, {769, 9}}, {{770, 
   6}}, {{771, 6}}, {{772, 1}}, {{774, 6}, {774, 8}}, {{775, 1}, {775,
    6}, {775, 10}}, {{776, 2}, {776, 4}}, {{777, 1}, {777, 3}}, {{778,
    8}}, {{779, 2}, {779, 6}}, {{780, 1}, {780, 2}, {780, 4}}, {{781, 
   2}, {781, 8}}, {{783, 3}}, {{784, 1}, {784, 3}}, {{786, 1}, {786, 
   2}, {786, 4}}, {{787, 7}}, {{789, 9}}, {{790, 1}, {790, 6}, {790, 
   9}}, {{792, 1}, {792, 8}}, {{794, 2}}, {{795, 8}}, {{796, 6}, {796,
    8}}, {{797, 8}}, {{798, 2}, {798, 6}, {798, 7}}, {{799, 
   1}}, {{800, 6}, {800, 8}}, {{801, 1}}, {{803, 2}, {803, 4}, {803, 
   10}}, {{804, 1}, {804, 2}, {804, 7}}, {{805, 1}}, {{807, 1}, {807, 
   4}, {807, 8}}, {{808, 8}}, {{809, 2}}, {{810, 1}, {810, 9}}, {{811,
    1}}, {{813, 6}}, {{814, 1}, {814, 2}, {814, 3}, {814, 4}, {814, 
   9}}, {{815, 2}, {815, 8}, {815, 10}}, {{816, 2}, {816, 3}, {816, 
   9}}, {{819, 1}, {819, 3}}, {{825, 2}, {825, 10}}, {{828, 
   3}}, {{829, 1}, {829, 3}}, {{831, 6}}, {{832, 1}, {832, 3}, {832, 
   4}}, {{833, 2}, {833, 8}}, {{834, 1}, {834, 4}, {834, 9}}, {{835, 
   1}, {835, 3}}, {{836, 10}}, {{837, 3}}, {{838, 2}}, {{839, 
   8}}, {{841, 3}}, {{843, 3}}, {{845, 2}, {845, 4}}, {{846, 
   10}}, {{847, 1}}, {{848, 2}, {848, 6}}, {{849, 1}}, {{850, 
   1}, {850, 4}, {850, 9}}, {{852, 8}}, {{853, 10}}, {{855, 
   1}}, {{856, 2}, {856, 10}}, {{857, 4}}, {{860, 4}}, {{861, 
   1}, {861, 3}, {861, 4}}, {{862, 1}}, {{863, 2}}, {{866, 6}}, {{867,
    1}}, {{868, 6}}, {{869, 6}}, {{870, 7}}, {{871, 1}, {871, 
   3}, {871, 8}}, {{873, 2}, {873, 4}}, {{874, 1}}, {{875, 6}, {875, 
   8}}, {{876, 4}}, {{877, 1}, {877, 7}}, {{879, 3}}, {{880, 1}, {880,
    6}, {880, 10}}, {{881, 2}}, {{882, 3}}, {{883, 4}}, {{884, 
   2}}, {{885, 2}}, {{888, 3}}, {{889, 1}, {889, 2}}, {{890, 2}, {890,
    4}, {890, 6}}, {{891, 4}}, {{892, 1}}, {{894, 1}, {894, 6}, {894, 
   10}}, {{895, 1}}, {{897, 3}}, {{898, 10}}, {{901, 1}, {901, 
   2}, {901, 8}}, {{906, 1}, {906, 2}, {906, 8}}, {{909, 3}, {909, 
   8}, {909, 9}}, {{910, 3}}, {{912, 1}}, {{913, 4}, {913, 7}}, {{915,
    2}}, {{916, 1}, {916, 8}}, {{917, 8}}, {{918, 6}}, {{919, 
   8}, {919, 9}}, {{921, 2}, {921, 8}}, {{922, 4}}, {{923, 2}}, {{924,
    1}, {924, 4}, {924, 7}}, {{925, 2}, {925, 4}}, {{926, 6}}, {{928, 
   6}}, {{930, 2}, {930, 9}}, {{931, 1}, {931, 6}}, {{934, 1}}, {{936,
    1}}, {{937, 1}, {937, 7}}, {{938, 4}, {938, 10}}, {{939, 1}, {939,
    2}, {939, 8}}, {{940, 1}, {940, 3}, {940, 9}, {940, 10}}, {{941, 
   2}}, {{943, 3}}, {{944, 2}}, {{945, 1}, {945, 9}}, {{946, 2}, {946,
    4}}, {{948, 3}, {948, 4}}, {{950, 2}, {950, 6}, {950, 8}}, {{951, 
   1}, {951, 4}, {951, 8}}, {{952, 4}}, {{953, 4}}, {{954, 1}}, {{955,
    2}, {955, 4}, {955, 7}}, {{956, 2}}, {{957, 1}}, {{960, 
   6}}, {{961, 8}}, {{963, 2}}, {{965, 2}}, {{966, 1}, {966, 
   2}}, {{967, 1}}, {{968, 2}}, {{969, 3}, {969, 8}}, {{970, 3}, {970,
    6}, {970, 9}}, {{972, 3}}, {{974, 2}}, {{975, 1}}, {{976, 
   1}, {976, 2}, {976, 6}}, {{979, 4}, {979, 8}, {979, 9}}, {{980, 
   4}}, {{981, 2}, {981, 4}}, {{982, 3}, {982, 8}}, {{984, 2}, {984, 
   3}, {984, 6}}, {{987, 1}, {987, 3}}, {{988, 6}}, {{989, 2}, {989, 
   10}}, {{990, 1}, {990, 3}}, {{991, 3}}, {{992, 4}}, {{994, 
   1}, {994, 2}, {994, 6}}, {{996, 2}, {996, 3}, {996, 4}, {996, 
   6}}, {{997, 1}}, {{998, 2}}, {{999, 1}, {999, 9}}, {{1000, 
   1}, {1000, 2}}}

So, we can see that using the bounds $1\le\text{n}\le10^3$ and $1\le\text{k}\le10$ we found $1419$ solutions. That number is found by using the following Mathematica-code:

In[2]:=Clear["Global`*"];
\[Alpha] = 10^3;
\[Beta] = 10^1;
f = Total@*Map[Length];
f[ParallelTable[
   If[PrimeQ[n^k + n - 1], {n, k}, Nothing], {n, 1, \[Alpha]}, {k, 
    1, \[Beta]}] //. {} -> Nothing]

Out[2]=1419

Extending the bounds to $1\le\text{n}\le10^4$ and $1\le\text{k}\le10^2$ gives $19235$ solutions.

I did a search to find solutions for $\text{n}=107$. I did find a solution for $1\le\text{k}\le5\cdot10^3$ because when $\text{k}=1400$ the number $\text{n}^\text{k}+\text{n}-1$ is prime.

I also searched for solutions of $\text{n}$ and $\text{k}$ such that $\text{k}\ne6\text{m}+5$ (where $\text{m}\in\mathbb{N}$). I did find solutions for $1\le\text{n}\le10^2$ and $1\le\text{k}\le10$:

In[3]:=Clear["Global`*"];
\[Alpha] = 10^2;
\[Beta] = 10^1;
ParallelTable[
  If[TrueQ[PrimeQ[n^k + n - 1] && IntegerQ[(k - 5)/6] == False], {n, 
    k}, Nothing], {n, 1, \[Alpha]}, {k, 1, \[Beta]}] //. {} -> Nothing

Out[3]={{{2, 1}, {2, 2}, {2, 4}, {2, 8}}, {{3, 1}, {3, 2}, {3, 3}, {3, 
   4}, {3, 8}, {3, 10}}, {{4, 1}, {4, 2}, {4, 3}, {4, 6}, {4, 8}, {4, 
   9}}, {{5, 2}, {5, 6}, {5, 10}}, {{6, 1}, {6, 2}, {6, 4}, {6, 
   7}, {6, 10}}, {{7, 1}, {7, 3}}, {{8, 2}, {8, 6}, {8, 10}}, {{9, 
   1}, {9, 2}, {9, 4}, {9, 7}, {9, 10}}, {{10, 1}, {10, 2}, {10, 
   3}, {10, 4}, {10, 9}}, {{11, 2}, {11, 8}}, {{12, 1}, {12, 
   4}}, {{13, 2}, {13, 4}, {13, 10}}, {{15, 1}, {15, 2}, {15, 3}, {15,
    9}}, {{16, 1}, {16, 2}, {16, 3}, {16, 4}, {16, 8}, {16, 
   10}}, {{17, 4}, {17, 8}}, {{18, 3}, {18, 6}}, {{19, 1}, {19, 
   2}}, {{20, 2}, {20, 4}}, {{21, 1}, {21, 2}, {21, 3}}, {{22, 
   1}, {22, 7}}, {{23, 4}, {23, 6}}, {{24, 1}, {24, 2}, {24, 
   10}}, {{25, 3}, {25, 8}}, {{26, 2}, {26, 4}, {26, 10}}, {{27, 
   1}, {27, 3}, {27, 8}}, {{28, 2}, {28, 4}}, {{29, 10}}, {{30, 
   1}, {30, 2}, {30, 7}}, {{31, 1}, {31, 2}, {31, 4}, {31, 6}, {31, 
   10}}, {{33, 3}, {33, 4}}, {{34, 1}, {34, 6}}, {{35, 2}}, {{36, 
   1}, {36, 3}, {36, 6}}, {{37, 1}, {37, 7}}, {{38, 2}}, {{39, 
   2}, {39, 3}}, {{40, 1}, {40, 4}, {40, 10}}, {{41, 2}}, {{42, 
   1}}, {{43, 3}, {43, 4}}, {{44, 2}, {44, 4}}, {{45, 1}, {45, 
   2}}, {{46, 2}, {46, 3}, {46, 8}}, {{48, 2}}, {{49, 1}, {49, 
   7}, {49, 9}}, {{50, 2}, {50, 6}, {50, 8}}, {{51, 1}, {51, 3}, {51, 
   6}, {51, 10}}, {{52, 1}, {52, 3}}, {{53, 2}, {53, 6}}, {{54, 
   1}, {54, 2}, {54, 4}}, {{55, 1}, {55, 2}, {55, 3}}, {{56, 2}, {56, 
   6}}, {{57, 1}, {57, 9}}, {{58, 4}}, {{59, 2}, {59, 10}}, {{60, 
   2}, {60, 6}}, {{61, 7}, {61, 9}}, {{62, 8}}, {{63, 3}, {63, 
   6}}, {{64, 1}, {64, 2}}, {{65, 2}}, {{66, 1}, {66, 2}, {66, 
   8}, {66, 9}}, {{68, 2}, {68, 8}}, {{69, 1}, {69, 6}}, {{70, 
   1}, {70, 2}, {70, 7}, {70, 9}}, {{72, 4}}, {{73, 3}, {73, 
   6}}, {{74, 8}}, {{75, 1}, {75, 6}}, {{76, 1}, {76, 2}, {76, 
   6}, {76, 10}}, {{77, 4}, {77, 8}}, {{78, 3}}, {{79, 1}, {79, 
   9}}, {{81, 3}}, {{82, 1}}, {{83, 2}, {83, 6}}, {{84, 1}, {84, 
   8}}, {{85, 2}}, {{86, 2}}, {{87, 1}, {87, 3}, {87, 8}}, {{88, 
   8}}, {{89, 2}, {89, 10}}, {{90, 1}, {90, 10}}, {{91, 1}, {91, 
   6}}, {{92, 4}}, {{93, 2}, {93, 3}, {93, 4}, {93, 7}}, {{94, 
   2}, {94, 3}}, {{96, 1}, {96, 2}, {96, 3}, {96, 6}, {96, 10}}, {{97,
    1}}, {{98, 4}}, {{99, 1}, {99, 10}}, {{100, 1}, {100, 2}, {100, 
   3}, {100, 7}, {100, 8}}}
$\endgroup$
2
  • 2
    $\begingroup$ Thank you! Notably, this confirms conjecture $3$ for $k=9$ ($n=172$) $\endgroup$
    – Michał Zapała
    Dec 29, 2020 at 14:47
  • $\begingroup$ @MichałZapała You're welcome, I am glad that I could help you. $\endgroup$
    – Jan Eerland
    Dec 29, 2020 at 14:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.