x=n^8-1+n^4;
y=x;
a=((x+y/2+x-y-1)/(x-y-1))-((x+y))/(x+y)/2;
r=IntegerPart[a];
g1=Mod[r,9961];
g2={45,4135,5383,7767,9401,9489,9829,10745,11789,11869,13355,14157,15539,15661,16207,16741,17213,17871,21667,21761,23075,23513,23825,24849,25037,25391,27429,27995,28057,28817,28905,33455,34101,34309,35715,37665,38889,41289,41293,43755,44557,46179,46449,48081,48201,48505,49403,49591,50981,55977,59539,59615,60347,60445,61873,63161,64265,64823,66081,67999,68433,69797,70483,72715,73433,76689,77729,77849,79141,82955,83067,83989,84255,85847,86069,86735,88459,89137,90367,92033,92055,94177,95083,95085,96315,98367,98657,98743,99935,99969,100421,100615,101545,101951,103891,104001,104507,107501,111191,111907,112949,115127,116821,117673,118865,119565,120607,122585,123637,126895,126909,130539,131151,131817,132237,132469,132715,133011,133789,134343,134501,134699,136047,136523,136755,136901,136913,137671,138429,138765,139839,144641,147109,147939,148815,152289,153215,153457,154757,156295,156369,156991,157461,157801,157811,159031,160523,160949,161015,162001,164775,165289,165585,168357,170317,171235,171941,173859,174077,176015,176151,176665,178349,180629,182793,183943,184005,187147,187745,188907,189529,190525,190877,191085,191255,191665,193547,198283,200441,200891,201313,203093,204771,205055,205343,210035,212633,214271,214295,215287,216531,218129,222667,224089,224859,224957,225503,226139,226817,226927,227185,227623,228383,229651,229691,230237,231703,232033,233239,236265,237123,239013,239069,239305,240721,241311,242547,244047,244341,245863,246053,247351,247433,247607,248381,248477,249011,251683,252871,255105,255997,256143,257725,257929,258599,263119,264825,265503,266603,267359,270803,271719,272051,272535,274813,276561,277471,277899,278523,279091,279149,280001,280483,281149,281483,285265,286567,286721,287113,287471,289343,290037,290307,290629,290635,294279,295781,298281,301077,304275,305751,307791,309469,309571,310017,310229,310271,312695,313307,313801,315397,316913,319541,320385,321801,325007,326623,326847,328807,331447,331883,332793,338193,338873,341187,342171,342315,343251,345943,346639,347657,349873,350025,350393,353647,357267,360201,361119,361693,362075,362213,362345,363453,363867,363923,368347,370739,371793,374975,375749,377365,377499,377637,381333,381555,381963,383653,384753,385435,385777,386951,387943,388527,388583,388743,389171,389817,391129,391135,392531,392837,393951,398409,400379,401251,402509,402925,404401,405757,406445,407495,408461,409185,410009,411119,415005,417667,420091,420845,421281,421355,421591,421633,422833,424087,424143,424349,425165,425171,427531,428251,428985,429265,429747,431065,431407,431485,431827,433151,433661,436595,437011,438181,438375,438827,439055,439853,440999,441277,442239,442339,444367,444563,444647,448003,449149,449955,451039,452565,454747,455347,455609,455667,455977,457233,457555,457929,458229,458279,458617,461963,463425,463765,463849,464703,465081,465517,467539,467605,468599,469957,470453,470523,471229,471371,471429,472047,472075,473155,473645,477335,477531,478425,478753,480029,481957,482895,483385,484321,486053,486067,488343,489177,489179,490537,490881,491103,491241,496681,497227,497933,498243,498873,499053,499245,501157,501253,501615,502761,503565,504979,505395,508095,508391,508991,509077,509083,510049,510183,511565,511633,512737,512749,513943,514229,516989,517305,517403,518075,519473,520547,522385,522695,524865,526467,527221,529145,529659,531071,534465,534485,536827,537281,537879,540553,541349,543909,544125,544561,544781,545121,546231,548319,550693,551005,552539,553469,553669,554431,557005,558067,561763,562645,565439,566799,566975,567905,570345,572529,573015,574071,574477,576501,578231,579491,580621,581007,581341,582447,583417,583691,584337,585057,585603,585679,586512,586625}
ClearAll@f
f[n_] := Module[{x, y, a, r},
x = n^8-1+n^4;
y = x;
a = ((x + y/2 + x - y - 1)/(x - y - 1)) - ((x + y))/(x + y)/2;
r = IntegerPart[a];
Mod[r, 586918]]
Table[If[MemberQ[g2, f[n]], {n, f[n]}, Nothing], {n, 1, 9961}]
Table[If[MemberQ[g2, f[n]], {n,n^8-1+n^4, f[n]}, Nothing], {n, 1, 9961}]
Table[If[MemberQ[g2, f[n]], {n,PrimeQ[n^8-1+n^4], f[n]}, Nothing], {n, 1, 9961}]
result:
{2,True,586512},{5,True,45},{19,True,222667},{53,True,132237},{79,True,279091},{193,True,463765},{281,True,350025},{503,True,425165},{547,True,529659},{857,False,227185},{907,True,67999},{911,True,566799},{967,True,428985},{1009,True,491241},{1069,True,398409},{1091,True,88459},{1097,True,126909},{1213,True,200891},{1487,True,134343},{1493,True,455667},{1861,True,136047},{1867,True,536827},{1881,False,509077},{2137,True,531071},{2297,True,210035},{2357,True,529145},{2389,True,72715},{2477,True,165289},{2593,True,244047},{2659,True,483385},{2957,True,134699},{3347,True,463425},{3499,True,534485},{3539,True,546231},{3691,True,236265},{3797,True,457555},{4001,True,68433},{4007,True,229651},{4093,True,455609},{4157,False,16741},{4229,True,133011},{4339,True,363453},{4409,True,272535},{4721,True,470453},{4831,True,458229},{4931,True,162001},{4951,True,424143},{4973,True,585603},{5153,True,457233},{5179,True,239013},{5261,False,381555},{5279,True,83067},{5393,True,482895},{5483,True,313801},{5519,True,345943},{5573,False,48081},{5659,True,534465},{5841,False,160949},{6047,True,392837},{6113,True,258599},{6133,False,346639},{6163,True,98657},{6367,True,342171},{6691,True,82955},{6917,True,458279},{7001,True,76689},{7411,True,24849},{7457,True,14157},{7793,True,115127},{7829,True,79141},{7963,True,136523},{8017,True,503565},{8053,True,512749},{8447,True,157811},{8647,True,133789},{8779,True,164775},{8861,True,286721},{8863,True,256143},{8923,True,137671},{8951,True,23075},{9391,True,325007},{9405,False,247433},{9539,True,287471},{9697,True,484321},{9721,True,511633}}