Primes in the form $n^{k}+n-1$

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.

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

To my untrained eye, this seems approachable.

• Unsurprizingly, turns out the sequence is known in OEIS as A076845; but the list ends at 100 Dec 28, 2020 at 22:38
• 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. Dec 29, 2020 at 9:00
• @MichałZapała. For $1$ to $100$ it is almost immediate. After, it takes a lot of time. Dec 29, 2020 at 9:09
• A few more $\{2,44,2,14,3,1,1400,6,3,4,6,1,1\}$ Dec 29, 2020 at 9:12
• @Peter, $n^{6m+5}+n-1$ is divisible by $n^2-n+1$. Dec 29, 2020 at 9:39

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}}}
`
• Thank you! Notably, this confirms conjecture $3$ for $k=9$ ($n=172$) Dec 29, 2020 at 14:47
• @MichałZapała You're welcome, I am glad that I could help you. Dec 29, 2020 at 14:48