Back to reduction process Irreducibles in sequence
To evaluate I, given P (>2), it is necessary to know the unique values of x and y (<x) in the expression P = (x²+y²), and then to obtain integers a and b for which (ax-by) = ±1. Then Z = (ay+bx) has the desired property that (Z²+1) is divisible by P (another valid, if less helpful, way of obtaining a value with this property is to equate Z to ((P-1)/2)! - for a proof of this, see below). If 2Z<P, set I = Z; otherwise, subtract a suitable multiple of P from Z so that I, the absolute value of the result, is as small as possible (i.e. so that 2I < P). [I] is then the irreducible associated with P.
Example 1: suppose P = 1193 = (32²+13²). (5.13 - 2.32) = 1; so Z = (5.32 + 2.13) = 186. 2Z < P, so I = Z = 186. Example 2: suppose P = 269 = (13²+10²). (7.13 - 9.10) = 1; so Z = (7.10 + 9.13) = 187. 2Z > P, so (in this case) I = |Z-P| = 82.
[1] P=2 (1²+1²) [2] P=5 (2²+1²) [5] P=13 (3²+2²) [4] P=17 (4²+1²) [12] P=29 (5²+2²) [6] P=37 (6²+1²) [9] P=41 (5²+4²) [23] P=53 (7²+2²) [11] P=61 (6²+5²) [27] P=73 (8²+3²) [34] P=89 (8²+5²) [22] P=97 (9²+4²) [10] P=101 (10²+1²) [33] P=109 (10²+3²) [15] P=113 (8²+7²) [37] P=137 (11²+4²) [44] P=149 (10²+7²) [28] P=157 (11²+6²) [80] P=173 (13²+2²) [19] P=181 (10²+9²) [81] P=193 (12²+7²) [14] P=197 (14²+1²) [107] P=229 (15²+2²) [89] P=233 (13²+8²) [64] P=241 (15²+4²) [16] P=257 (16²+1²) [82] P=269 (13²+10²) [60] P=277 (14²+9²) [53] P=281 (16²+5²) [138] P=293 (17²+2²) [25] P=313 (13²+12²) [114] P=317 (14²+11²) [148] P=337 (16²+9²) [136] P=349 (18²+5²) [42] P=353 (17²+8²) [104] P=373 (18²+7²) [115] P=389 (17²+10²) [63] P=397 (19²+6²) [20] P=401 (20²+1²) [143] P=409 (20²+3²) [29] P=421 (15²+14²) [179] P=433 (17²+12²) [67] P=449 (20²+7²) [109] P=457 (21²+4²) [48] P=461 (19²+10²) [208] P=509 (22²+5²) [235] P=521 (20²+11²) [52] P=541 (21²+10²) [118] P=557 (19²+14²) [86] P=569 (20²+13²) [24] P=577 (24²+1²) [77] P=593 (23²+8²) [125] P=601 (24²+5²) [35] P=613 (18²+17²) [194] P=617 (19²+16²) [154] P=641 (25²+4²) [149] P=653 (22²+13²) [106] P=661 (25²+6²) [58] P=673 (23²+12²) [26] P=677 (26²+1²) [135] P=701 (26²+5²) [96] P=709 (22²+15²) [353] P=733 (27²+2²) [87] P=757 (26²+9²) [39] P=761 (20²+19²) [62] P=769 (25²+12²) [317] P=773 (22²+17²) [215] P=797 (26²+11²) [318] P=809 (28²+5²) [295] P=821 (25²+14²) [246] P=829 (27²+10²) [333] P=853 (23²+18²) [207] P=857 (29²+4²) [151] P=877 (29²+6²) [387] P=881 (25²+16²) [324] P=929 (23²+20²) [196] P=937 (24²+19²) [97] P=941 (29²+10²) [442] P=953 (28²+13²) [252] P=977 (31²+4²) [161] P=997 (31²+6²) [469] P=1009 (28²+15²) [45] P=1013 (23²+22²) [374] P=1021 (30²+11²) [355] P=1033 (32²+3²) [426] P=1049 (32²+5²) [103] P=1061 (31²+10²) [249] P=1069 (30²+13²) [530] P=1093 (33²+2²) [341] P=1097 (29²+16²) [354] P=1109 (25²+22²) [214] P=1117 (26²+21²) [168] P=1129 (27²+20²) [140] P=1153 (33²+8²) [243] P=1181 (34²+5²) [186] P=1193 (32²+13²) [49] P=1201 (25²+24²) [495] P=1213 (27²+22²) [78] P=1217 (31²+16²) [597] P=1229 (35²+2²) [546] P=1237 (34²+9²) [585] P=1249 (32²+15²) [113] P=1277 (34²+11²) [479] P=1289 (35²+8²) [36] P=1297 (36²+1²) [51] P=1301 (26²+25²) [257] P=1321 (36²+5²) [614] P=1361 (31²+20²) [668] P=1373 (37²+2²) [366] P=1381 (34²+15²) [452] P=1409 (28²+25²) [620] P=1429 (30²+23²) [542] P=1433 (37²+8²) [497] P=1453 (38²+3²) [465] P=1481 (35²+16²) [225] P=1489 (33²+20²) [432] P=1493 (38²+7²) [88] P=1549 (35²+18²) [339] P=1553 (32²+23²) [610] P=1597 (34²+21²) etc.
By Wilson's theorem, P divides ((P-1)! + 1) = ((4m)! + 1). Consider the first 2m terms in (4m)!, i.e. 4m, 4m-1, 4m-2, ...., 2m+1; these can be rewritten as: P-1, P-2, P-3, ...., P-2m, respectively. Therefore their product is congruent (modulo P) to (2m)!. The remaining terms in (4m)! are 2m, 2m-1, 2m-2, ...., 2, 1, and their product is exactly (2m)!. It follows that ((4m)! + 1) is congruent (modulo P) to (((2m)!)²+1), i.e. that if Z = ((P-1)/2)! = (2m)!, (Z²+1) is divisible by P.
Top of page