summaryrefslogtreecommitdiffstats
path: root/chapitres/corps-finis.tex
blob: 9181d622cde3f8016301b4e52618748847577c10 (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
773
774
775
776
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
793
794
795
796
797
798
799
800
801
802
803
804
805
806
807
808
809
810
811
812
813
814
815
816
817
818
819
820
821
822
823
824
825
826
827
828
829
830
831
832
833
834
835
836
837
838
839
840
841
842
843
844
845
846
847
848
849
850
851
852
853
854
855
856
857
858
859
860
861
862
863
864
865
866
867
868
869
870
871
872
873
874
875
876
877
878
879
880
881
882
883
884
885
886
887
888
889
890
891
892
893
894
895
896
897
898
899
900
901
902
903
904
905
906
907
908
909
910
911
912
913
914
915
916
917
918
919
920
921
922
923
924
925
926
927
928
929
930
931
932
933
934
935
936
937
938
939
940
941
942
943
944
945
946
947
948
949
950
951
952
953
954
955
956
957
958
959
960
961
962
963
964
965
966
967
968
969
970
971
972
973
974
975
976
977
978
979
980
981
982
983
984
985
986
987
988
989
990
991
992
993
994
995
996
997
998
999
1000
1001
1002
1003
1004
1005
1006
1007
1008
1009
1010
1011
1012
1013
1014
1015
1016
1017
1018
1019
1020
1021
1022
1023
1024
1025
1026
1027
1028
1029
1030
1031
1032
1033
1034
1035
1036
1037
1038
1039
1040
1041
1042
1043
1044
1045
1046
1047
1048
1049
1050
1051
1052
1053
1054
1055
1056
1057
1058
1059
1060
1061
1062
1063
1064
1065
1066
1067
1068
1069
1070
1071
1072
1073
1074
1075
1076
1077
1078
1079
1080
1081
1082
1083
1084
1085
1086
1087
1088
1089
1090
1091
1092
1093
1094
1095
1096
1097
1098
1099
1100
1101
1102
1103
1104
1105
1106
1107
1108
1109
1110
1111
1112
1113
1114
1115
1116
1117
1118
1119
1120
1121
1122
1123
1124
1125
1126
1127
1128
1129
1130
1131
1132
1133
1134
1135
1136
1137
1138
1139
1140
1141
1142
1143
1144
1145
1146
1147
1148
1149
1150
1151
1152
1153
1154
1155
1156
1157
1158
1159
1160
1161
1162
1163
1164
1165
1166
1167
1168
1169
1170
1171
1172
1173
1174
1175
1176
1177
1178
1179
1180
1181
1182
1183
1184
1185
1186
1187
1188
1189
1190
1191
1192
1193
1194
1195
1196
1197
1198
1199
1200
1201
1202
1203
1204
1205
1206
1207
1208
1209
1210
1211
1212
1213
1214
1215
1216
1217
1218
1219
1220
1221
1222
1223
1224
1225
1226
1227
1228
1229
1230
1231
1232
1233
1234
1235
1236
1237
1238
1239
1240
1241
1242
1243
1244
1245
1246
1247
1248
1249
1250
1251
1252
1253
1254
1255
1256
1257
1258
1259
1260
1261
1262
1263
1264
1265
1266
1267
1268
1269
1270
1271
1272
1273
1274
1275
1276
1277
1278
1279
1280
1281
1282
1283
1284
1285
1286
1287
1288
1289
1290
1291
1292
1293
1294
1295
1296
1297
1298
1299
1300
1301
1302
1303
1304
1305
1306
1307
1308
1309
1310
1311
1312
1313
1314
1315
1316
1317
1318
1319
1320
1321
1322
1323
1324
1325
1326
1327
1328
1329
1330
1331
1332
1333
1334
1335
1336
1337
1338
1339
1340
1341
1342
1343
1344
1345
1346
1347
1348
1349
1350
1351
1352
1353
1354
1355
1356
1357
1358
1359
1360
1361
1362
1363
1364
1365
1366
1367
1368
1369
1370
1371
1372
1373
1374
1375
1376
1377
1378
1379
1380
1381
1382
1383
1384
1385
1386
1387
1388
1389
1390
1391
1392
1393
1394
1395
1396
1397
1398
1399
1400
1401
1402
1403
1404
1405
1406
1407
1408
1409
1410
1411
1412
1413
1414
1415
1416
1417
1418
1419
1420
1421
1422
1423
1424
1425
1426
1427
1428
1429
1430
1431
1432
1433
1434
1435
1436
1437
1438
1439
1440
1441
1442
1443
1444
1445
1446
1447
1448
1449
1450
1451
1452
1453
1454
1455
1456
1457
1458
1459
1460
1461
1462
1463
1464
1465
1466
1467
1468
1469
1470
1471
1472
1473
1474
1475
1476
1477
1478
1479
1480
1481
1482
1483
1484
1485
1486
1487
1488
1489
1490
1491
1492
1493
1494
1495
1496
1497
1498
1499
1500
1501
1502
1503
1504
1505
1506
1507
1508
1509
1510
1511
1512
1513
1514
1515
1516
1517
1518
1519
1520
1521
1522
1523
1524
1525
1526
1527
1528
1529
1530
1531
1532
1533
1534
1535
1536
1537
1538
1539
1540
1541
1542
1543
1544
1545
1546
1547
1548
1549
1550
1551
1552
1553
1554
1555
1556
1557
1558
1559
1560
1561
1562
1563
1564
1565
1566
1567
1568
1569
1570
1571
1572
1573
1574
1575
1576
1577
1578
1579
1580
1581
1582
1583
1584
1585
1586
1587
1588
1589
1590
1591
1592
1593
1594
1595
1596
1597
1598
1599
1600
1601
1602
1603
1604
1605
1606
1607
1608
1609
1610
1611
1612
1613
1614
1615
1616
1617
1618
1619
1620
1621
1622
1623
1624
1625
1626
1627
1628
1629
1630
1631
1632
1633
1634
1635
1636
1637
1638
1639
1640
1641
1642
1643
1644
1645
1646
1647
1648
1649
1650
1651
1652
1653
1654
1655
1656
1657
1658
1659
1660
1661
1662
1663
1664
1665
1666
1667
1668
1669
1670
1671
1672
1673
1674
1675
1676
1677
1678
1679
1680
1681
1682
1683
1684
1685
1686
1687
1688
1689
1690
1691
1692
1693
1694
1695
1696
1697
1698
1699
1700
1701
1702
1703
1704
1705
1706
1707
1708
1709
1710
1711
1712
1713
1714
1715
1716
1717
1718
1719
1720
1721
1722
1723
1724
1725
1726
1727
1728
1729
1730
1731
1732
1733
1734
1735
1736
1737
1738
1739
1740
1741
1742
1743
1744
1745
1746
1747
1748
1749
1750
1751
1752
1753
1754
1755
1756
1757
1758
1759
1760
1761
1762
1763
1764
1765
1766
1767
1768
1769
1770
1771
1772
1773
1774
1775
1776
1777
1778
1779
1780
1781
1782
1783
1784
1785
1786
1787
1788
1789
1790
1791
1792
1793
1794
1795
1796
1797
1798
1799
1800
1801
1802
1803
1804
1805
1806
1807
1808
1809
1810
1811
1812
1813
1814
1815
1816
1817
1818
1819
1820
1821
1822
1823
1824
1825
1826
1827
1828
1829
1830
1831
1832
1833
1834
1835
1836
1837
1838
1839
1840
1841
1842
1843
1844
1845
1846
1847
1848
1849
1850
1851
1852
1853
1854
1855
1856
1857
1858
1859
1860
1861
1862
1863
1864
1865
1866
1867
1868
1869
1870
1871
1872
1873
1874
1875
1876
1877
1878
1879
1880
1881
1882
1883
1884
1885
1886
1887
1888
1889
1890
1891
1892
1893
1894
1895
1896
1897
1898
1899
1900
1901
1902
1903
1904
1905
1906
1907
1908
1909
1910
1911
1912
1913
1914
1915
1916
1917
1918
1919
1920
1921
1922
1923
1924
1925
1926
1927
1928
1929
1930
1931
1932
1933
1934
1935
1936
1937
1938
1939
1940
1941
1942
1943
1944
1945
1946
1947
1948
1949
1950
1951
1952
1953
1954
1955
1956
1957
1958
1959
1960
1961
1962
1963
1964
1965
1966
1967
1968
1969
1970
1971
1972
1973
1974
1975
1976
1977
1978
1979
1980
1981
1982
1983
1984
1985
1986
1987
1988
1989
1990
1991
1992
1993
1994
1995
1996
1997
1998
1999
2000
2001
2002
2003
2004
2005
2006
2007
2008
2009
2010
2011
2012
2013
2014
2015
2016
2017
2018
2019
2020
2021
2022
2023
2024
2025
2026
2027
2028
2029
2030
2031
2032
2033
2034
2035
2036
2037
2038
2039
2040
2041
2042
2043
2044
2045
2046
2047
2048
2049
2050
2051
2052
2053
2054
2055
2056
2057
2058
2059
2060
2061
2062
2063
2064
2065
2066
2067
2068
2069
2070
2071
2072
2073
2074
2075
2076
2077
2078
2079
2080
2081
2082
2083
2084
2085
2086
2087
2088
2089
2090
2091
2092
2093
2094
2095
2096
2097
2098
2099
2100
2101
2102
2103
2104
2105
2106
2107
2108
2109
2110
2111
2112
2113
2114
2115
2116
2117
2118
2119
2120
2121
2122
2123
2124
2125
2126
2127
2128
2129
2130
2131
2132
2133
2134
2135
2136
2137
2138
2139
2140
2141
2142
2143
2144
2145
2146
2147
2148
2149
2150
2151
2152
2153
2154
2155
2156
2157
2158
2159
2160
2161
2162
2163
2164
2165
2166
2167
2168
2169
2170
2171
2172
2173
2174
2175
2176
2177
2178
2179
2180
2181
2182
2183
2184
2185
2186
2187
2188
2189
2190
2191
2192
2193
2194
2195
2196
2197
2198
2199
2200
2201
2202
2203
2204
2205
2206
2207
2208
2209
2210
2211
2212
2213
2214
2215
2216
2217
2218
2219
2220
2221
2222
2223
2224
2225
2226
2227
2228
2229
2230
2231
2232
2233
2234
2235
2236
2237
2238
2239
2240
2241
2242
2243
2244
2245
2246
2247
2248
2249
2250
2251
2252
2253
2254
2255
2256
2257
2258
2259
2260
2261
2262
2263
2264
2265
2266
2267
2268
2269
2270
2271
2272
2273
2274
2275
2276
2277
2278
2279
2280
2281
2282
2283
2284
2285
2286
2287
2288
2289
2290
2291
2292
2293
2294
2295
2296
2297
2298
2299
2300
2301
2302
2303
2304
2305
2306
2307
2308
2309
2310
2311
2312
2313
2314
2315
2316
2317
2318
2319
2320
2321
2322
2323
2324
2325
2326
2327
2328
2329
2330
2331
2332
2333
2334
2335
2336
2337
2338
2339
2340
2341
2342
2343
2344
2345
2346
2347
2348
2349
2350
2351
2352
2353
2354
2355
2356
2357
2358
2359
2360
2361
2362
2363
2364
2365
2366
2367
2368
2369
2370
2371
2372
2373
2374
2375
2376
2377
2378
2379
2380
2381
2382
2383
2384
2385
2386
2387
2388
2389
2390
2391
2392
2393
2394
2395
2396
2397
2398
2399
2400
2401
2402
2403
2404
2405
2406
2407
2408
2409
2410
2411
2412
2413
2414
2415
2416
2417
2418
2419
2420
2421
2422
2423
2424
2425
2426
2427
2428
2429
2430
2431
2432
2433
2434
2435
2436
2437
2438
2439
2440
2441
2442
2443
2444
2445
2446
2447
2448
2449
2450
2451
2452
2453
2454
2455
2456
2457
2458
2459
2460
2461
2462
2463
2464
2465
2466
2467
2468
2469
2470
2471
2472
2473
2474
2475
2476
2477
2478
2479
2480
2481
2482
2483
2484
2485
2486
2487
2488
2489
2490
2491
2492
2493
2494
2495
2496
2497
2498
2499
2500
2501
2502
2503
2504
2505
2506
2507
2508
2509
2510
2511
2512
2513
2514
2515
2516
2517
2518
2519
2520
2521
2522
2523
2524
2525
2526
2527
2528
2529
2530
2531
2532
2533
2534
2535
2536
2537
2538
2539
2540
2541
2542
2543
2544
2545
2546
2547
2548
2549
2550
2551
2552
2553
2554
2555
2556
2557
2558
2559
2560
2561
2562
2563
2564
2565
2566
2567
2568
2569
2570
2571
2572
2573
2574
2575
2576
2577
2578
2579
2580
2581
2582
2583
2584
2585
2586
2587
2588
2589
2590
2591
2592
2593
2594
2595
2596
2597
2598
2599
2600
2601
2602
2603
2604
2605
2606
2607
2608
2609
2610
2611
2612
2613
2614
2615
2616
2617
2618
2619
2620
2621
2622
2623
2624
2625
2626
2627
2628
2629
2630
2631
2632
2633
2634
2635
2636
2637
2638
2639
2640
2641
2642
2643
2644
2645
2646
2647
2648
2649
2650
2651
2652
2653
2654
2655
2656
2657
2658
2659
2660
2661
2662
2663
2664
2665
2666
2667
2668
2669
2670
2671
2672
2673
2674
2675
2676
2677
2678
2679
2680
2681
2682
2683
2684
2685
2686
2687
2688
2689
2690
2691
2692
2693
2694
2695
2696
2697
2698
2699
2700
2701
2702
2703
2704
2705
2706
2707
2708
2709
2710
2711
2712
2713
2714
2715
2716
2717
2718
2719
2720
2721
2722
2723
2724
2725
2726
2727
2728
2729
2730
2731
2732
2733
2734
2735
2736
2737
2738
2739
2740
2741
2742
2743
2744
2745
2746
2747
2748
2749
2750
2751
2752
2753
2754
2755
2756
2757
2758
2759
2760
2761
2762
2763
2764
2765
2766
2767
2768
2769
2770
2771
2772
2773
2774
2775
2776
2777
2778
2779
2780
2781
2782
2783
2784
2785
2786
2787
2788
2789
2790
2791
2792
2793
2794
2795
2796
2797
2798
2799
2800
2801
2802
2803
2804
2805
2806
2807
2808
2809
2810
2811
2812
2813
2814
2815
2816
2817
2818
2819
2820
2821
2822
2823
2824
2825
2826
2827
2828
2829
2830
2831
2832
2833
2834
2835
2836
2837
2838
2839
2840
2841
2842
2843
2844
2845
2846
2847
2848
2849
2850
2851
2852
2853
2854
2855
2856
2857
2858
2859
2860
2861
2862
2863
2864
2865
2866
2867
2868
2869
2870
2871
2872
2873
2874
2875
2876
2877
2878
2879
2880
2881
2882
2883
2884
2885
2886
2887
2888
2889
2890
2891
2892
2893
2894
2895
2896
2897
2898
2899
2900
2901
2902
2903
2904
2905
2906
2907
2908
2909
2910
2911
2912
2913
2914
2915
2916
2917
2918
2919
2920
2921
2922
2923
2924
2925
2926
2927
2928
2929
2930
2931
2932
2933
2934
2935
2936
2937
2938
2939
2940
2941
2942
2943
2944
2945
2946
2947
2948
2949
2950
2951
2952
2953
2954
2955
2956
2957
2958
2959
2960
2961
2962
2963
2964
2965
2966
2967
2968
2969
2970
2971
2972
2973
2974
2975
2976
2977
2978
2979
2980
2981
2982
2983
2984
2985
2986
2987
2988
2989
2990
2991
2992
2993
2994
2995
2996
2997
2998
2999
3000
3001
3002
3003
3004
3005
3006
3007
3008
3009
3010
3011
3012
3013
3014
3015
3016
3017
3018
3019
3020
3021
3022
3023
3024
3025
3026
3027
3028
3029
3030
3031
3032
3033
3034
3035
3036
3037
3038
3039
3040
3041
3042
3043
3044
3045
3046
3047
3048
3049
3050
3051
3052
3053
3054
3055
3056
3057
3058
3059
3060
3061
3062
3063
3064
3065
3066
3067
3068
3069
3070
3071
3072
3073
3074
3075
3076
3077
3078
3079
3080
3081
3082
3083
3084
3085
3086
3087
3088
3089
3090
3091
3092
3093
3094
3095
3096
3097
3098
3099
3100
3101
3102
3103
3104
3105
3106
3107
3108
3109
3110
3111
3112
3113
3114
3115
3116
3117
3118
3119
3120
3121
3122
3123
3124
3125
3126
3127
3128
3129
3130
3131
3132
3133
3134
3135
3136
3137
3138
3139
3140
3141
3142
3143
3144
3145
3146
3147
3148
3149
3150
3151
3152
3153
3154
3155
3156
3157
3158
3159
3160
3161
3162
3163
3164
3165
3166
3167
3168
3169
3170
3171
3172
3173
3174
3175
3176
3177
3178
3179
3180
3181
3182
3183
3184
3185
3186
3187
3188
3189
3190
3191
3192
3193
3194
3195
3196
3197
3198
3199
3200
3201
3202
3203
3204
3205
3206
3207
3208
3209
3210
3211
3212
3213
3214
3215
3216
3217
3218
3219
3220
3221
3222
3223
3224
3225
3226
3227
3228
3229
3230
3231
3232
3233
3234
3235
3236
3237
3238
3239
3240
%%% Emacs: -*- mode:latex; coding:utf-8; -*-
\ifx\danslelivre\undefined
\documentclass[a4paper,9pt]{amsart}
\input{../config/preambule}
\input{../config/macros}
\title{Corps finis}
\externaldocument{extensions-algebriques}
\externaldocument{algo-corps-finis}
\externaldocument{correspondance-galois}
\begin{document}
\maketitle
\tableofcontents
\else
\chapter{Corps finis}
\begingroup
\fi

\section{Propriétés élémentaires}

\subsection{Caractéristique}

Soit $k$ un corps.  Le noyau de l'unique morphisme d'anneaux $𝐙→k$ est
un idéal premier de $𝐙$.  On rappelle que la \emph{caractéristique} de
$k$ désigne le générateur positif ou nul de cet idéal : on le note
$\car k$.  C'est un nombre premier (souvent noté $p$) ou bien $0$.
Lorsque $\car k$ est un nombre premier $p>0$, l'image de $\ZZ\to k$
est isomorphe à $\ZZ/p\ZZ$.

Pour tout nombre premier $p$, on note $𝐅_p$ le quotient $𝐙/p𝐙$.  C'est
un corps (car c'est un anneau intègre fini) de caractéristique $p$ à
$p$ éléments.  Pour tout corps $k$ de caractéristique $p$, l'image de
$\ZZ \to k$ est un sous-corps de $k$ isomorphe à $\FF_p$, qui est le
plus petit sous-corps de $k$ (car les sous-corps de $k$ sont eux aussi
de caractéristique $p$) et que l'on appelle \emph{corps premier}
de $k$.

On appelle par ailleurs \emph{exposant caractéristique} \index{exposant
caractéristique} de $k$ l'entier valant $1$ si $\car k= 0$ et valant $\car k$ sinon.

\begin{lemme2}\label{structures-sur-corps-premier}
Soit $p$ un nombre premier.

Un groupe abélien $M$ peut être munie d'une structure d'espace
vectoriel sur le corps $\FF_p$ exactement lorsque tout élément $x\in
M$ vérifie $px = 0$, auquel cas cette structure de $\FF_p$-espace
vectoriel est unique.

Un anneau $A$ non nécessairement commutatif peut-être muni d'une
structure de $𝐅_p$-algèbre non nécessairement commutative si et
seulement si l'image de $p$ dans $A$ par le morphisme canonique (et
unique) $𝐙→A$ est nulle.  Cette structure est alors unique.
\end{lemme2}
\begin{proof}
Pour ce qui est de la première affirmation, tout $\FF_p$-espace
vectoriel doit manifestement vérifier $px = 0$ pour tout $x$, et si un
groupe abélien $M$ vérifie cette condition, on peut alors poser $\bar
k\cdot x = k x$, pour tous $k \in \ZZ$, dont on note $\bar k \in
\FF_p$ la classe modulo $p$, et tout $x \in M$, ce qui définit une
structure de $\FF_p$ espace vectoriel sur $M$, qui était la seule
possible car $\bar k = k\cdot \bar 1$ dans $\FF_p$.

En particulier, toute $\FF_p$-algèbre non nécessairement
commutative $A$ doit vérifier $p 1_A = 0$, c'est-à-dire que l'image de
$p$ par le morphisme $\ZZ \to A$ est nulle ; et si cette condition est
satisfaite dans un anneau non nécessairement commutatif $A$ alors $p x
= p 1_A x = 0$ pour tout $x \in A$ donc on vient de voir qu'il y a une
unique façon de mettre sur $A$ une structure de $\FF_p$-espace
vectoriel, qui est clairement une structure de $\FF_p$-algèbre non
nécessairement commutative.
\end{proof}

\begin{lemme2}\label{anneaux-a-p-elements}
Soit $A$ un anneau non nécessairement commutatif ayant $p$ éléments,
où $p$ est un nombre premier.  Alors il existe un unique isomorphisme
entre $\FF_p$ et $A$.
\end{lemme2}
\begin{proof}
L'image du morphisme d'anneaux $\ZZ \to A$ est un sous-anneau de $A$
dont le cardinal doit diviser $p$ ; comme $0_A \neq 1_A$ (sans quoi
$A$ serait l'anneau nul, qui a un seul élément, ce qui n'est pas le
cas), ce cardinal est $p$, c'est-à-dire que $\ZZ \to A$ est surjectif.
Il définit donc un isomorphisme $\ZZ/n\ZZ \simto A$
avec $n$ le générateur positif de son noyau, et en comparant les
cardinaux on voit que $n=p$, de sorte qu'on a un isomorphisme $\FF_p
\simto A$, qui était visiblement le seul possible.
\end{proof}

On peut donc parler \emph{du} corps fini ayant $p$ éléments, et il n'y
a pas de problème à identifier $\FF_p$ au corps premier de n'importe
quel corps de caractéristique $p$.

\begin{proposition2}
Soit $F$ un corps fini.  Alors, la caractéristique de $F$ est un
nombre premier $p>0$ et le cardinal de $F$ est une puissance de $p$.
\end{proposition2}
\begin{démo}[Démonstration de la proposition]
Le morphisme $𝐙→F$ n'est pas injectif car $F$ est fini donc
$\car(F)≠0$.  D'autre part, si $p=\car(F)$, le
lemme \ref{structures-sur-corps-premier} assure que $F$ un
$\FF_p$-espace vectoriel (de façon unique).  Si $r=\dim_{\FF_p}(F)$
(nécessairement finie), on a $\# F=p^r$.
\end{démo}

Il est fréquent, lorsqu'on a affaire à un corps fini, de noter $p$ sa
caractéristique et $q$ son nombre d'éléments (qui en est donc une
puissance), à tel point que ces notations sont parfois utilisées, si
cela ne cause pas de confusion, sans avoir été introduites.  En
particulier, une expression telle que « soit $F$ un corps fini de
  cardinal $p^r$ » sous-entendra toujours que $p$ est un nombre
premier et $r>0$ un entier naturel non nul.

\begin{remarque2}
On peut montrer que tout corps gauche fini est commutatif (théorème de
Wedderburn ; nous en donnerons une démonstration en \ref{Wedderburn}),
ou même que toute algèbre à division alternative mais non
nécessairement associative est un corps fini.
\end{remarque2}

\begin{exercice2}
Montrer que le nombre de polynômes irréductibles unitaires
de $𝐅_p[X]$ de degré $≤3$ est $\frac{1}{3}p³+\frac{1}{2}p²+\frac{1}{6}p$.
% sans utiliser la formule de Gauß. C'est un simple comptage
% trivial.
\end{exercice2}

\begin{exercice2}
 Soient $K$ un corps fini de cardinal $q$ et $P
∈ K[T]$ un polynôme de degré $d$, supposé tel que $P(0)=0$
pour simplifier.
\begin{enumerate}
\item Soit $Q(X)=∏_{λ ∈ K} (X-P(λ))$. Montrer que
les coefficients de $Q$ de degré $q-i$ tel que $di<q-1$ sont
nuls. (Indication : on pourra considérer $∏_{λ ∈ K} (X-P(t
λ))=∑_i c_i(t)X^{q-i}$, où $c_i ∈ 𝐅[t]$ est de degré $≤
di$.)
% la _fonction_ c_i est constante sur $𝐅^×$ ; si son degré
% est $<q-1$, le polynôme c_i est constant, égal à c_i(0).
\item Montrer que $P(K) ⊆ K$ est l'ensemble des zéros du
polynôme $Q-(X^q-X)$ et en déduire le théorème suivant de
Wan : soit $P(K)=K$ soit $P(K)$ est de cardinal au plus $q-\frac{q-1}{d}$.
\end{enumerate}
\end{exercice2}


\subsection{Le morphisme de Frobenius}

\begin{proposition2}[petit théorème de Fermat]\label{petit-theoreme-fermat}
Soit $F$ un corps fini ayant $q$ éléments.  Alors tout élément $x$
de $F$ vérifie $x^q = x$.  Plus précisément, les racines du polynôme
$X^q-X$ dans $F$ sont tous les éléments de $F$, chacun avec
multiplicité $1$ : on a
\[
X^q - X = \prod_{a \in F} (X-a)
\]
\end{proposition2}
\begin{proof}
Le groupe multiplicatif $F^×$ des inversibles de $F$ est
d'ordre $q-1$, donc si $x \neq 0$ on a $x^{q-1} = 1$ donc $x^q = x$ ;
le cas $x=0$ est trivial.  Pour ce qui est de la seconde affirmation,
on vient de montrer que $\prod_{a \in F} (X-a)$ divise $X^q-X$, et
comme ces deux polynômes sont unitaires et de même degré, ils sont
égaux.
\end{proof}

\begin{corollaire2}\label{unicite-corps-q-elements-pour-inclusion}
Si $K$ est un corps de caractéristique $p>0$, alors pour toute
puissance $q = p^r$ de $p$, il existe au plus un sous-corps de $K$
ayant $q$ éléments.
\end{corollaire2}
\begin{proof}
Si $F$ est un sous-corps de $K$ à $q$ éléments, alors la
proposition \ref{petit-theoreme-fermat} montre que $F$ est exactement
l'ensemble des racines de $X^q-X$ (dans $F$ donc dans $K$), ce qui
prouve l'unicité.
\end{proof}

Autrement dit, un corps à $q$ éléments est unique comme sous-corps de
n'importe quel sur-corps.  On va voir
en \ref{existence-et-unicite-corps finis} qu'il est également unique à
isomorphisme près (mais pas à isomorphisme unique près).

\begin{proposition2}\label{morphisme-de-frobenius}
Soient $p$ un nombre premier et $A$ une $𝐅_p$-algèbre.  L'application
$\Frob|_A\colon A→A$ donnée par $a↦a^p$ est un \emph{endomorphisme} de $A$.
\end{proposition2}
\begin{démo}
Seule l'identité $\Frob|_A(x+y)=\Frob|_A(x)+\Frob|_A(y)$ n'est pas
évidente.  Elle résulte de la formule du binôme de Newton et de la
congruence $\frac{p!}{i!(p-i)!}≡0\pmod{p}$ pour tout $0<i<p$.
\end{démo}

Ce morphisme est le \emph{Frobenius}\index{Frobenius} de $A$ (ou
\emph{Frobenius absolu}), souvent noté $\Frob|_A$ (ou parfois
$\Frob_A$) ou simplement $\Frob$.  Lorsque cela ne semble pas prêter à
confusion, on notera $A^p⊆A$ son image.

Lorsque $k$ est un corps, $\Frob|_k$ est injectif puisque son noyau
est nul ; par conséquent, lorsque $F$ est un corps fini, $\Frob|_F$
est bijectif, et on en déduit que les corps finis sont parfaits
(\refext{Alg}{corps-parfait}).  En fait, puisque $\Frob^r(x) =
x^{p^r}$, lorsque $F$ est un corps fini ayant $q = p^r$ éléments, la
proposition \ref{petit-theoreme-fermat} se traduit par $(\Frob|_F)^r =
\Id_F$ (on verra plus loin que l'ordre de $\Frob|_F$ est
exactement $r$).

\begin{lemme2}\label{sous-corps-a-q-elements}
Soient $p$ un nombre premier et $q=p^r$ une puissance de $p$.  Soit
$K$ un corps de caractéristique $p$ sur lequel le polynôme $X^q-X$ est
scindé.  Alors l'ensemble $\Fix(\Frob^r_K)$ des racines du polynôme
$X^q-X$ dans $K$ est un sous-corps de $K$ à $q$ éléments (dont on a vu
l'unicité en \ref{unicite-corps-q-elements-pour-inclusion}).
\end{lemme2}
\begin{proof}
L'ensemble des racines de $X^q-X$ est un sous-corps de $K$ puisque
c'est l'ensemble $\Fix(\Frob^r_K)$ des points fixes du morphisme de
corps $\Frob^r_K$.  Comme la dérivée du polynôme $X^q-X$ est $-1$, les
racines de ce polynôme sont toutes simples et il y en a, dans $K$ où
il est supposé scindé, exactement $q$ : ainsi, $\Fix(\Frob^r_K)$ est
bien un sous-corps de $K$ à $q$ éléments.
\end{proof}

\begin{proposition2}\label{existence-et-unicite-corps finis}
Soit $q=p^r$ une puissance d'un nombre premier.  Il existe un corps à
$q$ éléments, unique à isomorphisme près.  Un tel corps est un corps
de décomposition (\refext{Alg}{définition corps de décomposition}) du
polynôme $X^q-X∈𝐅_p[X]$.
\end{proposition2}
\begin{proof}
L'existence se déduit du lemme \ref{sous-corps-a-q-elements} appliqué
à une clôture algébrique $K$ de $\FF_p$ ou simplement à un corps de
décomposition sur $\FF_p$ de $X^q-X$.  L'unicité se déduit de même :
tout corps fini $F$ à $q$ éléments se plonge dans la clôture
algébrique de $\FF_p$ (car $F$ est algébrique sur $\FF_p$) ou
simplement dans un corps de décomposition sur $\FF_p$ de $X^q-X$ (car
$F$ est engendré par les racines de ce polynôme) et la
proposition \ref{unicite-corps-q-elements-pour-inclusion} montre alors
l'unicité de $F$ dans ce sur-corps qui ne dépendait pas de $F$.  La
dernière affirmation est claire compte tenu
de \ref{unicite-corps-q-elements-pour-inclusion}.
\end{proof}

(On verra en \refext{ACF}{remarque-isomorphisme-explicite-corps-finis} une
façon d'obtenir un isomorphisme explicite entre des présentations
différentes d'un même corps fini.)

Dès lors que $q$ est une puissance stricte d'un nombre premier,
l'isomorphisme n'est plus unique puisque $\Frob\colon x \mapsto x^p$
constitue sur un corps fini à $q$ éléments un automorphisme différent
de l'identité.

On se permettra pourtant de noter, lorsque $q = p^r$ est une puissance
d'un nombre premier, par $\FF_q$ le corps fini à $q$ éléments,
celui-ci étant défini à isomorphisme non unique près ; ou encore, si
un corps contient un sous-corps ayant $q$ éléments (nécessairement
unique en tant que sous-corps, comme on l'a expliqué), on notera
$\FF_q$ ce sous-corps.

Si $q = p^r$, on notera par ailleurs $\Frob_q = (\Frob)^r \colon x
\mapsto x^q$ l'élévation à la puissance $q$ dans n'importe quel corps
de caractéristique $p$ : si le corps en question contient $\FF_q$,
alors $\FF_q$ est exactement l'ensemble des points fixes de $\Frob_q$,
et le morphisme $\Frob_q$, non content d'être $\FF_p$-linéaire, est en
fait $\FF_q$-linéaire.  Plus généralement, on définit $\Frob_q =
(\Frob)^r \colon x \mapsto x^q$ dans n'importe quelle $\FF_q$-algèbre.

\subsubsection{} Les trois lemmes suivants, qui doivent être considérés
comme un tout, ont pour vocation à clarifier le comportement des
polynômes $X^q - X$ lorsque $q$ est remplacé par une certaine
puissance de lui-même.

\begin{lemme2}\label{lemme-divisibilite-x-q-r-x}
Soient $m$ et $n$ deux entiers naturels non nuls tels que $m|n$.
Alors :
\begin{itemize}
\item pour tout entier $q>1$, l'entier $q^m-1$ divise $q^n-1$,
\item le polynôme $X^m-1$ divise $X^n-1$ (dans $\ZZ[X]$ ou, par
conséquent, $A[X]$ pour n'importe quel anneau $A$),
\item pour tout entier $q>1$, le polynôme $X^{q^m}-X$ divise
$X^{q^n}-X$ (de même).
\end{itemize}
\end{lemme2}
\begin{proof}
Le premier point découle de ce que $q^n-1 = (q^m-1)(q^{n-m} + q^{n-2m}
+ \cdots + q^{2m} + q^m + 1)$, comme on le voit en dévelopant.  Le
second découle de même de ce que $X^n-1 = (X^m-1)(X^{n-m} + X^{n-2m}
+ \cdots + X^{2m} + X^m + 1)$.  Le troisième point découle des deux
premiers : puisque $q^m-1$ divise $q^n-1$, le polynôme $X^{q^m-1} - 1$
divise $X^{q^n-1} - 1$, et par conséquent $X^{q^m} - X$ divise
$X^{q^n} - X$.
\end{proof}

\begin{lemme2}\label{lemme-non-divisibilite-x-q-r-x}
Soient $m$ et $n$ deux entiers naturels non nuls et $r$ le reste de la
division euclidienne de $m$ par $n$ ; on suppose $r>0$.  Alors :
\begin{itemize}
\item pour tout entier $q>1$, le reste de la division euclidienne de
$q^m-1$ par $q^n-1$ est $q^r-1$,
\item il existe $g$ dans $\ZZ[X]$ tel que $X^m-1 = (X^n-1) g + (X^r-1)$,
\item pour tout entier $q>1$, il existe $g$ dans $\ZZ[X]$ tel que
$X^{q^m}-X = (X^{q^n}-X) g + (X^{q^r}-X)$.
\end{itemize}
\end{lemme2}
\begin{proof}
Écrivons $m = kn+r$ : le lemme \ref{lemme-divisibilite-x-q-r-x} montre
que $q^{kn} \equiv 1 \pmod{q^n-1}$, et par conséquent $q^m - 1 \equiv
q^r -1 \pmod{q^n-1}$ ; puisque $0 < q^r - 1 < q^n - 1$, on a le
premier point annoncé.  Le second est rigoureusement analogue.  Le
troisième découle des deux premiers : puisque $q^r - 1$ est le reste
de la division euclidienne de $q^m - 1$ par $q^n - 1$, on peut écrire
$X^{q^m-1} - 1 = (X^{q^n-1}-1) g + (X^{q^r-1}-1)$, donc $X^{q^m} - X
= (X^{q^n}-X) g + (X^{q^r}-X)$.
\end{proof}

\begin{lemme2}\label{lemme-pgcd-x-q-r-x}
Soient $m$ et $n$ deux entiers naturels non nuls et $d$ leur pgcd.
Alors :
\begin{itemize}
\item pour tout entier $q>1$, les entiers $q^m-1$ et $q^n-1$ ont pour
pgcd $q^d-1$ (concrètement, il existe $u,v$ entiers tels que $(q^m-1)u
+ (q^n-1)v = q^d-1$),
\item les polynômes $X^m-1$ et $X^n-1$ de $\ZZ[X]$ engendrent l'idéal
$(X^d-1)$ de $\ZZ[X]$ (concrètement, il existe $u,v$ de $\ZZ[X]$ tels
que $(X^m-1)u + (X^n-1)v = X^d-1$),
\item pour tout entier $q>1$, les polynômes $X^{q^m}-X$ et $X^{q^n}-X$
de $\ZZ[X]$ engendrent l'idéal $(X^{q^d}-X)$ de $\ZZ[X]$
(concrètement, il existe $u,v$ de $\ZZ[X]$ tels que $(X^{q^m}-X) u +
(X^{q^n}-X) v = X^{q^d}-X$.
\end{itemize}
\end{lemme2}
\begin{proof}
Avant toute chose, \ref{lemme-divisibilite-x-q-r-x} assure bien que
$q^d-1$ divise $q^m-1$ et $q^n-1$, que $X^d-1$ divise bien $X^m-1$ et
$X^n-1$, et que $X^{q^d}-X$ divise bien $X^{q^m}-X$ et $X^{q^n}-X$.
(Ceci justifie notamment que dire « il existe $u,v$ de $\ZZ[X]$ tels
que $(X^m-1)u + (X^n-1)v = X^d-1$ » traduise bien le fait que $X^m-1$
et $X^n-1$ engendrent l'idéal $(X^d-1)$, et pas un idéal plus gros, et
de même pour les autres points.)

Montrons le premier point par récurrence sur $n$.  Si $n=d$, tout est
clair.  Sinon, soit $r$ le reste de la division euclidienne de $m$
par $n$, qui vérifie bien sûr $r>0$.  Alors le reste de la division
euclidienne de $q^m-1$ par $q^n-1$ vaut $q^r-1$
d'après \ref{lemme-non-divisibilite-x-q-r-x}.  Par conséquent,
$\pgcd(q^m-1,q^n-1) = \pgcd(q^n-1,q^r-1)$.  Comme $n$ et $r$ sont
premiers entre eux, l'hypothèse de récurrence permet de conclure que
ceci vaut $q^d-1$, ce qu'on voulait prouver.

Montrons le second point par récurrence sur $n$.  Si $n=d$, tout est
clair.  Sinon, soit $r$ le reste de la division euclidienne de $m$
par $n$, qui vérifie bien sûr $r>0$.  Alors on peut écrire $X^m-1 =
(X^n-1) g + (X^r-1)$ d'après \ref{lemme-non-divisibilite-x-q-r-x}.
Comme $n$ et $r$ sont premiers entre eux, l'hypothèse de récurrence
permet de trouver une écriture $X^d-1 = (X^n-1)u + (X^r-1)v$ ; en
remplaçant $X^r-1$ par $X^m-1 - (X^n-1) g$, on trouve bien une
écriture $X^d-1 = (X^m-1)u' + (X^n-1)v'$ comme souhaitée.

Le troisième point se démontre encore par récurrence sur $n$.
Si $n=d$, tout est clair.  Sinon, soit $r$ le reste de la division
euclidienne de $m$ par $n$, qui vérifie bien sûr $r>0$.  Alors on peut
écrire $X^{q^m}-X = (X^{q^n}-X) g + (X^{q^r}-X)$
d'après \ref{lemme-non-divisibilite-x-q-r-x}.  Comme $n$ et $r$ sont
premiers entre eux, l'hypothèse de récurrence permet de trouver une
écriture $X^{q^d}-X = (X^{q^n}-X)u + (X^{q^r}-X)v$ ; en remplaçant
$X^{q^r}-X$ par $X^{q^m}-X - (X^{q^n}-X) g$, on trouve bien une
écriture $X^{q^d}-X = (X^{q^m}-X)u' + (X^{q^n}-X)v'$ comme souhaitée.
\end{proof}

\begin{proposition2}\label{inclusions-corps-finis}
Si $q = p^r$ et $q' = p^{\prime r'}$, on a $\FF_q \subseteq \FF_{q'}$
(au sens où $\FF_{q'}$ contient un sous-corps à $q$ éléments, qui est
alors unique et isomorphe à $\FF_q$) si et seulement si $p = p'$ et
$r|r'$.  Le degré de l'extension $\FF_{q'} \bo \FF_q$ est alors $r'/r$.

Si $q = p^r$ et $q' = p^{r'}$ avec $\pgcd(r,r') = r_0$, alors $\FF_q
\cap \FF_{q'} = \FF_{q_0}$ où $q_0 = p^{r_0}$ dans n'importe quel
corps contenant des sous-corps ayant $q$ et $q'$ éléments.
\end{proposition2}
\begin{proof}
Si $\FF_q \subseteq \FF_{q'}$ où $q = p^r$ et $q' = p^{\prime r'}$, on
doit nécessairement avoir $p = p'$ car ce sont les caractéristiques de
ces deux corps.  Par ailleurs, $\FF_{q'}$ est un espace vectoriel de
dimension finie sur $\FF_q$, donc en notant $s$ sa dimension, on a $q'
= q^s$, c'est-à-dire $r' = rs$ et $r|r'$ comme annoncé.

Réciproquement, si $p = p'$ et $r|r'$, alors $q' = q^s$ où $s = r'/r$
est entier, donc le lemme \ref{lemme-divisibilite-x-q-r-x} montre que
$X^{q'} - X$ est multiple de $X^q - X$ (dans $\ZZ[X]$ et en
particulier dans $\FF_{q'}[X]$), et comme $X^{q'}-X$ est scindé sur
$\FF_{q'}$, le polynôme $X^q-X$ l'est aussi, ce qui montre que
$\FF_q \subseteq
\FF_{q'}$ d'après \ref{sous-corps-a-q-elements}.

La seconde affirmation est alors claire : $\FF_q \cap \FF_{q'}$ est un
corps fini qui contient le corps fini à $p^{r_1}$ éléments si et
seulement si $r_1 | r$ et $r_1 | r'$, c'est-à-dire si et seulement si
$r_1 | r_0$ où $r_0 = \pgcd(r,r')$ — autrement dit, il s'agit
justement de $\FF_{q_0}$.
\end{proof}

\section{Polynômes irréductibles}

\subsection{Polynômes minimaux et éléments conjugués}

Lorsque $x \in \FF_{q^r}$, on rappelle que le \emph{polynôme minimal}
(\refext{Alg}{polynome-minimal}) de $x$ sur $\FF_q$ (lequel est un
sous-corps de $\FF_{q^r}$ d'après \ref{inclusions-corps-finis}) est le
polynôme unitaire $h \in \FF_q[X]$ engendrant l'idéal dans $\FF_q[X]$
des polynômes $f$ tels que $f(x) = 0$, et que c'est l'unique polynôme
unitaire irréductible dans $\FF_q[X]$ s'annulant en $x$ ; son degré
est le degré $s = [\FF_q(x) : \FF_q]$ de $x$ sur $\FF_q$, qui divise
le degré $r = [\FF_{q^r} : \FF_q]$ de l'extension.  De plus, dans ces
conditions, on a $\FF_q(x) \cong \FF_q[X]/(h) \cong \FF_{q^s}$ : en
particulier, d'après \ref{petit-theoreme-fermat}, l'élément $x$
vérifie $x^{q^s} = x$, et $h(X) | (X^{q^s}-X)$.  Réciproquement, on
rappelle que si $h \in \FF_q[X]$ est un polynôme irréductible
quelconque alors $\FF_q[X]/(h)$ est un corps, et la classe $x$ de $X$
modulo $h$ (c'est-à-dire dans $\FF_q[X]/(h) = \FF_q(x)$) a $h$ pour
polynôme minimal.

\begin{proposition2}\label{racines-polynome-minimal-corps-fini}
Lorsque $x \in \FF_{q^r}$ a pour polynôme minimal $h$ sur $\FF_q$ et
degré $s$ (divisant $r$), alors le polynôme $h$ est scindé sur
$\FF_{q^r}$ et ses racines sont $x, x^q, x^{q^2}, \ldots,
x^{q^{s-1}}$ :
\[
h(X) = \prod_{i=0}^{s-1} (X-\Frob_q^i(x))
\]
\end{proposition2}
\begin{proof}
Puisque $h \in \FF_q[X]$ et que $\Frob_q$ est un automorphisme de
$\FF_{q^r}$ fixant $\FF_q$, on a $h(\Frob_q^i(x)) =
\Frob_q^i(h(x)) = 0$ pour tout $i$, c'est-à-dire que les $x^{q^i}$
sont racines de $h$.  Montrons maintenant que $x, x^q, \ldots,
x^{q^{s-1}}$ sont deux à deux distincts, c'est-à-dire que l'ordre de
$\Frob_q$ agissant sur $x$ (qui doit diviser $s$, comme on l'a
expliqué) est exactement $s$ : or si on a $x^{q^t} = x$ pour $t \leq
s$, on a $x \in \FF_{q^t}$ donc le degré $s$ de $x$ sur $\FF_q$
diviserait $t$, ce qui n'est possible que pour $t=s$.  Finalement, on
a trouvé $s$ racines distinctes dans $\FF_{q^r}$ pour un
polynôme ($h$) de degré $s$, c'est-à-dire que ce polynôme est scindé
avec la décomposition annoncée.
\end{proof}

Le phénomène qu'on vient de mettre en évidence, bien particulier aux
corps finis, et qui traduira le fait que leur groupe de Galois absolu
est abélien, est que pour tout polynôme irréductible $h \in
\FF_q[X]$, le polynôme $h$ est scindé sur n'importe quel corps qui
en contient une racine, autrement dit, \emph{le corps de
rupture $\FF_q[X]/(h)$ de $h$ en est un corps de décomposition}.  En
particulier, en utilisant \ref{inclusions-corps-finis}, $\FF_{q^r}$
est un corps de décomposition de $h$ (supposé irréductible !) pour
tout multiple $r$ du degré de $h$.  Si $h$ n'est pas supposé
irréductible, il découle de ce qui vient d'être dit que \emph{son
corps de décomposition est $\FF_{q^r}$ où $r$ est le plus petit
commun multiple des degrés des facteurs irréductibles de $h$}.

De plus, on vient de voir que l'ordre de $\Frob_q$ agissant sur $x$
— ou, par conséquent, sur $\FF_q(x)$ — est exactement le degré $s$
de $x$ sur $\FF_q$.  En utilisant le théorème de l'élément
primitif (\refext{Alg}{element-primitif}), on peut conclure que
$\Frob_q$ agissant sur $\FF_{q^r}$ est d'ordre exactement $r$ ; on
fournira toutefois
en \ref{existence-polynome-irreductible-tout-degre-corps-finis} une
démonstration plus simple du théorème de l'élément primitif dans le
cas particulier des corps finis.

\begin{corollaire2}\label{elements-conjugues-corps-finis}
Soient $x,x' \in \FF_{q^r}$.  Les conditions suivantes sont
équivalentes :
\begin{enumerate}
\item les polynômes minimaux de $x$ et $x'$ sur $\FF_q$ sont égaux,
\item le polynôme minimal de $x$ s'annule en $x'$,
\item tout polynôme $f \in \FF_q[X]$ à coefficient dans $\FF_q$
  s'annulant en $x$ s'annule aussi en $x'$,
\item il existe $i$ (qu'on peut supposer compris entre $0$ et $r-1$)
  tel que $x' = x^{q^i}$.
\end{enumerate}
\end{corollaire2}
\begin{proof}
L'équivalence entre les deux premières conditions (qui n'a rien de
particulier au cas des corps finis) résulte du fait que le polynôme
minimal d'un élément sur $\FF_q$ est l'unique polynôme unitaire
irréductible sur $\FF_q$ s'annulant en cet élément.  L'équivalence
avec la troisième résulte de ce que les polynômes de $\FF_q[X]$
s'annulant en un élément de $\FF_{q^r}$ sont exactement les multiples
du polynôme minimal de cet élément.

Enfin, la proposition précédente montre que, quel que soit $x \in
\FF_{q^r}$, les autres racines de son polynôme minimal sont justement
les $x^{q^i}$ (pour $i$ qu'on peut supposer entre $0$ et $r-1$) : il y
a donc équivalence entre (ii) et (iv).
\end{proof}

Des éléments $x,x' \in \FF_{q^r}$ vérifiant les conditions
équivalentes énoncées dans le
corollaire \ref{elements-conjugues-corps-finis} sont dits
\emph{conjugués sur $\FF_q$}.  La première condition montre qu'il
s'agit bien d'une relation d'équivalence, et la seconde, que tout
élément de $\FF_{q^r}$ a un nombre de conjugués sur $\FF_q$ égal à son
degré sur $\FF_q$.  (Cette définition et ces propriétés seront
généralisées plus tard dans le cadre d'une extension de corps plus
générale : cf. \refext{CG}{conjugues=racines}.)

La proposition suivante généralise la dernière affirmation
de \ref{petit-theoreme-fermat} :
\begin{proposition2}\label{factorisation-x-q-r-x}
La décomposition en facteurs irréductibles du polynôme $X^{q^r} - X$
dans $\FF_q[X]$ est donnée comme le produit de tous les polynômes
unitaires irréductibles de $\FF_q[X]$ de degré divisant $r$, chacun
apparaissant avec multiplicité $1$.

Notamment, la somme des degrés de tous les polynômes unitaires
irréductibles de $\FF_q[X]$ de degré divisant $r$ vaut $q^r$.
\end{proposition2}
\begin{proof}
Si $h \in \FF_q[X]$ est irréductible de degré $s$ avec $s|r$, alors
il est scindé à racines simples dans $\FF_{q^r}$ d'après
\ref{racines-polynome-minimal-corps-fini} et les remarques qui
suivent : il s'ensuit que $h$ divise $X^{q^r} - X$ (dans
$\FF_{q^r}[X]$ donc dans $\FF_q[X]$).  Comme tous les polynômes
unitaires irréductibles de degré divisant $r$ dans $\FF_q[X]$ sont
deux à deux premiers entre eux, le fait que $X^{q^r}-X$ soit multiple
de chacun d'eux implique qu'il est multiple de leur produit.  Pour
conclure, il reste donc à montrer l'égalité des degrés, c'est-à-dire
la dernière affirmation de l'énoncé : or cela se voit en écrivant
$q^r$ (le cardinal de $\FF_{q^r}$) comme somme des cardinaux de chaque
classe de conjugaison d'éléments sur $\FF_q$ (chacune étant associée à
un unique polynôme minimal, dont elle a un cardinal égal au degré).
\end{proof}

\begin{exemple2}\label{irreductibles-sur-f16}
Le polynôme $X^{16}-X$ se factorise sur $\FF_2$ comme : $X^{16}-X =
X(X+1)\penalty-100 (X^2+X+1)\penalty-100 (X^4+X+1)\penalty0
(X^4+X^3+1)\penalty-50 (X^4+X^3+X^2+X+1)$.
\end{exemple2}

\begin{exercice2}
\label{exercice-Phi8}
\begin{enumerate}
\item Vérifier les factorisations dans $𝐂[X]$
\[
X^4+1=(X^2+i)(X^2-i)=(X^2-\sqrt{2} X+1)(X^2+\sqrt{2}X+1)=(X^2+i\sqrt{2}X-1)(X^2-i\sqrt{2}-1).
\]
\item En déduire que $X^4+1$ est irréductible dans $𝐐[X]$.
\item Montrer que $X^4+1$ est réductible dans $𝐅_p[X]$ pour tout nombre
premier $p$. (Indication : on rappelle que l'ensemble des carrés de
$𝐅_p^×$ est un sous-groupe d'indice $2$ de sorte que $a,b ∈  𝐅_p$, alors $a$, $b$ ou $ab$
est un carré dans $𝐅_p$.)
Voir \ref{existence-p-Phin-irreductible-mod-p} pour un énoncé général.
\end{enumerate}
\end{exercice2}

\begin{exercice2}
Soit $n ≥ 0$ un entier.
\begin{enumerate}
\item Montrer que le quotient 
\[K_n=𝐅₂[X_i : 0 ≤ i<n]/(X_i²+X_i+∏_{j<i}X_j, 0 ≤ i<n)
\]
est une extension de $𝐅₂$ de degré $2^n$.
(Indication : on pourra montrer que les monômes
$∏_{i ∈ I} x_i$, où $I$ parcourt les sous-ensembles de $\{0,…,n-1\}$, forment une base
sur $𝐅₂$ de $K_n$.)
\item En observant que tout entier s'écrit de manière unique
comme une somme de produits de monômes en les $2^{2^i}$,
munir $𝐍$ d'une structure de corps, isomorphe à $𝐅_{2^{2^
∞}}$.

\end{enumerate}
\end{exercice2}


\subsubsection{}\label{definition-fonction-de-Moebius} On appelle \emph{fonction de Möbius} la fonction $\mu \colon \NN \to
\ZZ$ définie par $\mu(n) = 0$ si $n$ est multiple du carré d'un entier
autre que $1$ et $\mu(n) = (-1)^t$ si $n = p_1\cdots p_t$ avec
$p_1,\ldots,p_t$ des nombres premiers deux à deux distincts (ainsi,
$\mu(1) = 1$, $\mu(2) = -1$, $\mu(3) = -1$, $\mu(4) = 0$, $\mu(5) =
-1$, $\mu(6) = 1$, $\mu(7) = -1$, $\mu(8) = 0$, $\mu(9) = 0$, $\mu(10)
= 1$).  On admet le résultat suivant :
\begin{proposition2}[théorème d'inversion de Möbius]
Si $\Gamma$ est un groupe abélien et que $f\colon \NN_{>0} \to \Gamma$
est une fonction quelconque, alors les deux formules suivantes sont
équivalentes pour une fonction $g\colon \NN_{>0} \to \Gamma$ :
\[
g(n) = \sum_{d|n} f(d)
\]
\[
f(n) = \sum_{d|n} \mu\big(\frac{n}{d}\big)\, g(d)
\]
\end{proposition2}

\begin{corollaire2}\label{denombrement-polynomes-irreductibles-corps-finis}
\commentaire{changer $r$ en $n$ ? (cf. infra)}
Le nombre de polynômes unitaires irréductibles de degré $n$
sur $\FF_q$ vaut
\[
\frac{1}{n} \sum_{d|n} \mu\big(\frac{n}{d}\big)\, q^d
\]
Où $\mu$ est la fonction de Möbius.  Lorsque $n \to +\infty$ (à $q$
fixé), ce nombre vaut $\frac{1}{n} q^n + O(q^{n/2})$.
\end{corollaire2}
\begin{proof}
Pour ce qui est de la première affirmation, en notant $M(n)$ le nombre
— qu'on cherche à calculer — d'unitaires irréductibles de
degré $n$ sur $\FF_q$, la formule d'inversion de Möbius montre qu'il
suffit de prouver $q^n = \sum_{d|n} d\,M(d)$ : or c'est justement la
deuxième affirmation de l'énoncé de la
proposition \ref{factorisation-x-q-r-x}.

Pour ce qui est de l'estimation asymptotique, remarquons que dans la
somme exacte, le terme $d=n$ vaut $\frac{1}{n} q^n$, le terme
$d=\frac{n}{2}$, s'il existe (c'est-à-dire, si $n$ est pair), vaut
$-\frac{1}{n} q^{n/2}$, et tous les autres termes, dont le nombre est
au plus $n$, sont chacun $O(q^{n/3})$ — leur somme est donc
bien $O(q^{n/2})$.
\end{proof}

Même sans utiliser la formule d'inversion de Möbius, on peut au moins
démontrer, dans le même esprit que cette estimation asymptotique :
\begin{corollaire2}\label{existence-polynome-irreductible-tout-degre-corps-finis}
Sur $\FF_q$, il existe au moins un polynôme irréductible de chaque
degré $r$.  De façon équivalente, dans $\FF_{q^r}$, il existe un
élément de degré $r$ sur $\FF_q$.
\end{corollaire2}
\begin{proof}
Le nombre d'éléments de $\FF_{q^r}$ de degré $<r$ est majoré par la
somme des cardinaux des $\FF_{q^s}$ pour $s|r$, or chacun est de
cardinal $\leq q^{r/2}$ et leur nombre est $\leq r$, par conséquent
cette somme de cardinaux est inférieure ou égale à $r q^{r/2}$.  Pour
avoir la conclusion souhaitée, il suffit d'avoir $q^r > r q^{r/2}$,
soit $q^{r/2} > r$, ce qui se produit dès que $2^r > r^2$, donc dès
que $r > 4$.  Pour les valeurs plus petites de $r$, on constate que
$q^4 > q^2 + q$ et $q^3 > q$ et $q^2 > q$ (et $q > 0$...) pour tout $q
\geq 2$.
\end{proof}

Avec les remarques qui suivent \ref{racines-polynome-minimal-corps-fini},
ceci montre notamment que $\Frob_q$ agissant sur $\FF_{q^r}$ est d'ordre
exactement $r$.

\subsubsection{}Si l'on utilise la formule de Möbius,
sous la forme exacte, on peut obtenir une seconde
démonstration de \ref{existence-polynome-irreductible-tout-degre-corps-finis}.
Il suffit en effet de montrer que pour chaque entier $r$,
on a l'inégalité
$\displaystyle ∑_{\substack{d|r \\ μ(r/d)=1}} q^d ≠ ∑_{\substack{d|r \\ μ(r/d)=-1}} q^d$.
Or, cela résulte de l'unicité de la décomposition d'un entier en
base $q$, elle-même s'observant par exemple par réduction modulo la plus
petite puissance de $q$ apparaissant dans l'une des deux
sommes. On verra en \ref{cyclicite-groupe-multiplicatif-corps} un résultat
plus fin : l'existence d'éléments ou de polynômes
\emph{primitifs}.
On peut préciser le corollaire précédent sous la forme suivante.

\begin{corollaire2}
\label{estimation-uniforme-proportion-polynomes-irreductibles-dans-Fp}
Soit $p ≥ 3$ un nombre premier et soit $d ≥ 1$ un nombre
entier. La proportion des polynômes de degré $d$ dans
$𝐅_p[X]$ qui sont \emph{irréductibles} (resp.
\emph{irréductibles unitaires}) est au moins
égale à $\frac{1}{3d}$ (resp. $\frac{1}{2d}$).
\end{corollaire2}

\begin{démo}
On a vu que le nombre d'éléments primitifs de $𝐅_{p^d}$
sur $𝐅_p$ est minoré
\[
p^d-∑_{\substack{m|d \\ m ≠ d}} p^m ≥ p^d - ∑_{m=1}^{d-1}p^m >
p^d-\frac{p^d}{p-1}=p^d ⋅ \frac{p-2}{p-1}.
\]
Le nombre de polynômes irréductibles \emph{unitaires}
de degré $d$ est donc minoré par un $d$-ième
de cette quantité, et celui des polynômes irréductibles
non nécessairement unitaires (donc de coefficient
dominant arbitraire dans $𝐅_p^×$) par
$p-1$ fois cette dernière quantité.
La conclusion résulte alors des inégalités
$\frac{p-2}{p-1} ≥ ½$ et $1-\frac{2}{p} ≥ ⅓$.
\end{démo}

\subsubsection{Fonction zêta $ζ$}Pour tout polynôme unitaire $f ∈ 𝔽_p[T]$, notons $|f|$ l'entier
$p^{\deg(f)}$ ; en particulier, $|1|=1$. Pour chaque $s ∈ ℂ$ de partie réelle $>1$, considérons la série
(de Dirichlet)
\[
ζ(s) ≔ ∑_{f \text{ unitaire}} \frac{1}{|f|^s},
\]
analogue à la fonction zêta usuelle de Riemann $\displaystyle ζ_{ℤ}(s) ≔ ∑_{n ≥ 1} \frac{1}{n^s} = ∏_{p} \frac{1}{1-p^{-s}}$.
Ici aussi, l'existence et l'unicité de la décomposition en produit d'irréductibles entraîne formellement l'égalité
(« produit eulérien ») $ζ(s) = ∏_{P \text{ irr. unit.}} \frac{1}{1-|P|^{-s}}$.
En effet, le terme de droite est égal à $∏_{P} \big(∑_{n ≥ 1} |P|^{-ns}\big)=∑_f |f|^{-s}$ :
si $f=P₁^{n₁} ⋯ P_r^{n_r}$, on a $|f|^{-s}=|P₁|^{-n₁s} ⋯ |P_r|^{-n_rs}$.
Par contre, à la différence du cas de l'anneau $ℤ$, la fonction zêta de $𝔽_p[T]$
est facile à calculer : $ζ(s)=\displaystyle ∑_{d ≥ 0} \frac{p^d}{p^{ds}}=\frac{1}{1-p⋅p^{-s}}$ car il
y a exactement $p^d$ polynômes unitaires de degré $d$.

\subsubsection{Fonction Zêta $Z$}Il est parfois plus commode de faire le changement de variable $x=p^{-s}$, c'est-à-dire considérer la série (formelle/entière)
\[
Z(x) ≔ ∏_P \frac{1}{1-x^{\deg(P)}}= ∏_{d ≥ 1} \frac{1}{(1-x^d)^{I_d}},
\]
où $P$ parcourt les polynômes irréductibles unitaires de $𝔽_p[T]$ et
$I_d$ désigne le nombre d'entre eux de degré $d$.
Par construction, on a $ζ(s)=Z(p^{-s})$ et, d'après le calcul du paragraphe précédent,
on a $\displaystyle Z(x)=\frac{1}{1-px}$.
Notons qu'en prenant la dérivée logarithmique de l'égalité $\displaystyle ∏_{d ≥ 1} \frac{1}{(1-x^d)^{I_d}}=\frac{1}{1-px}$,
on retrouve les égalités $∑_{a|d} aI_a=p^d$.

\subsubsection{Polynômes sans facteur carré}
Soit $ζ_{⧄}$ l'analogue de $ζ$ pour les polynômes unitaires
\emph{sans facteur carré} : $ζ_{⧄}(s)=∑_{f} |f|^{-s}$ où $f$ parcourt les polynômes unitaires
sans facteur carré. On a trivialement $ζ_{⧄}(s)=∏_P (1+|P|^{-s})$,
où $P$ parcourt les polynômes unitaires irréductibles.
De l'identité $\displaystyle 1+z=\frac{1-z²}{1-z}$ appliquée aux $z=|P|^{-s}$, on tire l'égalité
\[
ζ_{⧄}(s)=\frac{ζ(s)}{ζ(2s)}.
\]
On peut réécrire cette formule en faisant le changement de variable précédent :
\[
Z_{⧄}(x)=\frac{Z(x)}{Z(x²)}=\frac{1-px²}{1-px}.
\]
Comme $Z_{⧄}(x)=∑_d I^{⧄}_d   x^d$, où $I^{⧄}_d$ est le nombre de polynômes unitaires
de degré $d$ sans facteur carré, on a $I^{⧄}_d=p^d-p^{d-1}=p^d(1-p^{-1})$
pour chaque $d ≥ 2$. On a donc démontré la proposition suivante.

\begin{proposition2}
La proportion de polynômes $f ∈ 𝔽_p[T]$ unitaires de degré $d ≥ 2$ sans facteur carré est $\displaystyle 1-p^{-1}=\frac{1}{ζ(2)}$.
\end{proposition2}

(Il n'est pas difficile de montrer directement qu'à $d$ fixé le nombre de tels polynômes est $1-𝗈(1)$ lorsque $p → + ∞$,
cf. p. ex. \cite[lemme 4]{cycles-of-a-random-permutation//Tao}.)

\subsubsection{Nombre moyen de facteurs irréductibles}
Pour tout polynôme unitaire $f ∈ 𝔽_p[T]$, notons $λ(f)$ le nombre de ses facteurs irréductibles
(comptés avec multiplicités, avec la convention que $λ(1)=0$) et considérons la série formelle de deux
variables
\[
Z(x,u) ≔ ∏_{d ≥ 1} (1-ux^d)^{-I_d} = ∑_f x^{\deg(f)} u^{λ(f)}
\]
qui encode les nombres de polynômes unitaires $f$ de degré et nombre de facteurs irréductibles donnés.
Elle raffine la fonction Zêta précédente : $Z(x,1)=Z(x)$.
Sa dérivée logarithmique par rapport à la nouvelle variable $u$
est égale à $\displaystyle ∑_{d ≥ 1} \frac{I_d x^d}{1-ux^d}=∑_{d ≥ 1,k ≥ 0} I_d x^{d(k+1)} u^k$
si bien que l'on a l'égalité
\[
Z(x,u)= \exp\big(∑_{k ≥ 1} u^k \frac{I(x^k)}{k}\big)\text{ où }I(x) ≔ ∑_{d ≥ 1} I_d x^d.
\]
Pour chaque entier $d ≥ 1$, notons $𝕖_d$ le nombre moyen de facteurs irréductibles
d'un polynôme unitaire de degré $d$.  
Par construction et le calcul précédent, on a
\[
∑_{d ≥ 1} 𝕖_d x^d = \frac{\mathrm{d}Z}{\mathrm{d}u}(x/p,u)_{|u=1} = Z(x/p)× ∑_{k ≥ 1} I(x^k/p^k).
\]
Or, il résulte de la formule d'inversion de Möbius que l'on a
\[
I(x) = -∑_{m ≥ 1} \frac{μ(m)}{m}\log(1-px^m)
\]
d'où, en utilisant $∑_{m|d} φ(m)=d$ et à nouveau la formule d'inversion,
\[
∑_{k ≥ 1} I(x^k)= - ∑_{d ≥ 1} \frac{φ(d)}{d}\log(1-px^d).
\]
Finalement, $\displaystyle ∑_{d ≥ 1} 𝕖_d x^d = \frac{1}{1-x}∑_{d ≥ 1} \frac{φ(d)}{d}\log(\frac{1}{1-p^{1-d}x^d})$.
En développant le logarithme, on en déduit que
\[
𝕖_d=\big(1+\frac{1}{2}+\frac{1}{3}+ ⋯ +\frac{1}{d}\big) + ∑_{r=1}^d \frac{1}{r p^r} \big(∑_{k ≥ 2 \atop k-1 ∣ r} φ(k) ⋅ (1-\frac{1}{k})\big).
\]
Le second terme est un $\displaystyle 𝖮(∑_{r=1}^d r p^{-r})=𝖮(p^{-1})$, uniformément en $d$.
On a donc en particulier montré la proposition suivante.
\begin{proposition2}
Le nombre moyen de facteurs irréductibles
d'un polynôme unitaire de degré $d$ de $𝔽_p[T]$
est équivalent à $\log(d)$ lorsque $d → + ∞$ ($p$ fixé ou non).
\end{proposition2}

Il en est du même du nombre moyen de cycles d'une
permutation aléatoire de $𝔖_d$ lorsque $d → +∞$ ;
ce n'est pas une coïncidence.
% Préciser ce lien.

\subsection{Critères d'irréductibilité}

\begin{proposition2}[critère d'irréductibilité de Rabin]\label{critere-rabin}
Un polynôme $h \in \FF_q[X]$ de degré $r$ est irréductible si et
seulement si il vérifie la conjonction des deux conditions
suivantes :
\begin{itemize}
\item le polynôme $h$ divise $X^{q^r}-X$,
\item le polynôme $h$ est premier avec $X^{q^s}-X$ pour tout $s$
diviseur strict de $r$ (ou simplement les diviseurs immédiats de $r$,
c'est-à-dire les $r/\ell$ avec $\ell$ diviseur premier de $r$).
\end{itemize}
\end{proposition2}
\begin{proof}
Si $h$ est irréductible de degré $r$, alors,
d'après \ref{factorisation-x-q-r-x}, $h$ divise $X^{q^r}-X$, et s'il
divise $X^{q^s}-X$ pour $s|r$, on doit avoir $r|s$, ce qui n'est
possible que pour $s=r$ et la seconde condition est démontrée
($h$ étant supposé irréductible, s'il ne divise pas $X^{q^s}-X$, il
est premier avec lui).

Réciproquement, si $h$ vérifie les deux conditions annoncées, et si
$h_1$ en est un facteur irréductible, le degré $r_1$ de $h_1$ doit
diviser $r$ d'après la première condition (toujours en
utilisant \ref{factorisation-x-q-r-x}), et il ne peut pas être un
diviseur strict de $r$ d'après la seconde condition (qui assure que
$h_1$ ne divise pas $X^{q^s}-X$) : donc $r_1=r$ et $h_1=h$.  Ceci
montre que $h$ est irréductible.

Le fait qu'il suffise de tester la seconde condition pour les
diviseurs $s$ de la forme $r/\ell$ avec $\ell$ premier résulte de ce
que $X^{q^s}-X$ divise $X^{q^{s'}}-X$ si $s|s'$.
\end{proof}

\begin{remarques2}\label{remarques-critere-rabin}
\begin{itemize}
\item On ne peut pas se contenter de vérifier l'une des deux conditions
énoncées : l'exemple du polynôme $X^6+X^5+X^4+X^3+X^2+X+1 =
(X^3+X^2+1)\penalty-100 (X^3+X+1) \in \FF_2[X]$, qui n'est pas
irréductible mais vérifie la première condition (il divise déjà
$X^8-X$) montre que la première condition, seule, n'assure pas
l'irréductibilité ; et l'exemple du polynôme $X^5 + X^4 + 1 =
(X^2+X+1)\penalty-100 (X^3+X+1) \in \FF_2[X]$, qui n'est pas
irréductible mais est premier à $X^2-X$ montre que la seconde
condition, seule, n'est pas non plus suffisante.  On peut aussi donner
l'exemple de $X^6 + X^5 + X = X (X^2+X+1) (X^3+X+1) \in \FF_2[X]$, qui
n'est pas irréductible bien qu'il vérifie la première condition et
aussi la seconde condition dans laquelle on a affaibli « $h$ est
premier avec $X^{q^s}-X$ » en « $h$ ne divise pas $X^{q^s}-X$ » (pour
tout diviseur $s$ de $r$, soit ici $s \in \{1,2,3\}$).
\item Le critère de Rabin fournit un \emph{algorithme} permettant de
tester l'irréductibilité d'un polynôme $h \in \FF_q[X]$ de degré $r$
en un nombre raisonnable (i.e., polynomial\footnote{On peut par
exemple montrer qu'il s'effectue en au pire $O(r^{2+\varepsilon})$
opérations pour tout $\varepsilon>0$, où la constante impliquée par
le $O$ dépend de $\varepsilon$ et $q$.} en $r$) d'opérations
dans $\FF_q$ : en effet, la première condition du critère s'exprime
également comme $X^{q^r} \equiv X \pmod{h}$, ce qui se teste en
calculant $X^{q^r}$ dans $\FF_q[X]/(h)$ au moyen d'un algorithme
d'exponentiation rapide, et la seconde condition, pour un $s$ donné,
peut se tester au moyen de l'algorithme d'Euclide étendu (pour
calculer le pgcd), dont la première étape consiste à calculer le reste
de la division euclidienne de $X^{q^s}-X$ par $h$, ce qui peut de
nouveau se faire en travaillant dans $\FF_q[X]/(h)$.
\item Une fois qu'on dispose d'un algorithme permettant de tester
l'irréductibilité d'un polynôme $h \in \FF_q[X]$ de degré $r$ donné,
il est possible de \emph{générer} des polynômes irréductibles de
degré $r$ selon le principe simple suivant : tirer un polynôme
(unitaire) de degré $r$ au hasard, tester son irréductibilité, et
recommencer jusqu'à trouver un polynôme irréductible.  En vertu de
l'asymptotique trouvée
en \ref{denombrement-polynomes-irreductibles-corps-finis}, parmi les
$q^r$ polynômes unitaires de degré $r$ sur $\FF_q$, une proportion
d'environ $\frac{1}{r}$ d'entre eux sont irréductibles, donc
l'algorithme qu'on vient de décrire réussira en environ $r$ essais en
moyenne.  Enfin, il convient de remarquer que la connaissance d'un
polynôme $h$ irréductible de degré $r$ sur $\FF_p$ permet de
représenter $\FF_{p^r}$ comme $\FF_p[X]/(h)$ (les calculs dans $\FF_p
= \ZZ/p\ZZ$ sont, pour leur part, faciles) : en combinant avec ce qui
vient d'être dit, on dispose des outils algorithmiques permettant
d'effectuer des calculs dans tous les corps finis.
\end{itemize}
\end{remarques2}

\begin{exemple2}\label{exemple-numerique-critere-rabin}
Montrons sur l'exemple de $h = X^6 -2 X^4 + 3 X^3 - X^2 - X -
2 \in \FF_7[X]$ comment on peut appliquer le critère de Rabin en
pratique, même sans ordinateur.  On commence par calculer la table des
restes modulo $h$ des puissances $X^7, X^{7\times 2}, X^{7\times
3}, \ldots, X^{7\times 6}$ de l'indéterminée :
\[
\begin{array}{r@{\,}l}
X^7 &\equiv 2X^5 - 3X^4 + X^3 + X^2 + 2X \pmod{h}\\
X^{14} &\equiv -3X^5 - 2X^4 + 2X^3 + 2X^2 + 2X + 2 \pmod{h}\\
X^{21} &\equiv -2X^5 + 3X^4 - 3X^3 - X^2 - 1 \pmod{h}\\
X^{28} &\equiv 3X^5 - 3X^4 - 2X^3 + 2X \pmod{h}\\
X^{35} &\equiv X^5 - 3X^4 - 2X^3 - 2X + 3 \pmod{h}\\
X^{42} &\equiv -3X^5 + X^4 + X^3 - X^2 + X \pmod{h}\\
\end{array}
\]
(la première ligne se calcule par division euclidienne de $X^7$
par $h$, puis chaque ligne suivante en multipliant par $2X^5 - 3X^4 +
X^3 + X^2 + 2X$ et en effectuant une nouvelle division euclidienne
par $h$).  Il est également utile de préparer une table des valeurs du
Frobenius sur le corps de base : ici, $a \mapsto a^7$ sur $\FF_7$ est
bien sûr l'identité.  Au moyen de ces deux tables, on peut facilement
élever n'importe quel polynôme à la puissance $7$ modulo $h$, donc
calculer $X^{7^i}$ pour $i$ allant de $1$ à $6$ modulo $h$ :
\[
\begin{array}{r@{\,}l}
X^7 &\equiv 2X^5 - 3X^4 + X^3 + X^2 + 2X \pmod{h}\\
X^{7^2} &\equiv 2^7 X^{35} - 3^7 X^{28} + X^{21} + X^{14} + 2^7 X^7\\
&\equiv -X^5 - 2X^4 + 3X^3 + 3X^2 + 3X \pmod{h}\\
X^{7^3} &\equiv -X^{35} - 2^7 X^{28} + 3^7 X^{21} + 3^7 X^{14} + 3^7 X^7\\
&\equiv -2X^5 + 3X^4 - X^3 - X^2 + 3X \pmod{h}\\
X^{7^4} &\equiv -2^7 X^{35} + 3^7 X^{28} - X^{21} - X^{14} + 3^7 X^7\\
&\equiv -3X^5 + X^4 + 2X^3 + 2X^2 \pmod{h}\\
X^{7^5} &\equiv -3^7 X^{35} + X^{28} + 2^7 X^{21} + 2^7 X^{14} \\
&\equiv -3 X^5 + X^4 + 2 X^3 + 2 X^2 - 2 X \pmod{h}\\
X^{7^6} &\equiv -3^7 X^{35} + X^{28} + 2^7 X^{21} + 2^7 X^{14} - 2^7 X^7 \\
&\equiv X \pmod{h}\\
\end{array}
\]
L'égalité $X^{7^6} \equiv X \pmod{h}$ montre que la première partie du
critère de Rabin est vérifiée.  Pour la seconde partie, il s'agit de
continuer l'algorithme d'Euclide pour calculer le pgcd de $X^{7^2} -
X \equiv -X^5 - 2X^4 + 3X^3 + 3X^2 + 2X$ et de $X^{7^3} - X\equiv
-2X^5 + 3X^4 - X^3 - X^2 + 2X$ avec $h$ : or au prix de nouvelles
divisions euclidiennes, on trouve
\[
\begin{array}{c}
h \equiv -2X^4 + 2X^2 + 2X - 2 \pmod{-X^5 - 2X^4 + 3X^3 + 3X^2 + 2X}\\
-X^5 - 2X^4 + 3X^3 + 3X^2 + 2X \equiv 2X^3 + X + 2 \pmod{-2X^4 + 2X^2 + 2X - 2}\\
-2X^4 + 2X^2 + 2X - 2 \equiv 3 X^2 - 3 X - 2 \pmod{2X^3 + X + 2}\\
2X^3 + X + 2 \equiv 2 X + 1 \pmod{3 X^2 - 3 X - 2}\\
3 X^2 - 3 X - 2 \equiv 2 \pmod{2X + 1}\\
\end{array}
\]
ce qui montre que $X^{7^2} - X$ est premier avec $h$, et pour ce qui
est de $X^{7^3} - X$ :
\[
\begin{array}{c}
h \equiv -2X^4 + X^2 - 3X - 2 \pmod{-2X^5 + 3X^4 - X^3 - X^2 + 2X}\\
-2X^5 + 3X^4 - X^3 - X^2 + 2X \equiv -2X^3 + 3X - 3 \pmod{-2X^4 + X^2 - 3X - 2}\\
-2X^4 + X^2 - 3X - 2 \equiv -2X^3 + 3X - 3 \pmod{-2X^3 + 3X - 3}\\
-2X^3 + 3X - 3 \equiv -2 X^2 - 2 \pmod{-2X^3 + 3X - 3}\\
-2X^3 + 3X - 3 \equiv -2 X - 3 \pmod{-2 X^2 - 2}\\
-2 X^2 - 2 \equiv -3 \pmod{-2 X - 3}\\
\end{array}
\]
— ce qui conclut la vérification du critère de Rabin.  Tous ces
calculs montrent donc que $h = X^6 -2 X^4 + 3 X^3 - X^2 - X - 2$ est
irréductible dans $\FF_7[X]$.

Par la suite, nous passerons normalement sous silence toutes les
vérifications du fait qu'un polynôme univarié à coefficients dans un
corps fini est irréductible.
\end{exemple2}

Le critère suivant, dans le même esprit que celui de Rabin, et plus
simple à énoncer, est plus généralement efficace quand il s'agit de
générer des polynômes irréductibles par le procédé expliqué à la fin
de \ref{remarques-critere-rabin} :
\begin{proposition2}[critère d'irréductibilité de Ben-Or]\label{critere-ben-or}
Un polynôme $h \in \FF_q[X]$ de degré $r$ est irréductible si et
seulement si $h$ est premier avec $X^{q^i}-X$ pour tout $1 \leq i \leq
\frac{r}{2}$ (c'est-à-dire $1 \leq i \leq \lfloor\frac{r}{2}\rfloor$
où $\lfloor\tiret\rfloor$ désigne la partie entière).
\end{proposition2}
\begin{proof}
D'après \ref{factorisation-x-q-r-x}, les facteurs irréductibles de
$X^{q^i}-X$ pour un $1\leq i<r$ ont pour degré les diviseurs de
ce $i$, qui sont donc toujours strictement inférieurs à $r$ : ceci
montre qu'un $h$ irréductible de degré $r$ est premier avec tous les
$X^{q^i}-X$ pour $1\leq i<r$ (et en particulier $1 \leq
i \leq \frac{r}{2}$).  Réciproquement, si $h$ a un facteur
irréductible $h_1$ de degré $r_1<r$, alors on peut supposer
$r_1 \leq \frac{r}{2}$ (quitte à remplacer $h_1$ par un facteur
irréductible de $h/h_1$ si ce n'est pas le cas), et dans ce cas $h_1$
divise $X^{q^{r_1}}-X$ donc $h$ n'est pas premier avec ce dernier.
\end{proof}

Le critère d'irréductibilité suivant utilise, pour sa part, l'algèbre
linéaire plutôt que des manipulations de polynômes (on rappelle que
$h \in \FF_q[X]$ est dit \emph{séparable} lorsque $h$ est à racines
simples dans une clôture algébrique de $\FF_q$, c'est-à-dire,
concrètement, lorsque $h$ et $h'$ sont premiers entre eux, ce qui peut
se tester algorithmiquement par l'algorithme d'Euclide ; comme les
corps finis sont parfaits, cela équivaut encore à dire que $h$ est
sans facteur carré, cf. \ref{rappels-polynomes-sans-facteurs-carres-corps-finis}).
\begin{proposition2}[critère d'irréductibilité de Butler]\label{critere-butler}
Un polynôme $h \in \FF_q[X]$ de degré $r$ séparable est irréductible
si et seulement si $\dim_{\FF_q} \Ker(\Frob_q - \Id) = 1$, où
$\Frob_q \colon x \mapsto x^q$ et $\Id \colon x \mapsto x$ sont vus
comme des applications $\FF_q$-linéaires sur $\FF_q[X]/(h)$.
\end{proposition2}
\begin{proof}
Si $h$ est irréductible alors $\FF_q[X]/(h)$ est un corps (isomorphe
à) $\FF_{q^r}$ dans lequel $\Ker(\Frob_q - \Id)$ est le sous-corps
$\FF_q$ qui est donc de dimension $1$ comme $\FF_q$-espace vectoriel.

De façon générale, quel que soit $h \in \FF_q[X]$, le $\FF_q$-espace
vectoriel $\Ker(\Frob_q - \Id)$ contient au moins celui engendré
par $1$, donc sa dimension est au moins $1$ : il reste à prouver que
si $h$ est réductible cette dimension doit être strictement
supérieure.  Si $h = h_1 h_2$ avec $h_1,h_2$ premiers entre eux, on a
$\FF_q[X]/(h) \cong \FF_q[X]/(h_1) \times \FF_q[X]/(h_2)$ par le
théorème chinois, donc la dimension de $\Ker(\Frob_q - \Id)$ sur tout
cet espace vaut au moins $1+1=2$.
\end{proof}

Il sera de nouveau question de $\Ker(\Frob_q - \Id)$ (l'\emph{algèbre
de Berlekamp} de $h$) dans la
proposition \refext{ACF}{proposition-algorithme-berlekamp} qui généralise le
critère ci-dessus.

\begin{exemple2}\label{exemple-numerique-critere-butler}
Reprenons l'exemple du polynôme $h = X^6 -2 X^4 + 3 X^3 - X^2 - X -
2 \in \FF_7[X]$ de \ref{exemple-numerique-critere-rabin} en lui
appliquant cette fois le critère de Butler : il faut d'abord vérifier
que $h$ est séparable, c'est-à-dire, premier avec sa dérivée $h' =
-X^5 - X^3 + 2 X^2 - 2 X - 1$, ce qui se fait au moyen de l'algorithme
d'Euclide :
\[
\begin{array}{c}
h \equiv -3 X^4 - 2 X^3 - 3 X^2 - 2 X - 2 \pmod{h'}\\
h' \equiv -2 X^3 + 2 X^2 - X - 3 \pmod{-3 X^4 - 2 X^3 - 3 X^2 - 2 X - 2}\\
-3 X^4 - 2 X^3 - 3 X^2 - 2 X - 2 \equiv -3 X^2 - 2 X + 2 \pmod{-2 X^3 + 2 X^2 - X - 3}\\
-2 X^3 + 2 X^2 - X - 3 \equiv -3 X \pmod{-3 X^2 - 2 X + 2}\\
-3 X^2 - 2 X + 2 \equiv 2\pmod{-3 X}\\
\end{array}
\]
(la dernière ligne de calcul est, en fait, inutile : tout polynôme de
coefficient constant non nul est premier avec un multiple nul de
l'indéterminée).  On calcule alors la matrice de l'endomorphisme
$\Frob_7 - \Id$ sur la base $1, X, X^2, \ldots, X^5$ de
$\FF_7[X]/(h)$, en calculant successivement $X^7, X^{14}, \ldots,
X^{35}$ modulo $h$ — les calculs sont donc très semblables à ceux
menés au début de \ref{exemple-numerique-critere-rabin} et conduisent
à :
\[
\Frob_7 = \left(
\begin{matrix}
1& 0& 2&-1& 0& 3\\
0& 2& 2& 0& 2&-2\\
0& 1& 2&-1& 0& 0\\
0& 1& 2&-3&-2&-2\\
0&-3&-2& 3&-3&-3\\
0& 2&-3&-2& 3& 1\\
\end{matrix}
\right)
\;,\;\;
\Frob_7-\Id = \left(
\begin{matrix}
0& 0& 2&-1& 0& 3\\
0& 1& 2& 0& 2&-2\\
0& 1& 1&-1& 0& 0\\
0& 1& 2& 3&-2&-2\\
0&-3&-2& 3& 3&-3\\
0& 2&-3&-2& 3& 0\\
\end{matrix}
\right)
\]
(Les coefficients de la première matrice sont les coefficients des
restes de $X^7, X^{14}, X^{21},\ldots, X^{35}$ modulo $h$, comme
calculés en \ref{exemple-numerique-critere-rabin}.)  On calcule le
rang de cette deuxième matrice en appliquant l'algorithme du pivot de
Gauß : on se convainc ainsi que les cinq colonnes non-nulles sont
linéairement indépendantes, c'est-à-dire que le rang est $5$, ce qui
prouve bien $\dim_{\FF_7} \Ker(\Frob_7 - \Id) = 1$, donc $h$ est bien
irréductible.
\end{exemple2}

\subsection{Polynômes irréductibles et extensions}

\subsubsection{} Nous étudions maintenant ce que devient un polynôme
irréductible sur un corps fini lorsque ce dernier est remplacé par une
extension (d'abord de degré divisant le degré du polynôme, puis
premier avec lui, et enfin en corollaire dans le cas général).

\begin{proposition2}\label{scindage-partiel-polynomes-corps-finis}
Soit $f \in \FF_q[X]$ irréductible de degré $r$, et $s$ un diviseur
de $r$.  Alors $f$ vu dans $\FF_{q^s}[X]$ est produit de $s$ facteurs
irréductibles chacun de degré $r/s$.  Si $h$ est l'un de ces facteurs,
alors tous sont donnés par les $\Frob_q^i(h)$ (où par là on désigne le
polynôme de même degré que $h$, dont les coefficients sont image de
ceux de $h$ par $\Frob_q^i$, sans faire agir ce dernier sur
l'indéterminée) pour $i$ allant de $0$ à $s-1$.
\end{proposition2}
\begin{proof}[Première démonstration]
Puisque $f$ est irréductible sur $\FF_q$, on
sait (\ref{factorisation-x-q-r-x}) qu'il divise $X^{q^r}-X$, qui
s'écrit encore $X^{(q^s)^{r/s}}-X$, par conséquent (toujours
d'après \ref{factorisation-x-q-r-x}) sur $\FF_{q^s}$ le polynôme $f$
est produit de facteurs irréductibles distincts de degrés
divisant $r/s$.  Mais par ailleurs $f$ est premier avec $X^{q^t}-X$
pour tout diviseur strict $t$ de $r$ (\ref{critere-rabin}) : en
particulier avec les $X^{(q^s)^t}-X$ pour $t$ diviseur strict
de $r/s$ ; ceci montre que les facteurs irréductibles de $f$ sont de
degré exactement $r/s$, et par conséquent ils sont bien au nombre
de $s$.  Si $h$ est un quelconque de ces facteurs irréductibles, qu'on
choisira unitaire, alors $\Frob_q^i(h)$ est encore, pour chaque $i$
entre $0$ et $s-1$, un facteur irréductible de degré $r/s$ de $h$ (car
$\Frob_q$ est un automorphisme de $\FF_q$).  Reste à savoir que tous
ces facteurs sont distincts (donc premiers entre eux) : or si $h$
était laissé stable par un $\Frob_q^i$ avec $0<i<s$, il serait à
coefficients dans un $\FF_{q^{s'}}[t]$ avec $s'$ diviseur strict
de $s$, dans lequel il serait certainement irréductible, mais c'est
impossible car on vient de voir que les facteurs irréductibles de $f$
dans $\FF_{q^{s'}}[t]$ sont de degré $r/s' > r/s$.
\end{proof}
\begin{proof}[Seconde démonstration]
Soit $h$ un facteur irréductible de $f$ dans $\FF_{q^s}[X]$, et $x$
une racine de $h$ dans $\FF_{q^r}$ (qui existe puisque $f$, donc $h$,
est scindé sur $\FF_{q^r}$).  Le degré de $x$, c'est-à-dire de
$\FF_q(x) = \FF_{q^r}$, sur $\FF_q$ vaut $r$, et par conséquent
(\ref{inclusions-corps-finis} ou \refext{Alg}{multiplicativité degré})
son degré sur $\FF_{q^s}$ vaut $r/s$ : c'est donc le degré de $h$
(polynôme minimal de $x$ sur $\FF_{q^s}$).  On a vu
en \ref{racines-polynome-minimal-corps-fini} que les racines de $f$
(dans $\FF_{q^r}$) sont les $\Frob_q^i(x)$ pour $i$ allant de $0$
à $r-1$, et que celles de $h$ sont les $(\Frob_{q^s})^j(x)
= \Frob_q^{js}(x)$ pour $j$ allant de $0$ à $(r/s)-1$.  Pour $i$
allant de $0$ à $s-1$, le polynôme $\Frob_q^i(h) \in \FF_{q^s}[X]$
s'annule en $\Frob_q^i(x)$ et en tous les $\Frob_q^{i+js}(x)$ ; il est
irréductible puisque $\Frob_q^i$ est un automorphisme de
$\FF_{q^s}[X]$ (et que $h$ est irréductible), et tous ces polynômes
$\Frob_q^i(h)$ sont premiers entre eux puisque leurs racines dans
$\FF_{q^r}$, où ils se scindent, sont disjointes : par conséquent, $f$
est bien égal, à une constante près, au produit des $\Frob_q^i(h)$
(pour $i$ allant de $0$ à $s-1$).
\end{proof}

Voir \ref{descindage-polynomes-tours-corps-finis} pour une sorte de
réciproque de cette affirmation.

\begin{proposition2}\label{polynomes-restent-irreductibles-corps-finis}
Soit $h \in \FF_q[X]$ irréductible de degré $r$, et soit $s$ premier
avec $r$.  Alors $h$ vu dans $\FF_{q^s}[X]$ est encore irréductible.
\end{proposition2}
\begin{proof}[Première démonstration]
D'après le critère de Rabin (\ref{critere-rabin}), le polynôme $h$
divise $X^{q^r}-X$, et est premier avec $X^{q^t}-X$ pour tout $t$
diviseur strict de $r$ : on veut prouver la même chose en remplaçant
$q$ par $q^s$.  Le fait que $X^{q^r}-X$ divise $X^{(q^s)^r}-X$ (et
donc que $h$ divise ce dernier) résulte du
lemme \ref{lemme-divisibilite-x-q-r-x} ; par ailleurs, un diviseur de
$h$ et de $X^{q^{st}}-X$ devrait diviser à la fois $X^{q^r}-X$ et
$X^{q^{st}}-X$ donc leur pgcd, qui vaut $X^{q^t}-X$
d'après \ref{lemme-pgcd-x-q-r-x} (puisque le pgcd de $r$ et $st$
est $t$).
\end{proof}
\begin{proof}[Seconde démonstration]
Soit $h_1$ un facteur irréductible de $h$ dans $\FF_{q^s}[X]$, et $x$
une racine de $h_1$ dans $\FF_{q^{rs}}$ (qui existe puisque $h$ est
scindé sur $\FF_{q^r}$, donc dans $\FF_{q^{rs}}$, donc $h_1$ est
scindé dans $\FF_{q^{rs}}$).  Alors $(\Frob_{q^s})^i(x)
= \Frob_q^{is}(x)$ est racine de $h_1$ pour tout $i$.  Or, $s$ étant
premier avec $r$, l'entier $is$ prend toutes les valeurs possibles
modulo $r$, donc $\Frob_q^{is}(x)$ parcourt toutes les racines de $h$
(cf. \ref{racines-polynome-minimal-corps-fini}) : ceci montre que
toute racine de $h$ est racine de $h_1$ et finalement $h = h_1$ est
irréductible dans $\FF_{q^s}[X]$.
\end{proof}

\begin{corollaire2}\label{corollaire-scindage-partiel-polynomes-corps-finis}
Soit $f \in \FF_q[X]$ irréductible de degré $r$, et $s > 0$ un entier
naturel, et soit $d = \pgcd(r,s)$.  Alors $f$ vu dans $\FF_{q^s}[X]$
est produit de $d$ facteurs irréductibles chacun de degré $r/d$.  Si
$h$ est l'un de ces facteurs, alors tous sont donnés par les
$\Frob_q^i(h)$ (où par là on désigne le polynôme de même degré
que $h$, dont les coefficients sont image de ceux de $h$ par
$\Frob_q^i$, sans faire agir ce dernier sur l'indéterminée) pour $i$
allant de $0$ à $d-1$.
\end{corollaire2}
\begin{proof}
C'est une conséquence immédiate des
propositions \ref{scindage-partiel-polynomes-corps-finis} et \ref{polynomes-restent-irreductibles-corps-finis},
en appliquant la première pour décrire $f$ dans $\FF_{q^d}[X]$ et la
seconde pour voir que chacun des facteurs irréductibles reste
irréductible en passant de $\FF_{q^d}[X]$ à $\FF_{q^s}[X]$ (vu que
$s/d$ est premier avec $r$).
\end{proof}

La proposition suivante doit être vue comme un complément
à \ref{scindage-partiel-polynomes-corps-finis} :

\begin{proposition2}\label{descindage-polynomes-tours-corps-finis}
Soit $h \in \FF_{q^s}[X]$ unitaire irréductible de degré $t$.  Alors
le polynôme $f = \prod_{i=0}^{s-1}\Frob_q^i(h)$, de degré $st$,
appartient à $\FF_q[X]$, et il est irréductible si et seulement si le
ppcm des degrés sur $\FF_q$ des coefficients de $h$ est égal à $s$.
\end{proposition2}
\begin{proof}
Le fait que $f$ appartienne à $\FF_q[X]$ vient de ce que $\Frob_q(f) =
f$ (on rappelle que $\Frob_q$ opère uniquement sur les coefficients
des polynômes), comme il résulte aisément de $\Frob_q^s(h) = h$.

Dire que le ppcm des degrés sur $\FF_q$ des coefficients de $h$ est
égal à $s$ signifie (cf. \ref{racines-polynome-minimal-corps-fini})
que $\Frob_q$ a pour période exactement $s$ en agissant sur $h$,
c'est-à-dire que tous les $\Frob_q^i(h)$ (pour $i$ allant de $0$
à $s-1$) sont distincts et donc, étant unitaires et irréductibles
sur $\FF_{q^s}$, premiers entre eux.  Si c'est le cas, alors $f$ est
irréductible sur $\FF_q$, car aucun sous-ensemble non trivial de ses
facteurs irréductibles $\Frob_q^i(h)$ sur $\FF_{q^s}$ n'est stable
par $\FF_q$ donc ne définit de polynôme de $\FF_q[X]$.
Réciproquement, si $f$ est irréductible dans $\FF_q[X]$, il a $st$
racines distinctes dans $\FF_{q^{st}}$, donc tous les $\Frob_q^i(h)$
sont distincts.
\end{proof}

On étudiera en \refext{ACF}{remarque-tours-corps-finis} la question du rapport
entre les présentations de $\FF_{q^{st}}$, dans les conditions de la
proposition précédente, données par $\FF_q[X]/(f)$ et par
$\FF_{q^s}[X]/(h)$.

\section{Éléments primitifs et groupe multiplicatif}

\subsection{Éléments primitifs}

\begin{théorème2}\label{cyclicite-groupe-multiplicatif-corps}
Tout sous-groupe fini du groupe multiplicatif d'un corps est cyclique.
En particulier, le groupe multiplicatif d'un corps fini est cyclique.
\end{théorème2}

\begin{remarque2}
Soient $r$ un entier et $x$ un générateur du groupe
multiplicatif $𝐅_{q^r}^×$. On a $𝐅_{q^r}=𝐅_q(x)$ :
l'élément $x$ est \emph{primitif}. En particulier, son
polynôme minimal sur $𝐅_q$ est de degré $r$ ;
il est irréductible et unitaire.
Ceci fournit une nouvelle démonstration de \ref{existence-polynome-irreductible-tout-degre-corps-finis}.
\end{remarque2}

\begin{démo}
Soient $K$ un corps et $G⊆K^×$ un sous-groupe fini.  Pour tout entier
$n$, l'ensemble $G[n]$ des éléments de $G$ d'ordre divisant $n$ est de
cardinal au plus $n$ car il est inclus dans l'ensemble des racines
dans $K$ du polynôme $X^n-1$.  La conclusion résulte donc du lemme
suivant.
\end{démo}

\begin{lemme2}\label{lemme-detection-groupes-cycliques}
Soit $G$ un groupe fini non nécessairement abélien d'ordre $n$ tel que
pour tout $d$ divisant $n$ on ait
\[\# G[d]≤d\]
en notant $G[d]$ l'ensemble des éléments d'ordre divisant $d$.
Alors $G$ est cyclique.
\end{lemme2}

\begin{démo}
Pour tout $d$ divisant $n$, notons $X_d$ l'ensemble des éléments
d'ordre exactement $d$.  On souhaite montrer que $X_n$ est non vide.
Commençons par montrer que si un $X_d$ est non vide, il est d'ordre
$φ(d)$.  En effet, si $x∈X_d$, l'ensemble à $d$ éléments
$\{1,x,\dots,x^{d-1}\}$ est inclus dans — donc égal à — $G[d]$.  Pour
un tel $d$, $G[d]$ est cyclique d'ordre $d$ et $X_d$ est l'ensemble de
ses générateurs, donc de cardinal $φ(d)$.  Il résulte de la formule
$∑_{d|n} φ(d)=n$ et de l'égalité $G=∐_{d|n} X_d$ (le symbole $\coprod$
désignant la réunion disjointe) que chaque $X_d$ est non vide. En
particulier c'est le cas de $X_n$.
\end{démo}

\begin{definition2}\label{element-primitif-corps-fini}
Un élément $x \in \FF_q^\times$ qui engendre le groupe multiplicatif
$\FF_q^\times$ est dit \emph{primitif}.
\end{definition2}

Le théorème \ref{cyclicite-groupe-multiplicatif-corps} affirme donc
qu'il existe dans (le groupe multiplicatif de) tout corps fini $\FF_q$
des éléments primitifs, et leur nombre est alors $\varphi(q-1)$
(nombre de générateurs d'un groupe cyclique d'ordre $q-1$), où
$\varphi$ désigne la fonction indicatrice d'Euler.  Plus généralement,
le nombre d'éléments d'ordre exactement $d$ dans $\FF_q^\times$ est
$\varphi(d)$ si $d|(q-1)$ et $0$ sinon (comparer avec la démonstration
du lemme \ref{lemme-detection-groupes-cycliques}).

\begin{remarques2}\label{elements-et-polynomes-primitifs}
Si $x \in \FF_{q^r}^\times$ est primitif, alors tout élément conjugué
à $x$ sur $\FF_q$ (cf. \ref{elements-conjugues-corps-finis} et les
remarques qui suivent) est encore primitif (en effet, l'ordre
multiplicatif d'un élément est préservé par l'automorphisme de
corps $\Frob_q \colon z \mapsto z^q$).  Par ailleurs, le degré de $x$
sur $\FF_q$ est alors exactement $r$ (et non un diviseur strict $s$
de $r$) : en effet, si on avait $x \in \FF_{q^s}$ avec $s<r$ alors
toutes les puissances de $x$ appartiendraient à $\FF_{q^s}$,
contredisant l'hypothèse que $x$ soit primitif.

Il est donc raisonnable d'appeler aussi primitif le polynôme minimal
commun sur $\FF_q$ de $x$ et de ses conjugués.  Autrement dit, un
polynôme primitif sur $\FF_q$ est un polynôme irréductible de
degré $r$ sur $\FF_q$ dont les racines dans $\FF_{q^r}$ sont
primitives.

Puisqu'il existe $\varphi(q^r-1)$ éléments primitifs dans $\FF_{q^r}$
et que la classe de conjugaison de chacun comporte exactement $r$
éléments et définit un unique polynôme primitif unitaire, on en déduit
qu'il existe $\frac{1}{r}\varphi(q^r-1)$ polynômes primitifs unitaires
de degré $r$ sur $\FF_q$.  Ce résultat, à comparer
avec \ref{denombrement-polynomes-irreductibles-corps-finis}, fournit
une nouvelle démonstration du fait qu'il existe des polynômes
irréductibles de degré arbitraire sur un corps fini (et qu'il existe
dans $\FF_{q^r}$ des éléments de degré $r$ sur $\FF_q$).

Signalons la conjecture d'Artin : si $ℓ$ est un nombre premier,
il existe une infinité de nombres premiers $p$ tels
que $ℓ$ soit primitif modulo $p$, c'est-à-dire tel que l'image 
de $ℓ$ dans $𝐅_p$ soit un élément primitif. \XXX
%cf. p. ex. http://www.mast.queensu.ca/~murty/mi.dvi
\end{remarques2}

\begin{proposition2}\label{2-primitif-mod-p}
Si $p$ un nombre premier de la forme
$4ℓ+1$ où $ℓ$ est un nombre premier, alors $2$ est primitif modulo
$p$.
\end{proposition2}

Cette proposition s'applique par exemple à $p=13,29$ ou $53$.

\begin{démo}
Un nombre $a$ est primitif modulo $p$ si pour tout
premier $p'$ tel que $p$ soit congru à $1$ modulo $p'$, 
$a^{(p-1)/p'}$ n'est pas congru à $1$ modulo $p$. 
Sous l'hypothèse de la proposition, $p-1$ a deux diviseurs
premiers : $2$ et $ℓ$. Puisque $ℓ$ est impair,
$4ℓ+1$ congru à $5$ modulo $8$, de sorte que
(\ref{formule-complementaire}) $2^{(p-1)/2}$ est congru à $-1$
modulo $p$. Enfin, $2^{(p-1)/ℓ}=2^4≡1$ modulo $p$ entraîne $p=3$ ou $5$.
\end{démo}

\begin{remarque2}
On ne sait pas s'il existe une infinité de nombres premiers
de la forme $(p-1)/4$. Par contre, la méthode dite du « crible »
permet de montrer qu'il existe une infinité de premiers $p$
tels que $(p-1)/4$ soit un produit de deux nombres premiers
plus grands que $p^θ$ où $θ$ est une constante strictement supérieure
à $⅓$. On peut en déduire (Heath-Brown) que l'un des trois entiers $2$, $3$ et $5$
est primitif pour une infinité de nombres premiers.
\end{remarque2}

\begin{exemples2}\label{primitifs-sur-f16}
\begin{itemize}
\item Le polynôme irréductible $h = X^4+X+1 \in \FF_2[X]$ est primitif
(sur $\FF_2$), c'est-à-dire qu'une quelconque de ses racines engendre
$\FF_{16}^\times$.  Pour se convaincre à la fois du fait qu'il est
irréductible et qu'il est primitif, on peut par exemple calculer les
puissances successives de la classe $x$ de $X$ modulo $h$, soit
$x^0=1$, $x^1=x$, $x^2$, $x^3$, $x^4=x+1$, $x^5=x^2+x$, $x^6=x^3+x^2$,
$x^7=x^3+x+1$, $x^8=x^2+1$, $x^9=x^3+x$, $x^{10}=x^2+x+1$,
$x^{11}=x^3+x^2+x$, $x^{12}=x^3+x^2+x+1$, $x^{13}=x^3+x^2+1$,
$x^{14}=x^3+1$ et $x^{15}=1$ : le fait qu'on ait obtenu un groupe
cyclique à $15$ éléments, c'est-à-dire tous les éléments non nuls de
$\FF_2[X]/(h)$, montre d'une part que l'ensemble des éléments non nuls
de $\FF_2[X]/(h)$ est un groupe (donc que $\FF_2[X]/(h)$ est un corps,
c'est-à-dire que $h$ est irréductible) et d'autre part que $x$ y est
primitif, c'est-à-dire que $h$ est primitif.
\item Le polynôme irréductible $h = X^4+X^3+X^2+X+1 \in \FF_2[X]$,
bien qu'irréductible, n'est pas primitif.  En effet, on a $X^5 \equiv
X \pmod{h}$, c'est-à-dire que la classe $x$ de $X$ dans $\FF_2[X]/(h)$
est d'ordre $5$, et cette classe n'engendre donc pas
$\FF_{16}^\times$.
\end{itemize}
\end{exemples2}

Ces exemples ont notamment pour but de souligner le fait que tous les
polynômes irréductibles ne sont pas nécessairement primitifs ou que,
de façon équivalente, le fait qu'un élément $x \in \FF_{q^r}$ soit de
degré $r$ sur $\FF_q$ ne suffit pas à entraîner qu'il soit primitif.
(De fait, c'était déjà clair sur les dénombrements qu'on a obtenus :
dans $\FF_{16}$ il y a $16-4 = 12$ éléments de degré $4$ sur $\FF_2$,
dont seulement $\varphi(15) = 8$ sont primitifs, c'est-à-dire qu'il y
a parmi les polynômes unitaires de degré $4$ sur $\FF_2$ un total de
$\frac{12}{4} = 3$ polynômes irréductibles dont $\frac{8}{4} = 2$ sont
primitifs.)

\begin{lemme2}\label{somme-x-s-dans-f-q}
Si $s$ est un entier naturel, alors $\sum_{x\in\FF_q} x^s$ vaut $-1$
si $s$ est non-nul \emph{et} multiple de $q-1$, et $0$ sinon (on fait
la convention $0^0 = 1$).
\end{lemme2}
\begin{proof}
Si $s=0$, la somme $\sum_{x\in\FF_q} x^s = \sum_{x\in\FF_q} 1$
vaut $q$, c'est-à-dire $0$ dans $\FF_q$.  Supposons maintenant $s>0$ :
alors $\sum_{x\in\FF_q} x^s = \sum_{x\in\FF_q^\times} x^s$, et en
appelant $g$ un élément primitif de $\FF_q$, cette somme s'écrit
encore $\sum_{i=0}^{q-2} g^{si}$.  Si $g^s = 1$, ce qui se produit
exactement lorsque $s$ est multiple de $q-1$, la somme vaut $q-1$,
c'est-à-dire $-1$ dans $\FF_q$.  Sinon, on a $\sum_{i=0}^{q-2} g^{si}
= \frac{g^{s(q-1)}-1}{g^s-1} = 0$.
\end{proof}

\subsection{Polynômes cyclotomiques et corps finis}

\subsubsection{} On rappelle que les polynômes cyclotomiques
$\Phi_n \in \ZZ[X]$ sont les uniques polynômes unitaires à
coefficients rationnels (et en fait, entiers) vérifiant pour tout $n$
la relation $X^n-1 = \prod_{d|n} \Phi_d(X)$ (le produit étant pris sur
tous les $d$ divisant $n$).  On peut aussi écrire $\Phi_n(X)
= \prod_\zeta (X-\zeta)$ pour $\zeta$ parcourant l'ensemble des
racines primitives $n$-ièmes de l'unité dans une extension quelconque
de $\QQ$ les contenant.  Les $\Phi_n$ sont irréductibles dans $\ZZ[X]$
(et deux à deux distincts, donc deux à deux premiers entre eux), et le
degré de $\Phi_n$ est $\varphi(n)$.  La formule $\Phi_n(X)
= \prod_\zeta (X-\zeta)$ pour $\zeta$ parcourant l'ensemble des
racines primitives $n$-ièmes de l'unité est encore valable dans
n'importe quel corps, de caractéristique ne divisant pas $n$, où il
existe une — et donc $\varphi(n)$ — racine primitive $n$-ième de
l'unité.

Si $q$ et $n$ sont premiers entre eux où $q$ est une puissance d'un
nombre premier $p$, considérons un $r$ tel que $n|(q^r-1)$
(c'est-à-dire $q^r \equiv 1 \pmod{n}$ ; un tel $r$ existe évidemment :
par exemple l'ordre multiplicatif de $q$ modulo $n$ convient) ; dans
ces conditions, si $\xi$ est un élément primitif de $\FF_{q^r}$, il
est facile de voir que $\zeta = \xi^{(q^r-1)/n}$ est d'ordre
multiplicatif exactement $n$ dans $\FF_{q^r}$, c'est-à-dire, est une
racine primitive $n$-ième de l'unité.  Dans ces conditions (lorsque
$n|(q^r-1)$), on a encore $\Phi_n(X) = \prod_\zeta (X-\zeta)$ dans
$\FF_{q^r}$, où $\zeta$ parcourt les racines primitives $n$-ièmes de
l'unité dans $\FF_{q^r}$, c'est-à-dire les $\varphi(n)$ éléments
d'ordre exactement $n$ dans $\FF_{q^r}^\times$.  En particulier, les
$\Phi_n$ pour $n$ premier avec $q$ sont encore deux à deux premiers
entre eux dans $\FF_q[X]$.

On a, de façon analogue à \ref{factorisation-x-q-r-x} :
\begin{proposition2}\label{factorisation-phi-q-r-1}
La décomposition en facteurs irréductibles du polynôme
$\Phi_{q^r-1}(X)$ dans $\FF_q[X]$ est donnée comme le produit de tous
les polynômes unitaires primitifs de $\FF_q[X]$ de degré $r$ (au
nombre de $\frac{1}{r}\varphi(q^r-1)$,
cf. \ref{elements-et-polynomes-primitifs}), chacun apparaissant avec
multiplicité $1$.
\end{proposition2}
\begin{proof}
D'après ce qui a été dit, $\Phi_{q^r-1}$ est scindé sur $\FF_{q^r}$ et
ses racines sont exactement les éléments primitifs de $\FF_{q^r}$
(chacune avec multiplicité $1$) ; et sur $\FF_q$ on a vu que les
polynômes minimaux de ces éléments primitifs de $\FF_{q^r}$ sont les
polynômes unitaires primitifs de degré $r$ sur $\FF_q$.
\end{proof}

\begin{exemple2}
Dans $\FF_2$, le polynôme $\Phi_{15}(X) = X^8 - X^7 + X^5 - X^4 + X^3
- X + 1 \in \ZZ[X]$ se factorise comme $(X^4 + X + 1)\penalty-100 (X^4
+ X^3 + 1)$ : ces deux facteurs sont les $\frac{1}{4} \varphi(15) = 2$
polynômes primitifs de degré $4$ sur $\FF_2$.  (Comparer
avec \ref{primitifs-sur-f16}.)
\end{exemple2}

Plus généralement :
\begin{proposition2}\label{factorisation-phi-n}
Soit $n$ un entier naturel premier avec $q$ (où $q$ est une puissance
d'un nombre premier).  Alors la décomposition en facteurs
irréductibles du polynôme $\Phi_n(X)$ dans $\FF_q[X]$ est formée de
$\frac{1}{r}\varphi(n)$ facteurs irréductibles chacun de degré $r$, où
$r$ est l'ordre multiplicatif de $q$ modulo $n$ (c'est-à-dire le plus
petit entier naturel tel que $q^r \equiv 1 \pmod{n}$).

En particulier, (toujours sous l'hypothèse que $n$ et $q$ sont
premiers entre eux, cf. \ref{irreductibilite-phi-n-complement})
$\Phi_n(X)$ est irréductible dans $\FF_q[X]$ exactement lorsque $q$
engendre le groupe multiplicatif $(\ZZ/n\ZZ)^\times$.
\end{proposition2}
\begin{proof}
Soit $r$ l'ordre multiplicatif de $q$ modulo $n$.  Il existe alors
dans $\FF_{q^r}$ une racine primitive $n$-ième de l'unité $\zeta$ :
ansi, $\Phi_n$ est scindé sur $\FF_{q^r}$ et on peut écrire $\Phi_n(X)
= \prod (X-\zeta^j)$ pour $j$ parcourant (les $\varphi(n)$ éléments
de) $(\ZZ/n\ZZ)^\times$.  Le degré de $\zeta^j$ sur $\FF_q$ (pour
$j \in (\ZZ/n\ZZ)^\times)$) est le plus petit $i$ tel que
$\zeta^{j\,q^i} = \zeta^j$, c'est-à-dire tel que $j q^i \equiv
j \pmod{n}$, ce qui équivaut à $q^i \equiv 1 \pmod{n}$ (puisque $j$
est inversible modulo $n$), c'est donc exactement $r$.  Ainsi,
$\Phi_n$ est scindé sur $\FF_{q^r}$, et les polynômes minimaux sur
$\FF_q$ de ses racines sur $\FF_{q^r}$ sont chacun de degré $r$ : ceci
prouve que $\Phi_n$ s'écrit sur $\FF_q$ comme produit de
$\frac{1}{r}\varphi(n)$ polynômes irréductibles de degré $r$.

La dernière affirmation signifie simplement que $q$ engendre le groupe
multiplicatif $(\ZZ/n\ZZ)^\times$ exactement lorsque son ordre
multiplicatif modulo $n$ est $\varphi(n)$.
\end{proof}

On peut dire (cf. les remarques
suivant \ref{racines-polynome-minimal-corps-fini}) que le corps de
décomposition de $\Phi_n$ sur $\FF_q$ (toujours sous l'hypothèse que
$n$ n'est pas multiple de $p$) est $\FF_{q^r}$ où $r$ est l'ordre
multiplicatif de $q$ modulo $n$.  Ce corps de décomposition, qui est
le corps de rupture d'un quelconque des facteurs irréductibles (tous
de degré $r$) de $\Phi_n$ sur $\FF_q$, peut se noter $\FF_q(\zeta_n)$,
en désignant par $\zeta_n$ une racine primitive $n$-ième de l'unité
dans $\FF_{q^r}$.  Il faut cependant se garder de croire que les
différents choix possibles de $\zeta_n$ soient interchangeables (plus
précisément, qu'ils seraient conjugués sous l'action de $\Frob_q$) :
même si le corps $\FF_q(\zeta_n) = \FF_{q^r}$ engendré par $\zeta_n$
est le même quel que soit le choix effectué, le polynôme minimal de
$\zeta_n$ sur $\FF_q$, lui, ne l'est pas (c'est justement l'un
quelconque des $\frac{1}{r} \varphi(n)$ facteurs irréductibles
de $\Phi_n$) ; ceci diffère de la situation sur $\QQ$ où toutes les
racines primitives $n$-ièmes de l'unité sont interchangeables
(précisément, on dira qu'elles sont conjuguées par le groupe de
Galois), non seulement elles engendrent le même corps $\QQ(\zeta_n)$
mais aussi elles ont le même polynôme minimal sur $\QQ$, qui est
justement $\Phi_n$.

\begin{corollaire2}
Le polynôme $Φ_ℓ$ a une racine dans $𝐅_p$ si et seulement si
$p ≡ 1 \mod ℓ$.
\end{corollaire2}

\begin{proposition2}
Soit $P ∈ 𝐙[X]$ un polynôme non constant. Il existe une infinité
de nombres premiers $p$ tels que $P$ ait une racine dans $𝐅_p$.
\end{proposition2}

% Variante (plus dure) : scindé
% Čebotarev pour l'absence de racine si P irréductible.

\begin{démo}
C'est une variante de la méthode d'Euclide pour montrer
qu'il existe une infinité de nombres premiers. Supposons
que les $P(n)$, $n ∈ 𝐍$ n'aient qu'un nombre fini de
diviseurs premiers $ℓ₁,ℓ₂,…,ℓ_r$. Pour chaque $n ∈ 𝐍$,
l'entier $P(n ℓ₁ℓ₂\cdots ℓ_r)$ est congru à $P(0)$
modulo chaque $ℓ_i$. Si $P(0)=±1$, il en résulte
que $P(nℓ₁ℓ₂\cdots ℓ_r)$ est premier à
chacun des $ℓ_i$. Or, si $n$ est grand, $P(n ℓ₁ℓ₂\cdots ℓ_r)$
est grand (en valeur absolue) donc a un diviseur premier.
Absurde. Dans le cas général, on observe que si $a=P(0)$,
on a $P(aX)=aQ(X)$ où $Q(0)=1$. Si $Q$ a une racine
modulo un nombre premier $p$, il en est de même de $P$.
\end{démo}

\begin{corollaire2}
\label{Dirichlet faible}
Soit $ℓ$ un nombre premier. Il existe une infinité
de nombres premiers $p$ congrus à $1$ modulo $ℓ$.
\end{corollaire2}

\begin{proposition2}
Soit $h$ un polynôme irréductible unitaire sur $\FF_q$, autre que $X$.
Alors il existe un unique $n$ premier à $q$ tel que $h$
divise $\Phi_n$ : ce $n$ divise $q^r-1$ où $r$ est le degré de $h$.
Il s'agit exactement de l'ordre multiplicatif d'une racine
(quelconque) de $h$ dans $\FF_{q^r}$.
\end{proposition2}
\begin{proof}
On a $X^{q^r-1}-1 = \prod_{n|(q^r-1)} \Phi_n(X)$ par définition
des $\Phi_n$, donc $X^{q^r}-X = X\,\prod_{n|(q^r-1)} \Phi_n(X)$.
D'après \ref{factorisation-x-q-r-x}, le polynôme irréductible $h$
divise ce produit : il doit donc diviser un des $\Phi_n$ avec
$n|(q^r-1)$.  Comme les $\Phi_n$ pour $n$ premier à $q$ sont premiers
entre eux, il ne peut en diviser un autre.  Enfin, dire qu'une racine
de $h$ (dans $\FF_{q^r}$) est racine de $\Phi_n$ signifie précisément
que son ordre multiplicatif est exactement $n$.
\end{proof}

\begin{exemples2}
\begin{itemize}
\item Le polynôme $\Phi_5(X) = X^4+X^3+X^2+X+1 \in \ZZ[X]$ demeure
irréductible dans $\FF_2$ car $2$ engendre $(\ZZ/5\ZZ)^\times$.  Il
n'est, naturellement, pas primitif (puisque ses racines dans
$\FF_{2^4}$ sont d'ordre $5$ et non $15$).  On retrouve-là un exemple
déjà donné en \ref{primitifs-sur-f16}.
\item Le polynôme $\Phi_{9}(X) = X^6 + X^3 + 1 \in \ZZ[X]$
demeure irréductible dans $\FF_2$ car $2$
engendre $(\ZZ/9\ZZ)^\times$.  Il n'est, naturellement, pas primitif
(puisque ses racines dans $\FF_{2^6}$ sont d'ordre $9$ et non $63$).
\item Le polynôme $\Phi_{17}(X) = X^{16} + X^{15} + \cdots + X + 1 \in
\ZZ[X]$ se factorise dans $\FF_2$ comme produit de deux facteurs de
degré $8$ puisque $2$ est d'ordre $8$ dans $(\ZZ/17\ZZ)^\times$ (on a
$2^8 \equiv 1 \pmod{17}$).  À savoir : $\Phi_{17}(X) =
(X^8+X^5+X^4+X^3+1)\penalty-100 (X^8+X^7+X^6+X^4+X^2+X+1)$.  Aucun de
ces facteurs, naturellement, n'est primitif (puisque leurs racines
sont toutes d'ordre $17$ et non $2^8-1 = 255$).
\end{itemize}
\end{exemples2}

\subsubsection{} Lorsque $n$ n'est plus supposé premier avec $p$
(i.e., avec $q$), les choses sont très différentes, et le polynôme
$\Phi_n$ n'est généralement plus séparable sur $\FF_q$ comme on va le
voir.  Par exemple, il est facile de se convaincre par récurrence
sur $k$ que $\Phi_{p^k}(X) = (X-1)^{(p-1)p^{k-1}}$ sur $\FF_p$ (ou
sur $\FF_q$, donc).

\begin{proposition2}\label{factorisation-phi-n-inseparable}
Si $n = p^k m$ où $m$ n'est pas multiple de $p$, alors $\Phi_n(X)
= \Phi_m(X)^{(p-1)p^{k-1}}$ dans $\FF_p[X]$ (donc dans $\FF_q[X]$).
En particulier, sauf éventuellement dans le cas où $p=2$ et $k=1$, le
polynôme $\Phi_n(X)$ n'est ni séparable ni irréductible
sur $\FF_q[X]$.
\end{proposition2}
\begin{proof}
On procède par récurrence sur $k$ et, à $k$ fixé, par récurrence
sur $m$.  On a d'une part $X^{p^k m} - 1 = (X^m-1)^{p^k}
= \prod_{d|m}\Phi_d(X)^{p^k}$ et d'autre part $X^{p^k m} - 1
= \prod_{d|p^k m} \Phi_d(X) = \prod_{d|m}
(\Phi_d(X)\, \prod_{\ell=1}^k \Phi_{p^\ell d}(X))$.  Les hypothèses
des récurrences permettent de remplacer chaque $\Phi_{p^\ell d}(X)$
par $\Phi_d(X)^{(p-1)p^{\ell-1}}$ sauf le dernier
($\ell=k$ et $d=m$) : pour montrer qu'on a bien aussi $\Phi_{p^k m}(X)
= \Phi_m(X)^{(p-1)p^{k-1}}$, il suffit donc de montrer que
$\prod_{d|m}\Phi_d(X)^{p^k} = \prod_{d|m}
(\Phi_d(X)\, \prod_{\ell=1}^k \Phi_d(X)^{(p-1)p^{\ell-1}})$.  Or cela
résulte du fait que $1 + \sum_{\ell=1}^k (p-1)p^{\ell-1} = p^k$.
\end{proof}

\begin{proposition2}\label{irreductibilite-phi-n-complement}
Si $q$ est une puissance d'un nombre premier $p$ et $n$ est un entier
naturel, le polynôme cyclotomique $\Phi_n$ est irréductible
dans $\FF_q$ si et seulement si :
\begin{itemize}
\item le nombre $q$ engendre le groupe multiplicatif
$(\ZZ/n\ZZ)^\times$ (ce qui sous-entend que $q$ est premier
avec $n$), \emph{ou bien}
\item on a $n=2m$ avec $m$ impair, et $p=2$, et $q$ engendre le groupe
multiplicatif $(\ZZ/m\ZZ)^\times$.
\end{itemize}
\end{proposition2}
\begin{proof}
D'après \ref{factorisation-phi-n-inseparable}, on sait que si $n$ est
multiple de $p$ avec $p>2$, ou que $n$ est multiple de $4$ lorsque
$p=2$, alors $\Phi_n$ n'est pas irréductible modulo $p$ (donc
dans $\FF_q$).  Lorsque $n$ est premier avec $q$, la
proposition \ref{factorisation-phi-n} donne le premier cas.  Reste
enfin le cas où $n = 2m$ avec $m$ impair et $p=2$ : dans ce cas
$\Phi_n(X) = \Phi_m(X)$ modulo $2$, donc la
proposition \ref{factorisation-phi-n} donne de nouveau le résultat.
\end{proof}

\begin{exemples2}
\begin{itemize}
\item Modulo $2$, les polynômes $\Phi_{2m}(X)$ et $\Phi_m(X)$
(pour $m$ impair) sont toujours égaux.  (En fait, dans $\ZZ[X]$, on a
$\Phi_{2m}(X) = \Phi_m(-X)$ pour $m$ impair, puisque les racines
primitives $2m$-ièmes de l'unité sont les $-\zeta$ avec $\zeta$ racine
primitive $m$-ième de l'unité.)  Ensuite, toujours modulo $2$ et avec
$m$ impair, on a $\Phi_{4m}(X) = \Phi_m(X)^2$.
\item Le polynôme $\Phi_8(X) = X^4 + 1$, bien qu'irréductible dans
$\ZZ[X]$ ou $\QQ[X]$, n'est irréductible dans \emph{aucun}
$\FF_q[X]$ : en effet, en caractéristique $p=2$, on a $\Phi_8 =
(X-1)^4$, et en caractéristique $p\neq 2$, on a vu
en \ref{factorisation-phi-n} que pour que $\Phi_8$ soit irréductible
dans $\FF_q$ il faut (et il suffit) que $q$ engendre
$(\ZZ/8\ZZ)^\times$, or ce dernier n'est pas cyclique (il a quatre
éléments tous d'ordre divisant $2$) : donc $\Phi_8$ se scinde (en
quatre facteurs de degré $1$) pour $q \equiv 1 \pmod{8}$, et se
factorise en deux facteurs de degré $2$ pour tout autre $q$
impair. (\XXX Peut-on être un chouïa plus explicite sur la
factorisation de $\Phi_8$ modulo $p$ ?  Par ailleurs, cette remarque
fait doublon avec l'exercice \ref{exercice-Phi8} ajouté après.)
\item Si $n$ est multiple de deux nombres premiers impairs distincts
$\ell_1,\ell_2$, alors, de même, $\Phi_n$, bien qu'irréductible dans
$\ZZ[X]$ ou $\QQ[X]$, n'est irréductible dans aucun $\FF_q$ : en
effet, en caractéristique $\ell_1$ ou $\ell_2$, le polynôme $\Phi_n$
n'est pas irréductible (il est une puissance parfaite) ; et en toute
autre caractéristique, on sait que pour que $\Phi_n$ soit irréductible
dans $\FF_q$ il faut (et il suffit) que $q$ engendre
$(\ZZ/n\ZZ)^\times$, or ce dernier n'est pas cyclique car le théorème
chinois assure qu'on peut l'écrire comme produit de deux groupes
d'ordres pairs (par exemple $(\ZZ/n\ZZ)^\times \cong
(\ZZ/n_1\ZZ)^\times \times (\ZZ/n_2\ZZ)^\times$ où $n_1 = \ell_1^k$ et
$n_2$ est premier avec $\ell_1$).
\end{itemize}
\end{exemples2}

\subsubsection{Éléments primitifs modulo $n$} On dit qu'un élément
$g \in \ZZ/n\ZZ$ est \emph{primitif} modulo $n$ lorsque
$g$ est premier avec $n$ (c'est-à-dire $g \in
(\ZZ/n\ZZ)^\times$) et que $g$ engendre le groupe
multiplicatif $(\ZZ/n\ZZ)^\times$.  (Lorsque $n$ est
premier, cette terminologie est cohérente avec celle introduite
en \ref{element-primitif-corps-fini}.)  Autrement dit, dire qu'il
existe des éléments primitifs modulo $n$ signifie que
$(\ZZ/n\ZZ)^\times$ est cyclique, et lorsqu'il en
existe, il en existe exactement $\varphi(\varphi(n))$.

On rappelle ou admet le résultat suivant :
\begin{proposition2}
\begin{itemize}
\item Si $p$ est un nombre premier impair, alors
  $(\ZZ/p\ZZ)^\times$ est cyclique, i.e., il existe des éléments
  primitifs modulo $p$.  (Il en existe exactement $\varphi(p-1)$.)
\item Si $p$ est un nombre premier impair et $k\geq 2$, alors
  $(\ZZ/p^k\ZZ)^\times$ est cyclique, i.e., il existe des éléments
  primitifs modulo $p^k$.  (Il en existe exactement
  $\varphi(p^{k-1}(p-1))$.)  Plus précisément : $g$ est primitif
  modulo $p^k$ si et seulement si il l'est modulo $p^2$.
\item Si $p=2$ et $1\leq k\leq 2$, alors
  $(\ZZ/2^k\ZZ)^\times$ est (trivialement) cyclique.
\item Si $p=2$ et $k \geq 3$, alors
  $(\ZZ/2^k\ZZ)^\times$ \emph{n'est pas} cyclique : il est produit
  d'un groupe cyclique d'ordre $2$ engendré par $-1$ et d'un groupe
  cyclique d'ordre $2^{k-2}$ engendré par $5$ (l'ordre maximal
  possible d'un élément est $2^{k-2}$).
\item Si $n$ n'est pas de la forme $2$, $4$, $p^k$ ou $2 p^k$
  avec $p$ premier impair, alors $(\ZZ/n\ZZ)^\times$ \emph{n'est pas}
  cyclique : il peut s'écrire comme produit de deux groupes d'ordre
  pair.
\end{itemize}
\end{proposition2}

Par ailleurs, on admet provisoirement le théorème suivant, qui sera
démontré en \XXX :
\begin{theoreme2}[Dirichlet]
Si $b \in (\ZZ/n\ZZ)^\times$, alors il existe un nombre premier $p$
tel que $p \equiv b \pmod{n}$.
\end{theoreme2}

On peut alors remarquer :
\begin{proposition2}
\label{existence-p-Phin-irreductible-mod-p}
Pour tout entier naturel $n$, il existe un nombre premier $p$ (ou, de
façon équivalente, une puissance $q$ d'un nombre premier) tel que
$\Phi_n$ soit irréductible dans $\FF_p$ (resp., dans $\FF_q$) si, et
seulement si, $n$ vaut $2$, $4$, $\ell^k$ ou $2\ell^k$ pour $\ell$
premier impair.
\end{proposition2}

(Le cas $n=8$ a été considéré dans l'exercice \ref{exercice-Phi8}.)

\begin{proof}
Démontrons le « si » : si $n$ est d'une des formes indiquées, alors
$(\ZZ/n\ZZ)^\times$ est cyclique, donc il existe un élément $g \in
(\ZZ/n\ZZ)^\times$ qui soit primitif, et d'après le théorème de
Dirichlet, on peut supposer que $g \equiv p \pmod{n}$ avec $p$
premier, et d'après \ref{factorisation-phi-n} le polynôme $\Phi_n$ est
irréductible modulo $p$.

Montrons maintenant le « seulement si » : si $\Phi_n$ est irréductible
dans $\FF_q$, on sait d'après \ref{irreductibilite-phi-n-complement}
que soit $q$ est premier avec $n$ et primitif modulo $n$ soit $n=2m$
avec $m$ impair et $q = 2^r$ est primitif modulo $m$.  Dans le premier
cas, $n$ vaut $2$, $4$, $\ell^k$ ou $2\ell^k$ avec $\ell$ premier
impair, et dans le second, $m$ vaut $\ell^k$ avec $\ell$ premier
impair, donc $n=2m$ est bien de la forme $2\ell^k$ avec $\ell$ premier
impair.
\end{proof}

\subsection{Trace et norme}

On renvoie à \refext{Alg}{trace-et-norme} pour les généralités sur la
trace et la norme dans une algèbre quelconque sur un corps.  On se
préoccupera ici d'une extension $\FF_{q^r}\bo \FF_q$ de corps finis :
la \emph{trace} $\Tr_{\FF_{q^r}\bo\FF_q}(x)$,
la \emph{norme} $\N_{\FF_{q^r}\bo\FF_q}(x)$, et le \emph{polynôme
caractéristique} $\chi_{\FF_{q^r}\bo\FF_q}(x,X)$ d'un élément
$x \in \FF_{q^r}$ sont respectivement la trace, la norme, et le
polynôme caractéristique de l'application $\FF_q$-linéaire $z \mapsto
xz$ de multiplication par $x$ sur $\FF_{q^r}$, ce dernier étant vu
comme un $\FF_q$-espace vectoriel de dimension $r$.

\begin{proposition2}\label{trace-et-norme-corps-finis}
Soit $x \in \FF_{q^r}$ : alors on a
\[\chi_{\FF_{q^r}\bo\FF_q}(x,X) = \prod_{i=0}^{r-1} (X-\Frob_q^i(x))\]
et en particulier
\[\Tr_{\FF_{q^r}\bo\FF_q}(x) = \sum_{i=0}^{r-1} \Frob_q^i(x)\]
\[\N_{\FF_{q^r}\bo\FF_q}(x) = \prod_{i=0}^{r-1} \Frob_q^i(x) = x^{(q^r-1)/(q-1)}\]
\end{proposition2}
\begin{proof}
Considérons d'abord le cas où $x$ engendre $\FF_{q^r}$ sur $\FF_q$,
c'est-à-dire que son degré est $r$.  Alors on a vu
en \ref{elements-conjugues-corps-finis} que les conjugués de $x$ sont
justement les $\Frob_q^i(x)$ pour $i\in\{0,\ldots,r-1\}$, le polynôme
$\prod_{i=0}^{r-1} (X-\Frob_q^i(x))$ étant alors le polynôme minimal
de $x$.  Puisqu'il est de degré $r$, c'est aussi son polynôme
caractéristique, ce qui montre la première formule dans le cas
particulier considéré.

Dans le cas où $x$ est de degré $s<r$, on décompose l'extension
$\FF_{q^r}\bo\FF_q$ en deux extensions $\FF_q(x)\bo\FF_q$
(c'est-à-dire $\FF_{q^s}\bo\FF_q$) et $\FF_{q^r}\bo\FF_q(x)$, de
degrés respectifs $s$ et $r/s$.  On a
$\chi_{\FF_{q^r}\bo\FF_q(x)}(x,X) = (X-x)^{r/s}$.
D'après \refext{Alg}{composition-trace-norme}
et \refext{Alg}{Norme=pol-car}, on a $\chi_{\FF_{q^r}\bo\FF_q}(x,X)
= \N_{\FF_q(x)[X]\bo\FF_q[X]} (\chi_{\FF_{q^r}\bo\FF_q(x)}(x,X))
= \N_{\FF_q(x)[X]\bo\FF_q[X]}(X-x)^{r/s}
= \chi_{\FF_q(x)\bo\FF_q}(x,X)^{r/s}$.  Or d'après le cas déjà
démontré, $\chi_{\FF_q(x)\bo\FF_q}(x,X) = \prod_{i=0}^{s-1}
(X-\Frob_q^i(x))$ : on a donc $\chi_{\FF_{q^r}\bo\FF_q}(x,X)
= \prod_{i=0}^{s-1} (X-\Frob_q^i(x))^{s/r} = \prod_{i=0}^{r-1}
(X-\Frob_q^i(x))$ en se rappelant que $\Frob_q^s(x) = x^{q^s} = x$.
Ceci démontre la première formule en général.  Les autres formules
s'en déduisent immédiatement.
\end{proof}

\begin{proposition2}\label{surjectivite-trace-et-norme}
Soit $\FF_{q^r}\bo\FF_q$ une extension de corps finis.  Les
applications $\Tr_{\FF_{q^r}\bo\FF_q} \colon \FF_{q^r}\to\FF_q$ et
$\N_{\FF_{q^r}\bo\FF_q} \colon \FF_{q^r}\to\FF_q$ sont surjectives.
De plus, si $g \in \FF_{q^r}$ est primitif, alors
$\N_{\FF_{q^r}\bo\FF_q}(g) \in \FF_q$ est primitif.
\end{proposition2}
\begin{proof}
La trace $\Tr_{\FF_{q^r}\bo\FF_q} \colon \FF_{q^r}\to\FF_q$ étant
$\FF_q$-linéaire, il suffit pour montrer qu'elle est surjective de
montrer qu'elle n'est pas identiquement nulle.  Or en tant que
polynôme à coefficients dans $\FF_q$ (et évalué sur $\FF_{q^r}$), la
trace est donnée par $X + X^q + X^{q^2} + \cdots + X^{q^{r-1}}$ : ce
polynôme étant de degré $q^{r-1}$ (et non identiquement nul), il ne
peut pas s'annuler en tout point de $\FF_{q^r}$, ce qu'on voulait.

La norme $\N_{\FF_{q^r}\bo\FF_q} \colon \FF_{q^r}\to\FF_q$ est donnée
par $x \mapsto x^{(q^r-1)/(q-1)}$.  La valeur $0$ étant manifestement
atteinte, la norme est surjective lorsque tout élément de
$\FF_q^\times$ est atteint.  Or $\FF_{q^r}^\times$ est un groupe
cyclique d'ordre $q^r-1$ (\ref{cyclicite-groupe-multiplicatif-corps}),
et $\FF_q^\times$ est son unique sous-groupe d'ordre $q-1$ : si $g$
est un générateur de $\FF_{q^r}^\times$, alors
$\N_{\FF_{q^r}\bo\FF_q}(g) = g^{(q^r-1)/(q-1)}$ est d'ordre
exactement $q-1$, donc il engendre $\FF_q^\times$, ce qui montre à la
fois la surjectivité et le fait que l'élément annoncé est primitif.
\end{proof}

\subsection{Polynômes de Conway}

Le choix d'un polynôme $h$ irréductible de degré $r$ donné sur $\FF_p$
étant loin d'être unique
(cf. \ref{denombrement-polynomes-irreductibles-corps-finis}), même si
on demande qu'il soit primitif
(cf. \ref{elements-et-polynomes-primitifs}), la présentation de
$\FF_{p^r}$ comme $\FF_p[X]/(h)$ ne l'est pas plus.  Il est parfois
utile par exemple dans un logiciel de calcul formel devant manipuler
$\FF_{p^r}$, de fixer une fois pour toutes une présentation
particulière de chaque corps fini de façon à définir une notation
standard pour ses éléments.  On pourrait pour cela choisir
arbitrairement un polynôme unitaire irréductible de chaque degré sur
chaque $\FF_p$ (comme le plus petit lexicographiquement), mais il
s'avère souhaitable de faire des choix possédant certaites
compatibilités d'un $\FF_q$ à un autre : c'est ce que réalisent les
polynômes de Conway.

Introduisons d'abord une terminologie temporaire pour la condition de
compatibilité qui va nous occuper :

\begin{definition2}\label{familles-compatibles-polynomes-conway}
Soit $p$ un nombre premier.  On dit qu'une famille $h_1,\ldots,h_N$ de
polynômes de $\FF_p[X]$, avec $h_n$ unitaire de degré $n$,
est \emph{compatible au sens de Conway} lorsque :
\begin{itemize}
\item pour chaque $1\leq n\leq N$, le polynôme $h_n$ est primitif
(cf. \ref{elements-et-polynomes-primitifs}),
\item pour tout $m$ divisant $n$ entre $1$ et $N$, la norme
$\N_{\FF_{p^n}\bo\FF_{p^m}}(x) = x^{(p^n-1)/(p^m-1)}$ de $\FF_{p^n}$ à
$\FF_{p^m}$ d'une racine quelconque $x$ de $h_n$ dans $\FF_{p^n}$ est
une racine de $h_m$ (autrement dit, $h_n$ divise
$h_m(X^{(p^n-1)/(p^m-1)})$, cf. \ref{trace-et-norme-corps-finis}).
\end{itemize}
\end{definition2}

(Dans la deuxième condition, le choix de la racine $x$ de $h_n$ est
sans importance : dans tous les cas, le corps $\FF_p(x)$ est isomorphe
à $\FF_p[X]/(h_n)$, et dire que la norme $x^{(p^n-1)/(p^m-1)}$ de $x$
est racine de $h_m$ signifie que $h_m(X^{(p^n-1)/(p^m-1)}) \equiv
0 \pmod{h_n}$.)

\begin{proposition2}\label{existence-polynomes-conway}
Soit $p$ un nombre premier, et $h_1,\ldots,h_{n-1}$ une famille de
polynômes de $\FF_p[X]$, avec $h_i$ unitaire de degré $i$, compatible
au sens de Conway.  Alors il existe $h_n$ unitaire de degré $n$ tel
que $h_1,\ldots,h_n$ soit encore compatible au sens de Conway.
\end{proposition2}
\begin{proof}
Fixons une présentation quelconque de $\FF_{p^n}$.

Montrons dans un premier temps qu'on peut choisir, pour chaque $m$
allant de $1$ à $n-1$, une racine $x_m$ de $h_m$ dans $\FF_{p^n}$, de
façon à avoir la compatibilité suivante : si $\ell|m$ alors
$x_m^{(p^m-1)/(p^\ell-1)} = x_\ell$.  On définit les $x_m$ par
récurrence sur $m$.  Supposons les $x_\ell$ déjà choisis pour
$\ell<m$.  Si $z$ est une racine quelconque de $h_m$ dans $\FF_{p^n}$,
la condition de compatibilité des $h_m$ signifie que pour tout
$\ell|m$ on a $z^{(p^m-1)/(p^\ell-1)} = x_\ell^{p^{j_\ell}}$ pour un
certain $j_\ell \in \ZZ/\ell\ZZ$.  La compatibilité supposée sur
les $x_\ell$ (par récurrence) assure que si $k|\ell|m$ alors
$x_{k}^{p^{j_k}} = z^{(p^m-1)/(p^{k}-1)} = (z^{(p^m-1)/(p^\ell-1)})
^{(p^\ell-1)/(p^{k}-1)} = (x_\ell^{p^{j_\ell}})
^{(p^\ell-1)/(p^{k}-1)} = (x_\ell^{(p^\ell-1)/(p^{k}-1)})
^{p^{j_\ell}} = x_{k}^{p^{j_\ell}}$, donc (l'élément $x_k$ étant de
degré $k$ sur $\FF_p$) on a $j_\ell \equiv j_k \pmod{k}$.  Le théorème
chinois garantit alors qu'il existe $j \in \ZZ/m\ZZ$ tel que $j \equiv
j_\ell \pmod{\ell}$ pour tout $\ell|m$.  On pose $x_m = z^{p^{-j}}$ :
on a alors $x_m^{(p^m-1)/(p^\ell-1)} = x_\ell^{p^{-j} \cdot p^{j_\ell}}
= x_\ell$, comme souhaité.

Soit maintenant $g$ un élément primitif de $\FF_{p^n}$, de sorte que
$\FF_{p^n}^\times$ est isomorphe à $\ZZ/(p^n-1)\ZZ$ par $i \mapsto
g^i$.  Pour chaque $m$ divisant $n$, l'élément $g^{(p^n-1)/(p^m-1)}$
est primitif dans $\FF_{p^m}$ (cf. \ref{surjectivite-trace-et-norme}).
Écrivons $x_m = g^{i_m(p^n-1)/(p^m-1)}$ avec $i_m \in \ZZ/(p^m-1)\ZZ$,
et même $i_m$ inversible (c'est-à-dire premier avec $p^m-1$) puisque
$x_m$ est primitif dans $\FF_{p^m}$.  Si $\ell|m$ alors la
compatibilité $x_m^{(p^m-1)/(p^\ell-1)} = x_\ell$ obtenue au
paragraphe précédent signifie que $(g^{i_m(p^n-1)/(p^m-1)})
^{(p^m-1)/(p^\ell-1)} = g^{i_\ell(p^n-1)/(p^\ell-1)}$ donc $i_m \equiv
i_\ell \pmod{p^\ell-1}$.  Le théorème chinois (avec le fait que
$\pgcd(p^\ell-1, p^m-1) = p^{\pgcd(\ell,m)}-1$) garantit alors qu'il
existe $i \in \ZZ/(p^n-1)\ZZ$ inversible (c'est-à-dire premier avec
$p^n-1$) tel que $i \equiv i_m \pmod{p^m-1}$ pour tout $m|n$.  On
définit $x_n = g^i$ : alors $x_n$ est primitif car $i$ est inversible,
et $x_n^{(p^n-1)/(p^m-1)} = x_m$ pour tout $m|n$.  En appelant $h_n$
le polynôme minimal de $x_n$, le polynôme $h_n$ vérifie toutes les
compatibilités demandées.
\end{proof}

\begin{definition2}\label{definition-polynomes-conway}
Soit $p$ un nombre premier.  On introduit l'ordre total sur $\FF_p$
donné par $0 < 1 < 2 < \cdots < (p-1)$, et l'ordre total sur les
polynômes unitaires de degré $n$ de $\FF_p[X]$ (« ordre
lexicographique alterné ») donné par $X^n - a_1 X^{n-1} + \cdots +
(-1)^n a_n < X^n - b_1 X^{n-1} + \cdots + (-1)^n b_n$ si et seulement
si $a_i < b_i$ pour le plus petit $i$ tel que $a_i \neq b_i$.

On définit alors par récurrence sur l'entier naturel non nul $n$
le \emph{polynôme de Conway} de degré $n$ sur $\FF_p$ comme le plus
petit polynôme unitaire $h_n$ de degré $n$, pour l'ordre introduit
ci-dessus, tel que la famille $h_1,\ldots,h_n$ soit compatible au sens
de Conway (\ref{familles-compatibles-polynomes-conway}).

On appelle \emph{élément de Conway} de $\FF_{p^n}$ tout élément de ce
dernier qui est racine de $h_n$.
\end{definition2}

L'existence de $h_n$ est garantie par la
proposition \ref{existence-polynomes-conway}.  Le choix du polynôme le
plus petit pour l'ordre lexicographique alterné est simplement une
manière de fixer les choix effectués : la condition intéressante de
compatibilité est celle explicitée
en \ref{familles-compatibles-polynomes-conway}.  Un élément de Conway
est primitif (il y en a $n$ dans $\FF_{p^n}$, mais ils sont
conjugués), et sa norme à n'importe quel sous-corps est encore un
élément de Conway.

Le polynôme $h_1$ vaut $X - g$ où $g$ est le plus petit élément
primitif de $\ZZ/p\ZZ$ (pour l'ordre $0<1<\cdots<(p-1)$).  C'est pour
que la classe $x$ de $X$ dans $\FF_p[X]/(h_1)$ soit cet élément $g$
(et non son opposé) qu'on a fait la convention de signes particulière
de l'ordre lexicographique \emph{alterné}.

Le calcul algorithmique du polynôme de Conway $h_n$ (connaissant les
$h_m$ avec $m$ divisant $n$) peut se faire selon essentiellement deux
stratégies :
\begin{itemize}
\item énumérer les polynômes unitaires de degré $n$ dans l'ordre
lexicographique alterné jusqu'à trouver un polynôme primitif et
vérifiant la compatibilité demandée avec les $h_m$, ou bien
\item choisir une présentation quelconque de $\FF_{p^n}$, et dans
celle-ci, énumérer (au moyen d'un élément primitif de $\FF_{p^n}$) les
éléments dont la norme dans chaque $\FF_{p^m}$ pour $m|n$ est un
élément de Conway, et choisir celui dont le polynôme minimal est le
plus petit pour l'ordre lexicographique alterné.
\end{itemize}
La première stratégie applique directement la
définition \ref{familles-compatibles-polynomes-conway}, tandis que la
seconde fonctionne comme l'explique la preuve de la
proposition \ref{existence-polynomes-conway}.  La première est plus
appropriée quand $n$ est peu divisible, tandis que la seconde est plus
efficace si $n$ a beaucoup de diviseurs (donc que les conditions de
compatibilités sont fortes).

À titre d'exemple, le tableau suivant donne les quelques premiers
polynômes de Conway pour $p\leq 7$ :
\begin{center}
\begin{tabular}{|c|c|c|}
\hline
$p=2$&$p^n=2$&$h_1 = X + 1$\\
&$p^n=4$&$h_2 =  X^2 + X + 1$\\
&$p^n=8$&$h_3 =  X^3 + X + 1$\\
&$p^n=16$&$h_4 =  X^4 + X + 1$\\
&$p^n=32$&$h_5 =  X^5 + X^2 + 1$\\
&$p^n=64$&$h_6 =  X^6 + X^4 + X^3 + X + 1$\\
&$p^n=128$&$h_7 =  X^7 + X + 1$\\
&$p^n=256$&$h_8 =  X^8 + X^4 + X^3 + X^2 + 1$\\
&$p^n=512$&$h_9 =  X^9 + X^4 + 1$\\
&$p^n=1024$&$h_{10} =  X^{10} + X^6 + X^5 + X^3 + X^2 + X + 1$\\
\hline
$p=3$&$p^n=3$&$h_1 = X + 1$\\
&$p^n=9$&$h_2 =  X^2 + 2 X + 2$\\
&$p^n=27$&$h_3 =  X^3 + 2 X + 1$\\
&$p^n=81$&$h_4 =  X^4 + 2 X^3 + 2$\\
&$p^n=243$&$h_5 =  X^5 + 2 X + 1$\\
&$p^n=729$&$h_6 =  X^6 + 2 X^4 + X^2 + 2 X + 2$\\
\hline
$p=5$&$p^n=5$&$h_1 = X + 3$\\
&$p^n=25$&$h_2 = X^2 + 4 X + 2$\\
&$p^n=125$&$h_3 = X^3 + 3 X + 3$\\
&$p^n=625$&$h_4 = X^4 + 4 X^2 + 4 X + 2$\\
\hline
$p=7$&$p^n=7$&$h_1 = X + 4$\\
&$p^n=49$&$h_2 = X^2 + 6 X + 3$\\
&$p^n=343$&$h_3 = X^3 + 6 X^2 + 4$\\
\hline
\end{tabular}
\end{center}

\section{Le caractère quadratique et la réciprocité quadratique}\label{caractere-quadratique-corps-finis}

\subsection{Le caractère quadratique en caractéristique impaire}\label{caractere-quadratique-corps-finis-caracteristique-impaire}

\subsubsection{} Si on se penche sur la question de la factorisation
des polynômes (ou la résolution des équations) de degré $2$ sur
$\FF_q$, en remarquant que, pour $q$ impair l'équation $X^2 + bX + c =
0$ peut se réécrire sous la forme $(X+\frac{b}{2})^2 =
(\frac{b^2}{4} - c)$, on voit que tout se ramène, en caractéristique
impaire, à déterminer \emph{quels éléments de $\FF_q$ sont des
  carrés}.  Nous allons, pour approfondir cette question, introduire
la définition suivante :

\begin{definition2}\label{definition-caractere-quadratique}
Soit $q$ une puissance d'un nombre premier impair.  On
appelle \emph{caractère quadratique} sur $\FF_q$ la fonction
$a \mapsto a^{(q-1)/2}$.  On note $\FF_q^{\times2}$ l'ensemble des
éléments de $\FF_q^\times$ qui sont des carrés.
\end{definition2}

\begin{proposition2}\label{denombrement-carres-f-q}
Si $q$ est une puissance d'un nombre premier impair, alors le caractère
quadratique ne prend sur $\FF_q^\times$ que les valeurs $+1$ et $-1$,
et on a $a \in \FF_q^{\times2}$ si et seulement si $a^{(q-1)/2} =
+1$ ; de plus, $\# \FF_q^{\times2} = \frac{1}{2}(q-1)$.
\end{proposition2}
\begin{proof}
L'application $z \mapsto z^2$, vue comme un morphisme
$\FF_q^\times \to \FF_q^\times$, a pour noyau $\{\pm 1\}$ (de
cardinal $2$), et pour image $\FF_q^{\times2}$, donc
$2\, \#\FF_q^{\times2} = \#\FF_q^{\times}$ : ceci montre la dernière
affirmation.

Si $e = a^{(q-1)/2}$ avec $a \in \FF_q^\times$, alors $e^2 = a^{q-1} =
1$, donc $e$ vaut $+1$ ou $-1$.

Si $a = b^2$ avec $b \in \FF_q^\times$, alors $a^{(q-1)/2} = b^{q-1} =
+1$.  On a donc montré que sur tout élément de $\FF_q^{\times2}$ le
caractère quadratique vaut $+1$ : comme on vient de voir qu'il y a
$\frac{1}{2}(q-1)$ tels éléments et que le polynôme $X^{(q-1)/2} - 1$
(de degré $\frac{1}{2}(q-1)$) n'est pas nul, il ne peut s'annuler en
aucun autre point de $\FF_q$ : on voit donc que réciproquement si
$a^{(q-1)/2} = +1$ alors $a \in \FF_q^{\times2}$.
\end{proof}

On pouvait également démontrer ce résultat en utilisant un élément
primitif $g$ (cf. \ref{cyclicite-groupe-multiplicatif-corps}) : les
éléments de $\FF_q^{\times2}$ sont ceux qui s'écrivent $g^{2i}$ avec
$i$ entier (et bien défini modulo $\frac{1}{2}(q-1)$).

\begin{corollaire2}\label{produits-de-non-carres-dans-f-q}
Un produit $ab$ dans $\FF_q$ est un carré \emph{si et seulement si}
les deux facteurs $a,b$ sont soit tous deux des carrés soit tous deux
des non-carrés.
\end{corollaire2}
\begin{proof}
Cela découle de \ref{denombrement-carres-f-q} et du fait que le
caractère quadratique est un morphisme multiplicatif : $(ab)^{(q-1)/2}
= a^{(q-1)/2}\, b^{(q-1)/2}$.
\end{proof}

On peut déjà résoudre complètement la question du caractère
quadratique de $-1$.

\begin{corollaire2}\label{caractere-quadratique-de-moins-un}
Pour $q$ une puissance d'un nombre premier impair, l'élément $-1$ de
$\FF_q$ est un carré \emph{si et seulement si} $q \equiv 1 \pmod{4}$.
\end{corollaire2}
\begin{proof}
Cela découle de \ref{denombrement-carres-f-q} et du fait que
$(-1)^{(q-1)/2}$ vaut $+1$ si $q \equiv 1 \pmod{4}$ et $-1$ si $q
\equiv 3 \pmod{4}$.
\end{proof}

On va voir en \ref{reciprocite-quadratique} plus bas ce qu'on peut
dire du caractère quadratique de $2$ et plus généralement de tout
entier.

\subsubsection{} Le calcul du caractère quadratique peut se faire
efficacement par un algorithme d'exponentiation rapide : ceci permet
donc de savoir effectivement si un élément donné de $\FF_q^\times$
admet une racine carrée.  (On renvoie à \ref{remarques-critere-rabin}
pour la question de la représentation des corps finis et
l'algorithmique dans ceux-ci ; mais pour beaucoup de questions
algorithmiques considérées ici, le cas où $q = p$ est premier et
$\FF_q = \ZZ/p\ZZ$ est déjà intéressant.)  Calculer effectivement la
racine carrée d'un élément qui en admet une est une question plus
délicate, qui sera considérée
en \refext{ACF}{equations-quadratiques-corps-finis}.

\begin{lemme2}\label{carres-extensions-corps-finis}
Soit $q = p^r$ avec $p$ premier impair.  Si $r$ est impair, alors un
élément de $\FF_p$ est un carré dans $\FF_p$ si et seulement si il
l'est dans $\FF_q$ (autrement dit, $\FF_q^{\times 2} \cap \FF_p
= \FF_p^{\times 2}$).  Si $r$ est pair, alors tout élément de $\FF_p$
est un carré dans $\FF_q$.
\end{lemme2}
\begin{proof}
On peut par exemple, pour $a \in \FF_p^\times$, écrire $a^{(q-1)/2} =
a^{(p^r-1)/2} = (a^{(p-1)/2})^{p^{r-1} + \cdots + p + 1}$, et
$a^{(p-1)/2}$ vaut $+1$ ou $-1$ selon que $a$ est un carré
dans $\FF_p$, et la parité de $p^{r-1} + \cdots + p + 1$ est la même
que celle de $r$, ce qui démontre le résultat.

Une autre démonstration consiste à considérer le polynôme $X^2 - a$ et
à lui
appliquer \ref{corollaire-scindage-partiel-polynomes-corps-finis}.
\end{proof}

Mentionnons par ailleurs le résultat combinatoire suivant, qui est une
application inattendue des propriétés du caractère quadratique sur les
corps finis :
\begin{proposition2}\label{matrice-d-hadamard-par-corps-finis}
Soit $q$ une puissance d'un nombre premier vérifiant $q \equiv
3 \pmod{4}$.  Alors il existe une matrice $M$ de taille $(q+1)\times
(q+1)$ à coefficients dans $\{\pm 1\}$ telle que deux lignes
distinctes quelconques de $M$ ont la même valeur en $\frac{1}{2}(q+1)$
de leurs entrées et une valeur opposée en les $\frac{1}{2}(q+1)$
autres.
\end{proposition2}
\begin{proof}
En notant $\PP^1(\FF_q) = \FF_q \cup \{\infty\}$, on définit une
fonction $\varphi\colon \PP^1(\FF_q) \times \PP^1(\FF_q) \to \{\pm
1\}$ par $\varphi(\infty,\infty) = \varphi(x,\infty)
= \varphi(\infty,y) = +1$ si $x \in \FF_q$ et $y \in \FF_q$, par
$\varphi(x,x) = -1$ pour tout $x \in \FF_q$, et par $\varphi(x,y) =
(x-y)^{(q-1)/2}$ (c'est-à-dire $+1$ ou $-1$ selon que $x-y$ est un
carré ou non dans $\FF_q$, cf. \ref{denombrement-carres-f-q}) si
$x\neq y$ avec $x,y\in \FF_q$.  La matrice indicée par
$\PP^1(\FF_q) \times \PP^1(\FF_q)$ dont les coefficients sont donnés
par la fonction $\varphi$ répond à la question : pour le montrer, il
s'agit de voir que si $x,x' \in \PP^1(\FF_q)$ avec $x\neq x'$ alors il
existe $\frac{1}{2}(q+1)$ valeurs $y \in \PP^1(\FF_q)$ exactement
telles que $\varphi(x,y) = \varphi(x',y)$.

Si $x$ vaut $\infty$, il s'agit de voir que $\frac{1}{2}(q+1)$ valeurs
$y$ vérifient $\varphi(x',y) = -1$, c'est-à-dire (puisque
$\varphi(x',x')=-1$) que $\frac{1}{2}(q-1)$ éléments $y \in \FF_q$
sont tels que $x'-y$ ne soit pas un carré dans $\FF_q$, ce qui est
bien le cas (cf. \ref{denombrement-carres-f-q}).  Si $x,x' \in \FF_q$,
on s'intéresse à $\varphi(x,y)/\varphi(x',y)$.  Si $y \in \FF_q$ et
$y \not\in \{x,x'\}$, cette fonction vaut
$(\frac{x-y}{x'-y})^{(q-1)/2}$, or l'expression $\frac{x-y}{x'-y}$
prend toutes les valeurs de $\FF_q$ sauf $0$ et $1$, donc
$(\frac{x-y}{x'-y})^{(q-1)/2}$ prend $\frac{1}{2}(q-3)$ fois la
valeur $+1$ ; si $y = \infty$, l'expression
$\varphi(x,y)/\varphi(x',y)$ vaut $+1$ ; si $y=x$ ou $y=x'$, enfin,
l'expression $\varphi(x,y)/\varphi(x',y)$ vaut $-(x'-x)^{(q-1)/2}$ et
$-(x-x')^{(q-1)/2}$ respectivement, et ces valeurs sont opposées
puisque $q\equiv 3 \pmod{4}$ entraîne $(-1)^{(q-1)/2} = -1$ ; on a
donc montré que $\varphi(x,y)/\varphi(x',y)$ prend exactement
$\frac{1}{2}(q+1)$ fois la valeur $+1$ lorsque $y$
parcourt $\PP^1(\FF_q)$.
\end{proof}

Une matrice telle que fournie par la
proposition \ref{matrice-d-hadamard-par-corps-finis}
s'appelle \emph{matrice d'Hadamard} de taille $q+1$.  On conjecture
qu'il existe une matrice d'Hadamard de toute taille multiple de $4$.

\subsection{La caractéristique $2$}\label{caractere-quadratique-corps-finis-caracteristique-2}

\subsubsection{} En caractéristique $2$, calculer
des racines carrées dans $\FF_q = \FF_{2^r}$ est facile : on a
$x^{2^r} = x$ d'après \refext{Fin}{petit-theoreme-fermat}, donc $x^{2^{r-1}}$
est une racine carrée de $x$.  À la différence du cas où $2$ est
inversible, cependant, savoir calculer des racines carrées ne permet
pas de résoudre toutes les équations quadratiques puisqu'on ne peut
pas écrire $X^2 + bX + c = 0$ sous la forme $(X+\frac{b}{2})^2 +
(c-\frac{b^2}{4}) = 0$.  À la place, si on note $\wp(Z) = Z^2 + Z$,
l'équation $X^2 + bX + c = 0$, lorsque $b\neq 0$ (le cas $b=0$ ayant
déjà été traité) peut se réécrire $\wp(X/b)+(c/b^2) = 0$, soit $X =
b\,\root\wp\of{c/b^2}$ si on note $\root\wp\of E$ une solution (si
elle existe) de l'équation $Z^2+Z = E$, l'autre solution étant alors
$\root\wp\of E + 1$ (puisque $\wp(Z+1) = \wp(Z)$).

\begin{definition2}\label{definition-caractere-quadratique-en-caracteristique-2}
Soit $q = 2^r$ une puissance de $2$.  On appelle \emph{caractère
quadratique additif} sur $\FF_q$ la fonction $\tau \colon a \mapsto a
+ a^2 + a^4 + a^8 + \cdots + a^{2^{r-1}}$ (qu'on notera aussi $\tau_r$
en cas d'ambiguïté).  On note $\wp\FF_q$ l'ensemble des éléments de
$\FF_q$ qui sont dans l'image de la fonction $\wp\colon z \mapsto z^2
+ z$.
\end{definition2}

On peut aussi considérer $\tau$ comme la trace pour l'extension
$\FF_q\bo\FF_2$ (cf. \ref{trace-et-norme-corps-finis}).

\begin{proposition2}\label{denombrement-artin-schreier-2-f-q}
Si $q$ est une puissance de $2$, alors le caractère quadratique
additif $\tau$ ne prend sur $\FF_q$ que les valeurs $0$ et $1$, et on
a $a \in \wp\FF_q$ si et seulement si $\tau(a) = 0$ ; de plus,
$\#(\wp\FF_q) = \frac{q}{2}$.
\end{proposition2}
\begin{proof}
L'application $\wp\colon z \mapsto z^2+z$, vue comme une application
$\FF_2$-linéaire $\FF_q \to \FF_q$, a pour noyau $\{0,1\}$ (de
cardinal $2$) puisque $0,1$ sont les deux solutions de $Z^2 + Z = 0$ ;
et elle a pour image $\wp\FF_q$, donc $2\, \#(\wp\FF_q) = \#\FF_q$ :
ceci montre la dernière affirmation.

Si $e = \tau(a)$ avec $a \in \FF_q$, alors $\wp(e) = e^2 + e = (a^2 +
a^4 + \cdots + a^q) + (a + a^2 + \cdots + a^{q/2}) = 0$ puisque $a^{q}
= a$, donc $e$ vaut $0$ ou $1$.

Si $a = \wp(b)$ avec $b \in \FF_q$, alors $\tau(a) = a + a^2 + \cdots
+ a^{q/2} = (b^2 + b) + (b^4 + b^2) + \cdots + (b^{q} + b^{q/2}) = 0$.
On a donc montré que sur tout élément de $\wp\FF_q$ le caractère
quadratique additif $\tau$ vaut $0$ : comme on vient de voir qu'il y a
$\frac{q}{2}$ tels éléments et que le polynôme $X + X^2 + X^4 + \cdots
+ X^{q/2}$ (de degré $\frac{q}{2}$) n'est pas nul, il ne peut
s'annuler en aucun autre point de $\FF_q$ : on voit donc que
réciproquement si $\tau(a) = 0$ alors $a \in \wp\FF_q$.
\end{proof}

\subsection{Symbole de Legendre, réciprocité quadratique et formule complémentaire}\label{reciprocite-quadratique}

On s'intéresse dans cette section au caractère quadratique des
éléments de $\FF_p$ avec $p$ un nombre premier impair.

\begin{definition2}\label{definition-symbole-legendre}
Si $p$ est un nombre premier impair et $a$ un entier, on
appelle \emph{symbole de Legendre} de $a$ modulo $p$, et on note
$\Legendre{a}{p}$, l'entier valant $0$ si $p|a$, et $1$ si $a$ est un
carré dans $\FF_p$, et $-1$ si $a$ n'est pas un carré dans $\FF_p$.
\end{definition2}

Il résulte trivialement de \ref{denombrement-carres-f-q} et
de \ref{produits-de-non-carres-dans-f-q} que :
\begin{proposition2}\label{formule-symbole-legendre}
Si $p$ est un nombre premier impair et $a$ un entier, alors
\[
\Legendre{a}{p} \equiv a^{(p-1)/2} \pmod{p}
\]
De plus, quels que soient les entiers $a,b$, on a $\Legendre{ab}{p}
= \Legendre{a}{p} \Legendre{b}{p}$.
\end{proposition2}

L'énoncé suivant, qui compare le caractère quadratique de $p$ modulo
$q$ au caractère quadratique de $q$ modulo $p$, et dont on va donner
deux démonstrations, porte le nom de \emph{loi de réciprocité
quadratique} :

\begin{theoreme2}\label{loi-reciprocite-quadratique}
Soient $p,q$ deux nombres premiers impairs distincts.  On a alors :
\[
\Legendre{p}{q} \Legendre{q}{p} = (-1)^{(p-1)(q-1)/4}
\]
— c'est-à-dire $\Legendre{q}{p} = \Legendre{p}{q}$ sauf si
$p,q \equiv 3 \pmod{4}$ auquel cas $\Legendre{q}{p} =
-\Legendre{p}{q}$.
\end{theoreme2}
\begin{proof}[Première démonstration]
Convenons pour cette démonstration de représenter les éléments de
$\ZZ/p\ZZ$ par $-\frac{p-1}{2},\ldots,\frac{p-1}{2}$, et de
dire d'un élément de $(\ZZ/p\ZZ)^\times$ qu'il est « positif »
lorsqu'il est congru à l'un des $\frac{p-1}{2}$ entiers
$1,2,3,\ldots,\frac{p-1}{2}$, et « négatif » lorsqu'il est congru à
l'un des $\frac{p-1}{2}$ entiers $-\frac{p-1}{2},\ldots,-1$.  Avec
cette définition, si $k \in \ZZ$ n'est pas multiple de $p$, son
« signe » modulo $p$ (c'est-à-dire $+1$ ou $-1$ selon qu'il a un
résidu positif ou négatif) vaut $(-1)^{\lfloor 2k/p\rfloor}$ où
$\lfloor\tiret\rfloor$ désigne la fonction partie entière.  Remarquons
d'ores et déjà que pour tout entier $i$ non multiple de $p$ on a
$\lfloor \frac{2qi}{p}\rfloor + \lfloor \frac{q(p-2i)}{p}\rfloor =
q-1$ (car $\lfloor\theta\rfloor +
\lfloor q-\theta\rfloor = q-1$ pour tout
$\theta \in \RR \setminus \ZZ$), et que cet entier est pair, de sorte
que $(-1)^{\lfloor 2qi/p\rfloor} = (-1)^{\lfloor q(p-2i)/p\rfloor}$
(ces deux expressions donnent donc le signe de $qi$ modulo $p$).

Le produit $\prod_{i=1}^{(p-1)/2} \bar\imath$ des éléments positif de
$(\ZZ/p\ZZ)^\times$ vaut $(\frac{p-1}{2})!$ modulo $p$.  Considérons
maintenant le produit $\prod_{i=1}^{(p-1)/2} q\bar\imath$ : on peut
manifestement l'écrire comme $q^{(p-1)/2} (\frac{p-1}{2})!$
modulo $p$.  Mais par ailleurs on ne peut pas avoir $q\bar\imath =
\pm q\bar\imath'$ pour $i,i' \in \{1,\ldots,\frac{p-1}{2}\}$ distincts,
donc les $q\bar\imath$ s'écrivent $\pm\bar\jmath$ avec $\bar\jmath$
parcourant $1,2,3,\ldots,\frac{p-1}{2}$ et le signe $\pm$ donné par
$(-1)^{\lfloor 2qi/p\rfloor} = (-1)^{\lfloor q(p-2i)/p\rfloor}$ comme
on l'a expliqué ; ainsi, $\prod_{i=1}^{(p-1)/2} q\bar\imath =
(-1)^{\sum_{i=1}^{(p-1)/2} \lfloor 2qi/p\rfloor}(\frac{p-1}{2})!$, et
en comparant les deux expressions trouvées et en
utilisant \ref{formule-symbole-legendre}, on a $\Legendre{q}{p} =
(-1)^{\sum_{i=1}^{(p-1)/2} \lfloor 2qi/p\rfloor}$ (« lemme
d'Eisenstein »), ou, mieux, $\Legendre{q}{p} =
(-1)^{\sum_{m=1}^{(p-1)/2} \lfloor qm/p\rfloor}$ (en appelant $m$ le
nombre $2i$ ou $p-2i$ selon que $0<i<\frac{p}{4}$ ou
$\frac{p}{4}<i<\frac{p}{2}$, de sorte que $m$ parcourt aussi les
entiers de $1$ à $\frac{p-1}{2}$ quand $i$ les parcourt).

Cette dernière expression admet l'interprétation géométrique
suivante : $\Legendre{q}{p}$ vaut $(-1)^\mu$ avec $\mu$ le nombre de
points $(m,n)$ à coordonnées entières telles que $0<m<\frac{p}{2}$ et
$0<n<\frac{q}{p}m$ et (donc) $0<n<\frac{q}{2}$, ou, si l'on préfère,
le nombre de points à coordonnées entières strictement à l'intérieur
du triangle du plan dont les sommets sont $(0,0)$, $(\frac{p}{2},0)$
et $(\frac{p}{2},\frac{q}{2})$.  On en déduit que
$\Legendre{p}{q} \Legendre{q}{p}$ est $(-1)^{\mu+\nu}$ avec $\mu+\nu$
le nombre de points $(m,n)$ à coordonnées entières vérifiant
$0<m<\frac{p}{2}$ et $0<n<\frac{q}{2}$ : on a bien $\mu+\nu
= \frac{(p-1)(q-1)}{4}$.
\end{proof}
\begin{proof}[Seconde démonstration]
Considérons $\FF_{q^r} = \FF_q(\zeta)$ (où $r$ est l'ordre
multiplicatif de $p$ modulo $q$) l'extension de $\FF_q$ par une racine
primitive $p$-ième de l'unité $\zeta$, c'est-à-dire le corps de
décomposition de $\Phi_p(X)$ sur $\FF_q$
(cf. \refext{Fin}{factorisation-phi-n}) dont on note $\zeta$ une racine.  Dans
ce corps, considérons la somme
\[
G = \sum_{i\in\FF_p^\times} \Legendre{i}{p} \zeta^i
\]
où on confond abusivement un $i \in \FF_p$ avec un représentant
quelconque de celui-ci dans $\ZZ$ (puisque $\Legendre{i}{p}$ et
$\zeta^i$ ne dépendent de la classe de $i$ modulo $p$).

On a alors $G^2
= \sum_{i,j\in \FF_p^\times} \Legendre{ij}{p} \zeta^{i+j}
= \sum_{i,t \in \FF_p^\times} \Legendre{t}{p} \zeta^{i(1+t)}$ (en
posant $t = j/i \in \FF_p^\times$ et en utilisant le fait que
$\Legendre{i}{p}^2 = 1$) ; comme $\sum_{i\in\FF_p^\times} \zeta^{iu}$
vaut $-1$ si $u \in \FF_p^\times$ et vaut $p - 1$ si $u = 0$, on en
déduit (en distinguant selon que $t=-1$ ou non) $G^2
= \Legendre{-1}{p}(p-1) - \sum_{t\neq 0,-1} \Legendre{t}{p}
= \Legendre{-1}{p} p$ car $\sum_{t\in\FF_p^\times} \Legendre{t}{p} =
0$ en vertu de \ref{denombrement-carres-f-q}.

Par ailleurs, $G^q = \Frob_q(G)
= \sum_{i\in\FF_p^\times} \Legendre{i}{p} \zeta^{qi}
= \sum_{j\in\FF_p^\times} \Legendre{q}{p} \Legendre{j}{p} \zeta^j$ (en
posant $j = qi$ et en utilisant de nouveau le fait que
$\Legendre{q}{p}$ est son inverse), donc $G^q = \Legendre{q}{p} G$, et
par conséquent $G^{q-1} = \Legendre{q}{p}$.

En écrivant $G^{q-1} = (G^2)^{(q-1)/2}$, on a donc prouvé
$\Legendre{q}{p} = \Legendre{-1}{p}^{(q-1)/2} p^{(q-1)/2} =
(-1)^{(p-1)(q-1)/4} \Legendre{p}{q}$ ; cette égalité entre éléments de
$\{\pm 1\}$ a lieu dans $\FF_{q^r}$ donc dans $\ZZ$ : c'est ce qu'on
voulait prouver.
\end{proof}

Pour ce qui est du caractère quadratique de $2$, il est déterminé par
la proposition suivante souvent appelée « formule complémentaire » :
\begin{proposition2}\label{formule-complementaire}
Soit $p$ un nombre premier impair.  On a alors :
\[
\Legendre{2}{p} = (-1)^{(p^2-1)/8}
\]
— c'est-à-dire $\Legendre{2}{p} = 1$ si $p\equiv 1,7 \pmod{8}$ et
$\Legendre{2}{p} = -1$ si $p\equiv 3,5 \pmod{8}$.
\end{proposition2}
\begin{proof}[Première démonstration]
Convenons pour cette démonstration de représenter les éléments de
$\ZZ/p\ZZ$ par $-\frac{p-1}{2},\ldots,\frac{p-1}{2}$, et de
dire d'un élément de $(\ZZ/p\ZZ)^\times$ qu'il est « positif »
lorsqu'il est congru à l'un des $\frac{p-1}{2}$ entiers
$1,2,3,\ldots,\frac{p-1}{2}$, et « négatif » lorsqu'il est congru à
l'un des $\frac{p-1}{2}$ entiers $-\frac{p-1}{2},\ldots,-1$.

Le produit $\prod_{i=1}^{(p-1)/2} \bar\imath$ des éléments positif de
$(\ZZ/p\ZZ)^\times$ vaut $(\frac{p-1}{2})!$ modulo $p$.  Considérons
maintenant le produit $\prod_{i=1}^{(p-1)/2} 2\bar\imath$ : on peut
manifestement l'écrire comme $2^{(p-1)/2} (\frac{p-1}{2})!$
modulo $p$.  Mais par ailleurs on ne peut pas avoir $2\bar\imath =
\pm 2\bar\imath'$ pour $i,i' \in \{1,\ldots,\frac{p-1}{2}\}$ distincts,
donc les $2\bar\imath$ s'écrivent $\pm\bar\jmath$ avec $\bar\jmath$
parcourant $1,2,3,\ldots,\frac{p-1}{2}$ et le signe $\pm$ (donné par
$(-1)^{\lfloor 4i/p\rfloor}$ si l'on veut) vaut $+$ pour
$0<i<\frac{p}{4}$ et $-$ pour $\frac{p}{4}<i<\frac{p}{2}$.  Le nombre
de signes $-$ est donc égal au nombre d'entiers entre $\frac{p}{4}$ et
$\frac{p}{2}$ et il est facile de se convaincre (par exemple en
considérant séparément chaque cas $1,3,5,7$ modulo $8$) que le signe
du produit est alors $(-1)^{(p^2-1)/8}$.  Ainsi,
$\prod_{i=1}^{(p-1)/2} 2\bar\imath =
(-1)^{(p^2-1)/8}(\frac{p-1}{2})!$, et en comparant les deux
expressions trouvées et en utilisant \ref{formule-symbole-legendre},
on a $\Legendre{2}{p} = (-1)^{(p^2-1)/8}$.
\end{proof}
\begin{proof}[Seconde démonstration]
Considérons $\FF_{p^r} = \FF_p(\zeta)$ (où $r$ est l'ordre
multiplicatif de $8$ modulo $p$) l'extension de $\FF_p$ par une racine
primitive $8$-ième de l'unité $\zeta$, c'est-à-dire le corps de
décomposition de $\Phi_8(X)$ sur $\FF_p$
(cf. \refext{Fin}{factorisation-phi-n}) dont on note $\zeta$ une racine.  Dans
ce corps, considérons la somme
\[
G = \zeta - \zeta^3 - \zeta^5 + \zeta^7
\]

On a alors $G^2 = 4 - 4\zeta^4 = 8$.

Par ailleurs, $G^p = \Frob_p(G) = \zeta^p - \zeta^{3p} - \zeta^{5p}
+ \zeta^{7p}$, donc $G^p = (-1)^{(p^2-1)/8} G$ (en considérant
séparément les cas $p\equiv 1,7\pmod{8}$ et $p\equiv 3,5\pmod{8}$), et
par conséquent $G^{p-1} = (-1)^{(p^2-1)/8}$.

En écrivant $G^{p-1} = (G^2)^{(p-1)/2}$, on a donc prouvé
$(-1)^{(p^2-1)/8} = 8^{(p-1)/2} = \Legendre{8}{p} = \Legendre{2}{p}$ ;
cette égalité entre éléments de $\{\pm 1\}$ a lieu dans $\FF_{p^r}$
donc dans $\ZZ$ : c'est ce qu'on voulait prouver.

Signalons la variante suivante. L'élément $ζ+ζ^{-1}$ est,
dans $𝐅_{p^r}$ une racine carré de $2$ car
$(ζ+ζ^{-1})²=2+ζ²+{ζ²}^{-1}=2$. Il en résulte que $2$ est un carré
dans $𝐅_p$ si et seulement si $ζ^p+ζ^{-p}=ζ+ζ^{-1}$. Cette condition
ne dépend que de $±p$ modulo $8$ et on vérifie immédiatement quelles
sont les valeurs pour lesquelles elle est satisfaite.
\end{proof}

\begin{remarque2}
L'étude des nombres premiers $p$ pour lesquels $2$ est un \emph{cube}
est plus délicate et s'insère naturellement dans la « théorie
non abélienne du corps de classes » (ou « programme de Langlands »).
On démontre que le nombre de solutions
dans $𝐅_p$ de l'équation $x³=2$ 
est $1+a_p$, où les $a_n$ sont les coefficients
de la série formelle
\[
x∏_{n=1}^∞ \big((1-x^{6n})(1-x^{18n})\big)=∑^∞_{n=1} a_n x^n.
\]
% cf. nouveau livre de Katô p. 36. À déplacer ?
\end{remarque2}

\begin{remarques2}\label{remarque-periodicite-symbole-legendre}
La loi de réciprocité quadratique et la formule complémentaire (ainsi
que la formule \ref{formule-symbole-legendre} pour le cas $a=-1$)
permettent de conclure que $\Legendre{a}{p}$, qui est évidemment une
fonction périodique de $a$ à $p$ fixé, est aussi, ce qui n'était pas
évident a priori, une fonction périodique de $p$ à $a$ fixé (au sens
où il existe un entier $T$ ne dépendant que de $a$ tel que si $p,p'$
sont premiers impairs et $p \equiv p' \pmod{T}$ alors $\Legendre{a}{p}
= \Legendre{a}{p'}$) ; plus précisément, il admet pour période $T =
4|a|$ (cela sera démontré en \ref{proprietes-symbole-jacobi}
ci-dessous).  Ceci peut inciter à vouloir donner un sens à
$\Legendre{a}{n}$ dans des cas où $n$ n'est plus nécessairement
premier, en appliquant cette périodicité (par exemple, puisque
$\Legendre{3}{p} = +1$ pour tout premier $p \equiv 1 \pmod{12}$, on
est tenté de convenir que $\Legendre{3}{25} = +1$ et $\Legendre{3}{85}
= +1$ même si $25$ et $85$ ne sont pas premiers et que $3$ n'est même
pas un carré dans $\ZZ/25\ZZ$ ni $\ZZ/85\ZZ$).  Le symbole de Jacobi
constitue une telle généralisation du symbole de Legendre :
\end{remarques2}

\subsection{Symboles de Jacobi et de Kronecker}

\begin{definition2}\label{definition-symbole-jacobi}
Pour tout $a \in \ZZ$ et tout $b \in \NN$ impair, on
appelle \emph{symbole de Jacobi} de $a$ et $b$, et on note
$\Legendre{a}{b}$, le symbole défini par $\Legendre{a}{b}
= \Legendre{a}{p_1}\cdots \Legendre{a}{p_k}$ où $b = p_1\cdots p_k$
avec $p_i$ des nombres premiers impairs, et où $\Legendre{a}{p_i}$
désigne alors le symbole de
Legendre (\ref{definition-symbole-legendre}).
\end{definition2}

\begin{proposition2}\label{proprietes-symbole-jacobi}
Le symbole de Jacobi défini en \ref{definition-symbole-jacobi} a les
propriétés suivantes :
\begin{itemize}
\item On a $\Legendre{a}{b} = 0$ si et seulement si $a,b$ sont
premiers entre eux.
\item Pour tous $a,a',b \in \ZZ$ avec $b$ positif impair, on a
$\Legendre{aa'}{b} = \Legendre{a}{b} \Legendre{a'}{b}$.
\item Pour tous $a,b,b' \in \ZZ$ avec $b,b'$ positifs impairs, on a
$\Legendre{a}{bb'} = \Legendre{a}{b} \Legendre{a}{b'}$.
\item À $b$ positif impair fixé, la fonction $\Legendre{a}{b}$ est
périodique admettant $b$ pour période.
\item À $a \neq 0$ fixé, la fonction $\Legendre{a}{b}$ est périodique
admettant $4|a|$ pour période, et même $2|a|$ si $a \equiv 1
\pmod{4}$ et $|a|$ si $a \equiv 0 \pmod{4}$.
\item Pour tout $b$ positif impair, on a $\Legendre{-1}{b} =
(-1)^{(b-1)/2}$.
\item Pour tout $b$ positif impair, on a $\Legendre{2}{b} =
(-1)^{(b^2-1)/8}$.
\item Pour tous $a,b$ positifs impairs, on a
$\Legendre{a}{b} \Legendre{b}{a} = (-1)^{(a-1)(b-1)/4}$.
\end{itemize}
\end{proposition2}
\begin{proof}
Les deux premières propriétés découlent immédiatement des propriétés
correspondantes du symbole de Legendre.  La troisième propriété est
une conséquence immédiate de la définition.  La quatrième propriété
(périodicité en $a$) découle de nouveau de la propriété correspondante
du symbole de Legendre.  La propriété suivante (périodicité en $b$)
sera démontrée en dernier.

Les formules $\Legendre{-1}{b} = (-1)^{(b-1)/2}$, $\Legendre{2}{b} =
(-1)^{(b^2-1)/8}$ et $\Legendre{a}{b} \Legendre{b}{a} =
(-1)^{(a-1)(b-1)/4}$ résultent des formules correspondantes pour le
symbole de Legendre
(\ref{formule-symbole-legendre}, \ref{formule-complementaire}
et \ref{loi-reciprocite-quadratique}) et du fait que ces formules sont
multiplicatives en $b$.

Montrons enfin que $\Legendre{a}{b}$ est périodique en $b$ avec les
périodes annoncées.  Si $a$ est positif impair, on a $\Legendre{a}{b}
= (-1)^{(a-1)(b-1)/4} \Legendre{b}{a}$ comme on vient de le voir, et
le membre de droite admet $4a$ pour période ou même $2a$ si $a \equiv
1 \pmod{4}$ ; si $a = -1$ alors $\Legendre{-1}{b}$ est périodique de
période $4$ et on en déduit le résultat pour tout $a$ impair.  Enfin,
si $a = 2^v a'$ avec $a'$ impair, on a $\Legendre{a}{b}
= \Legendre{2}{b}^v \Legendre{a'}{b}$.  Pour $v=1$ (cas où $a \equiv
2 \pmod{4}$), le premier facteur a pour période $8$ et le second admet
la période $4|a'|$, donc le produit admet la période $8|a'| = 4|a|$ ;
pour $v=2$, le premier facteur est constant et le second admet la
période $4|a'|$ donc le produit admet la période $4|a'| = |a|$ ; et
pour $v\geq 3$, le premier facteur admet la période $8$ et le second
la période $4|a'|$, donc le produit admet la période $8|a'|$
donc $|a|$.
\end{proof}

\begin{remarques2}
\begin{itemize}
\item Comme on l'a déjà illustré
en \ref{remarque-periodicite-symbole-legendre} par l'exemple de
$\Legendre{3}{25} = +1$ et $\Legendre{3}{85} = +1$, on peut très bien
avoir $\Legendre{a}{b} = +1$ sans que $a$ soit un carré
dans $\ZZ/b\ZZ$.  En revanche, si $\Legendre{a}{b} = -1$ (avec $b$
positif impair) alors $a$ n'est pas un carré dans $\ZZ/b\ZZ$ puisque
$a$ n'est pas un carré modulo l'un des facteurs premiers de $b$.
Voir cependant \ref{symbole-de-jacobi-et-corps-finis} ci-dessous.
\item La formule \ref{formule-symbole-legendre} n'est pas valable en
général pour le symbole de Jacobi, même si $a$ est effectivement un
carré modulo $b$ (le nombre noté $p$
en \ref{formule-symbole-legendre}) : par exemple, $\Legendre{11}{35} =
+1$, et de fait $11 \equiv 9^2 \pmod{35}$, pourtant
$11^{(35-1)/2} \equiv 16 \pmod{35}$.
\end{itemize}
\end{remarques2}

La proposition suivante est utile pour certains calculs, mais elle est
vraie pour des raisons essentiellement triviales :
\begin{proposition2}\label{symbole-de-jacobi-et-corps-finis}
Soit $q$ une puissance d'un nombre premier $p$ impair, et $a \in \ZZ$
non multiple de $p$.  Alors $a$ est un carré dans $\FF_q$ si et
seulement si $\Legendre{a}{q} = +1$ où $\Legendre{a}{q}$ désigne le
symbole de Jacobi.
\end{proposition2}
\begin{proof}
Écrivons $q = p^r$.  Si $r$ est pair alors $\Legendre{a}{q}
= \Legendre{a}{p}^2 = +1$, et $a$ est bien un carré dans $\FF_q$
d'après \refext{Fin}{carres-extensions-corps-finis}.  Si $r$ est impair alors
$\Legendre{a}{q} = \Legendre{a}{p}^r = \Legendre{a}{p}$, et $a$ est un
carré dans $\FF_q$ si et seulement s'il l'est dans $\FF_p$ de nouveau
d'après \refext{Fin}{carres-extensions-corps-finis}.
\end{proof}

\begin{remarque2}
On définit parfois une généralisation encore plus poussée des symboles
de Legendre et de Jacobi : le \emph{symbole de Kronecker}
$\Legendre{a}{b}$ défini pour tous $a,b\in\ZZ$.  Celui-ci est défini
en écrivant $b = u p_1\cdots p_k$ avec $u \in \{\pm 1\}$ et $p_i$ des
nombres premiers (cette fois $p_i=2$ est admis), où $\Legendre{a}{p}$
désigne le symbole de Legendre (\ref{definition-symbole-legendre}) si
$p$ est premier impair, et de plus :
\[\Legendre{a}{2} = \left\{
\begin{array}{ll}
0&\textrm{si $a$ est pair}\\
(-1)^{(a^2-1)/8}&\textrm{si $a$ est impair}\\
\end{array}
\right.\]
\[\Legendre{a}{-1} = \left\{
\begin{array}{ll}
1&\textrm{si $a\geq 0$}\\
-1&\textrm{si $a<0$}\\
\end{array}
\right.\]
et enfin
\[\Legendre{a}{0} = \left\{
\begin{array}{ll}
1&\textrm{si $a = \pm 1$}\\
0&\textrm{sinon}\\
\end{array}
\right.\]
Le prix à payer pour une telle généralisation est principalement de
perdre la périodicité de $\Legendre{a}{b}$ par rapport à $b$ lorsque
$a \equiv -1 \pmod{4}$ (ainsi que la périodicité par rapport à $a$
lorsque $b \leq 0$).  En fait, le choix de $\Legendre{a}{2} =
(-1)^{(a^2-1)/8}$ (pour $a$ impair) est quelque peu arbitraire, et le
symbole de Kronecker ne possède pas le caractère naturel du symbole de
Jacobi.  Il vérifie néanmoins les propriétés suivantes dont la
vérification est laissée au lecteur :
\begin{itemize}
\item On a $\Legendre{a}{b} = 0$ si et seulement si $a,b$ sont
premiers entre eux.
\item Pour tous $a,a',b \in \ZZ$, on a $\Legendre{aa'}{b}
= \Legendre{a}{b} \Legendre{a'}{b}$.
\item Pour tous $a,b,b' \in \ZZ$, on a $\Legendre{a}{bb'}
= \Legendre{a}{b} \Legendre{a}{b'}$ sauf éventuellement si $a=-1$ et
$bb'=0$.
\item À $b>0$ fixé, la fonction $\Legendre{a}{b}$ est périodique
admettant $4b$ pour période, et même $b$ si $b \not\equiv 2 \pmod{4}$.
\item À $a \neq 0$ fixé, la fonction $\Legendre{a}{b}$ est périodique
admettant $4|a|$ pour période si $a \not\equiv -1 \pmod{4}$, et même
$|a|$ si $a \equiv 0,1 \pmod{4}$.
\end{itemize}
\end{remarque2}


\section{Hypersurfaces diagonales ; réciprocité quadratique}

\subsection{Dualité dans les groupes abéliens finis}

\subsubsection{}Soit $G$ un groupe. Un morphisme $χ∈\Hom(G,𝐔)$,
où $𝐔=\{z∈𝐂, |z|=1\}≅𝐑/𝐙$, est appelé un \emph{caractère} du groupe $G$ ;
on note $\chap{G}$ leur ensemble, qui est naturellement un groupe \emph{abélien} : $(χχ')(g)=χ(g)χ'(g)$. 
C'est le \emph{dual} de $G$.

\subsubsection{}Le lecteur trouvera dans la littérature des variantes : on
aurait pu considérer $\Hom(G,𝐂^×)$ (on parle alors parfois de
\emph{quasi-caractères} ou caractères généralisés), $\Hom(G,E^×)$ (où $E$ est un corps contenant
les racines $\# G$-ème de l'unité, ou bien encore l'ensemble $\Hom(G,𝐐/𝐙)$.
Enfin, si $G$ est un groupe
topologique localement compact, %donc séparé
on pourrait considérer plutôt l'ensemble des caractères \emph{continus}. Muni de la topologie dite \emph{compacte ouverte}
c'est à nouveau un groupe topologique localement compact (dualité
de Pontrâgin). Dans le cas des groupes finis, ces notions sont toutes équivalentes. 
Par commodité nous préférons voir nos caractères comme à valeurs dans le cercle
unité complexe.

\subsubsection{}Par composition des fonctions, tout morphisme $H→G$ de groupes
induit un morphisme de groupes abéliens $\chap{G}→\chap{H}$.

\begin{lemme2}\label{lemme-Q-sur-Z-est-injectif}
Soit $K→G$ une \emph{injection} de groupes abéliens finis.
Le morphisme dual $\chap{G}→\chap{K}$ est une \emph{surjection}. 
\end{lemme2}

On note $K^{\perp}$ son noyau ; en symboles, $K^{\perp}=\{χ∈\chap{G}, χ(K)=\{1\}\}$.
Le morphisme $K^\perp→\chap{G/K}$ est une bijection :
tout caractère de $G$ trivial sur $K$ induit un caractère de $G/K$ et 
réciproquement.

\begin{démo}[Démonstration du lemme]
Soit $χ:K→\mathbf{U}$ un caractère de $K$ ; il faut montrer qu'il s'étend
à $G$, c'est-à-dire qu'il existe un caractère $χ':G→\mathbf{U}$ dont la restriction
à $K$ soit $χ$. Supposons $K≠G$ sans quoi le résultat est trivial et
considérons $x∈G-K$. Soient $r$ le plus petit entier non nul tel que
$x^r∈K$ et $z$ une racine $r$-ème de $χ(x^r)$ dans $𝐂$. On
a donc $χ(x^{rα})=z^{rα}$ pour tout $α∈ℕ$.
Il en résulte immédiatement que l'application $χ':⟨K,x⟩→\mathbf{U}$, $kx^i\mapsto χ(k)z^i$
est bien définie ; c'est un caractère du groupe $⟨K,x⟩$.
De proche en proche, on peut donc étendre le caractère initial à $G$ tout entier.
(De façon précise : procéder par récurrence sur l'indice $(G:K)$.)
\end{démo}

L'énoncé dual est trivial : si $G→H$ est une \emph{surjection},
le morphisme induit $\chap{H}→\chap{G}$ est une injection. (Cet
énoncé, de nature ensembliste, est vrai sans hypothèse sur $G$ ou $H$.)

Il en résulte que pour toute suite \emph{exacte} de groupes abéliens finis $1→K→G→H→1$,
la suite $1→\chap{H}→\chap{G}→\chap{K}→1$ est également exacte. En effet,
$K^\perp:=\Ker(\chap{G}→\chap{K})$ est naturellement
en bijection avec $\chap{G/K}$.

\begin{lemme2}
Soit $G$ un groupe fini abélien. Le morphisme d'évaluation
$G→\chap{\chap{G}}$, $g\mapsto \big(\mathtextrm{év}_g:χ\mapsto χ(g)\big)$ est un isomorphisme.
\end{lemme2}

\begin{démo}
On procède à nouveau par récurrence sur $\# G$, en remarquant
que l'énoncé est trivial pour un groupe cyclique (exercice).
Dans le cas général, on considère comme précédemment le diagramme 
de suites exactes :
\textcolor{red}{xymatrix à remplacer par du TikZ!}
%$$
%\xymatrix{
%1 \ar[d] \ar[r] & K \ar[d] \ar[r] & G \ar[d] \ar[r] & H \ar[d] \ar[r] & 1 \ar[d] \\
%1 \ar[r] & \chap{\chap{K}}  \ar[r] & \chap{\chap{G}} \ar[r] & \chap{\chap{H}} \ar[r] & 1 
%}
%$$
Par hypothèse de récurrence, $K→\chap{\chap{K}}$ et $H→\chap{\chap{H}}$ sont 
des isomorphismes ; il en est donc de même de $G→\chap{\chap{G}}$
(chasse au diagramme).
\end{démo}

\begin{proposition2}
Tout groupe abélien fini est isomorphe à un produit
de groupes cycliques.
\end{proposition2}

\begin{démo}
Soit $ω=∏ p_i^{r_i}$ le p.g.c.d des ordres d'éléments de $G$.
Pour tout $i$, il existe un élément $g_i$ d'ordre un multiple de $p_i^{r_i}$ ;
quitte à l'élever à une puissance convenable, on peut le supposer d'ordre
exactement $p_i^{r_i}$. Le produit $g=∏g_i$ est alors d'ordre exactement $ω$.
Soient $ζ_ω$ une racine primitive $ω$-ème de l'unité dans $𝐂$ et $χ:⟨g⟩→\mathbf{U}$ 
le caractère défini par $χ(g)=ζ_ω$. Il s'étend en un caractère $χ'$ de $G$.
Son noyau $\Ker(χ')$ est d'indice $ω$ (le cardinal de son image) et $\Ker(χ')⋂⟨g⟩=\{e\}$
de sorte que $G≅⟨g⟩×\Ker(χ')$. On peut donc démontrer la proposition par
récurrence sur l'ordre du groupe.
\end{démo}

\begin{corollaire2}
Si $G$ un groupe abélien fini il existe un isomorphisme
entre $G$ et $\chap{G}$.
\end{corollaire2}

\begin{démo}
Le résultat étant évident pour un groupe cyclique, il suffit de vérifier
que le dual d'un produit $K×K'$ est isomorphe au produit $\chap{K}×\chap{K'}$
des duaux. C'est immédiat. (Pour les groupes abéliens, le produit cartésien est 
la somme directe (comme $𝐙$-module).)
\end{démo}

\begin{lemme2}
\label{lemme-orthogonalite-caracteres}
Soient $G$ un groupe abélien fini et $g∈G$.
Alors, $∑_{χ∈\chap{G}} χ(g)$ est égal à $0$ si $g≠e$ et $|G|$ sinon.
\end{lemme2}

\begin{démo}
Le résultat est trivial si $g=e$. Supposons 
$g≠e$. Puisque le morphisme $G→\chap{\chap{G}}$ est un 
isomorphisme, il est donc injectif : $\mathtextrm{év}_g≠e$.
En d'autres termes, il existe un caractère $χ'∈\chap{G}$
tel que $χ'(g)≠1$. Soit $S=∑_χ χ(g)$. On a $χ'(g)S=∑_χ (χ'χ)(g)=S$.
Puisque $χ'(g)≠1$, on a bien $S=0$.
\end{démo}

\begin{corollaire2}
\label{variante-orthogonalite-caracteres}
Soit $G$ un groupe abélien fini et $χ∈\chap{G}$.
Alors, $∑_{g∈G} χ(g)$ est égal à $0$ si $χ ≠ 1$
et $|G|$ sinon.
\end{corollaire2}

\begin{démo}
Cela résulte de l'égalité $∑_g χ(g)=∑_g \mathtextrm{év}_g(χ)$,
du lemme précédent, et du fait que tout caractère de $\chap{G}$ est
de la forme $\mathtextrm{év}_g$ pour un unique $g∈G$.
\end{démo}

\subsection{Équation $X^n=g$ dans un groupe abélien fini ; application}

Pour tout groupe abélien $G$ (en notation multiplicative) et
tout entier $n$, notons $G[n]:=\{g∈G, g^n=1\}$ et $nG=\{g^n, g∈G\}$.
La surjection $G→G/nG$ induit une \emph{injection}
$\chap{G/nG}↪\chap{G}[n]$ : un caractère composé $G→G/nG→\mathbf{U}$
est tué par $n$. Le premier groupe a pour cardinal $(G:nG)$ ; celui de droite
$(\chap{G}:n\chap{G})$. D'après la proposition ci-dessus, $G≅\chap{G}$,
de sorte que $(\chap{G}:n\chap{G})=(G:nG)$ et, finalement,
$$
\chap{G/nG} ⥲ \chap{G}[n].
$$

Soit $g∈G$ et notons $\sur{g}$ son image dans $G/nG$. 
Cette image est nulle si et seulement si pour tout $\sur{χ}∈\chap{G/nG}$, $\sur{χ}(\sur{g})=1$.
Soit $χ$ l'image de $\sur{χ}$ par l'isomorphisme précédent ; on 
a par définition $χ(g)=\sur{χ}(\sur{g})$. 

\begin{corollaire2}
Soient $G$ un groupe abélien fini, $g∈G$ et $n$ un entier.
Les conditions suivantes sont équivalentes.
\begin{enumerate}
\item  $g∈nG$ ;
\item $\chap{G}[n](g)=\{1\}$.
\end{enumerate}
\end{corollaire2}

\begin{corollaire2}
Soient $G$ un groupe abélien fini, $g∈G$ et $n$ un entier. Alors,
$$
N(X^n=g)=∑_{χ∈\chap{G}[n]} χ(g),
$$
où $N(X^n=g)$ désigne le nombre de solution de l'équation $X^n=g$ dans $G$.
\end{corollaire2}

\begin{démo}
Le terme de gauche est égal à $0$ si $g∉nG$ ;
il est égal à $\#G[n]$ dans le cas contraire car deux solutions
diffèrent d'un élément de $G[n]$. 
Notons $\sur{g}$ l'image de $g$ dans $G/nG$. 
Le terme de droite se réécrit 
$$
∑_{\sur{χ}∈\chap{G/nG}} \sur{χ}(\sur{g}).
$$
D'après \ref{lemme-orthogonalite-caracteres}, cette somme vaut $0$ si $\sur{g}≠e$
(c'est-à-dire $g∉nG$) et $\#\chap{G/nG}$ sinon. Puisque $\chap{G/nG}≅\chap{G}[n]≅G[n]$,
l'égalité avec le terme de gauche en résulte.
\end{démo}



\subsubsection{}
Soit $F$ un corps \emph{fini}. Rappelons que le groupe multiplicatif $F^×$ est \emph{cyclique}
(\ref{cyclicite-groupe-multiplicatif-corps}).
%Si $n$ est un entier, la condition $n|d$
%du paragraphe précédent est équivalente à l'égalité $\#μ_n(F)=n$ ou encore à l'inclusion
%$μ_n(\sur{F})⊂F$.
Fixons un entier $d≥0$, des coefficients $c₀,\dots,c_d,b∈F^×$ et des exposants
$n=(n₀,\dots,n_d)$ tous non nuls. On s'intéresse dorénavant au nombre $N=N(c₀X₀^{n₀}+\cdots+c_d X_d^{n_d}=b)$
de solution de cette équation dans $F$ et ses sur-corps. On note $A$ la $F$-algèbre $F^{d+1}$.
Soit $L$ la forme linéaire sur $A$ définie par $L(a)=∑_i c_i a_i$, où 
$a=(a₀,\dots,a_d)∈F^{d+1}$. 
\subsubsection{}L'égalité suivante est tautologique :
$$N=∑_{\substack{a∈A\\ L(a)=b}} N(X₀^{n₀}=a₀)\cdots N(X_d^{n_d}=a_d).$$
D'après les résultats des paragraphes précédents, chaque 
entier $N(X_i^{n_i}=a_i)$ est égal à la somme
$∑_{χ∈\chap{F^×}[n_i]} χ(a_i)$. 

\begin{quote}
\emph{A priori}, cette formule n'a 
de sens que pour $a_i≠0$, elle reste pourtant vraie si l'on décrète que $χ(0)$
est nul si $χ≠1$ et égal à un sinon.
\end{quote}

Ainsi, en développant l'expression $\big(∑_{χ₀^{n₀}=1} χ(a₀)\big)\cdots
\big(∑_{χ_d^{n_d}=1} χ(a_d)\big)$ et en sommant sur les $a∈A$ tels que $L(a)=b$,
on trouve :
$$
(\star)\ N=(\# F)^d+∑_{χ=(χ₀,\dots,χ_d)≠1} \big(∑_{\substack{a∈A\\ L(a)=b}} χ₀(a₀)\cdots χ_d(a_d)\big),
$$
où la première somme porte sur les caractères comme ci-dessus, supposés
non tous triviaux. En effet, la contribution de $χ₀=\cdots=χ_d=1$
est égale au cardinal de l'hyperplan affine $L^{-1}(b)$.

Par commodité, on notera par la suite $χ₀(a₀)\cdots χ_d(a_d)=:χ(a)$.

\begin{lemme2}
Si certains des $χ_i$ sont triviaux, mais pas tous, la somme
$$∑_{\substack{a∈A\\ L(a)=b}} χ₀(a₀)\cdots χ_d(a_d)$$ est \emph{nulle}.
\end{lemme2}

\begin{démo}
Soit $χ=(χ₀,\dots,χ_d)$ comme dans l'énoncé et considérons 
l'algèbre quotient $A↠A'$ de $A$ correspondant aux facteurs non triviaux.
Tautologiquement, $χ(a)=χ'(a')$ où $a'$ est l'image de $a$ dans $A'$ et $χ'$
est la famille de caractères (tous) non triviaux correspondante.
La somme à évaluer est donc égale à $∑_{\substack{a∈A\\ L(a)=b}} χ'(a')$.
Elle est égale à $∑_{a'∈A'} \big(χ'(a')\cdot \#\{a∈A,a\mapsto a', L(a)=b\}\big)$.
Puisque pour tout $a'$, $\{a∈A,a\mapsto a', L(a)=b\}$ est un espace
affine non vide (car $A'≠A$) de dimension donc de cardinal indépendants de $a'$,
il suffit de montrer que $∑_{a'∈A'} χ'(a')=0$.
Puisque les constituants de $χ'$ sont tous non triviaux, elle
est égale à $∑_{a'∈{A'}^×} χ'(a')$. D'après
\ref{variante-orthogonalite-caracteres}, cette somme est nulle.
\end{démo}

\subsubsection{Nouveaux caractères}Soit $A↠A'$ comme dans la démonstration. En passant aux unités,
on obtient un morphisme induit $A^×↠{A'}^×$ d'où une injection
$\chap{{A'}^×}↪\chap{A^×}$. La proposition précédente affirme
que la contribution d'un caractère de l'image est nulle.
En d'autres termes, seuls contribuent les caractères qui ne sont pas induits
par une sous-algèbre quotient \emph{stricte}.
(On a vu en \ref{algebre-diagonalisable} que tous ces quotients sont du type
envisagé dans la démonstration.)

On note $\chap{A^×}^{\mathtextrm{nouv}}$ l'\emph{ensemble} de ces caractères (par oppositions
aux \emph{anciens}, provenant d'une plus petite algèbre).
Généralisant quelque peu la notation habituelle, 
on pose $\chap{A^×}[n]:=\{χ=(χ₀,\dots,χ_d)∈\chap{A^×}, χ_i^{n_i}=1\}$.
(Si $n₀=\dots=n_d$, on retombe sur la définition précédente.)
Enfin, si $E⊂\chap{A^×}$, on note $E[n]$ (resp. $E^{\mathtextrm{nouv}}$ resp.
$E^{\mathtextrm{nouv}}[n]$) son intersection avec le sous-ensemble correspondant
de $\chap{A^×}$. 
Remarquons que si $d+1=\dim_F(A)>1$, tout nouveau caractère de $A^×$ est non
trivial.

\subsubsection{Réécriture de l'égalité ($\star$)}
Si l'on pose $a'=ca$ (c'est-à-dire $a'_i=c_i a_i$ pour $0≤i≤d$), on a bien sûr 
$χ(a)=χ(c)^{-1}χ(a')$, ce qui complique un peu les choses, 
mais la condition $L(a)=b$ s'écrit $∑_i a'_i=b$, c'est-à-dire $\Tr_{A/F}(a')=b$.

Utilisant cette remarque et le lemme précédent, on peut donc
écrire :

$$
N=(\# F)^d+∑_{χ∈\chap{A^×}^{\substack{\mathtextrm{nouv}}[n]\\ χ≠1}} χ^{-1}(c)\big( ∑_{\substack{a∈A^×\\ \Tr(a)=b}}
χ(a)\big).
$$

Rappelons que le terme $(\# F)^d$ correspond au caractère $χ=1$.

Notons $χ_{|F^×}$ la restriction d'un caractère $χ$ de $A^×$ au sous-groupe $F^×$
plongé diagonalement, de sorte que $χ_{|F^×}(x)=∏_i χ_i(x)$.
En écrivant $a_i=a₀a'_i$ ($0<i≤d$), on trouve immédiatement,
pour tout caractère $χ$ de $A^×$ :
$$
∑_{\substack{a∈A^×\\ \Tr(a)=b}} χ(a)=∑_{x∈F^×} \Big(χ_{|F^×}(x) \big(∑_{\substack{a'∈{A'}^×\\ \Tr(a')=\frac{b}{x}-1}} χ'(a')\big)\Big),
$$
où $χ'=(χ₁,\dots,χ_d)$. 

Supposons $b=0$. La somme sur $a'$ ne dépend pas de $x$ et
$∑_{\substack{a∈A^×\\ \Tr(a)=0}} χ(a)$ est un multiple de $∑_{x∈F^×} χ_{|F^×}(x)$,
nul si $χ_{|F^×}$ est non trivial. On peut donc se restreindre pour le calcul de $N$
aux caractères de $A^×$ \emph{diagonalement triviaux}, c'est-à-dire
aux caractères de $A^×/F^×$.

La condition $\Tr(a)=0$ ($a∈A^×$) étant invariante par multiplication
par un scalaire $λ∈F^×$, il est licite de considérer la condition
$\Tr(x)=0$ dans $A^×/F^×$.

Nous avons établi la proposition suivante.

\begin{proposition2}
Soient $F$ un corps fini de cardinal $q$, $d≥0$ un entier, $c₀,\dots,c_d∈F^×$, et $n₀,\dots,n_d≥1$.
Alors,
$$
N(∑_i c_i X_i^{n_i}=0)=q^d+(q-1)∑_{\substack{x∈A^×/F^×,\Tr(a)=0 \\ χ∈\chap{A^×/F^×}^{\mathtextrm{nouv}}[n], χ≠1}} χ(c)χ^{-1}(x).
$$
\end{proposition2}

Le facteur $(q-1)$ provient du fait que chaque $x∈A^×/F^×$,
a exactement $(q-1)$ antécédents dans $A^×$.


\subsection{Sommes de Jacobi, sommes de Gauß}

Dans tout ce paragraphe, $F$ désigne un corps fini, de cardinal $q$.
Nous dirons qu'une $F$-algèbre isomorphe à un produit fini de corps
finis est une « $F$-algèbre étale ». Ceci est conforme
avec la terminologie introduite en \refext{Alg}{etale}.

\begin{définition2}\label{definition-somme-Jacobi}
Soit $A$ une $F$-algèbre \emph{étale} de rang $d+1$.
Pour tout caractère non trivial $χ∈\chap{A^×/F^×}$, on pose
$$
J(χ)=(-1)^{d-1}∑_{\substack{x∈A^×/F^×\\ \Tr(x)=0}} χ^{-1}(x).
$$
\end{définition2}

Une telle somme est appelée \emph{somme de Jacobi}.

Le cas qui nous intéresse particulièrement ici est le cas où $A=F^{d+1}$.
À $χ$ correspondent $d+1$ caractères $(χ₀,\dots,χ_d)$ de $F^×$, non tous triviaux,
de produit trivial. Dans ce cas, 
$$
J(χ)=(-1)^{d-1}∑_{\substack{x₁,\dots,x_d∈F^×\\ ∑_i x_i=-1}} χ₁^{-1}(x₁)\cdots
χ_d^{-1}(x_d).
$$

Dans ce langage, la proposition précédente (où l'on suppose $b=0$) se
reformule :
$$
N=q^d+(-1)^{d-1}(q-1)∑_χ χ(c)J(χ), 
$$
où $χ$ parcourt le sous-ensemble $\chap{A^×/F^×}^{\mathtextrm{nouv}}[n]$.

\subsubsection{Le cas $b$ quelconque}\label{formule-b-quelconque}
Comme pour $x∈F^×$, on a $x^{q-1}=1$, il vient :
$$
N(c₀X₀^{n₀}+\cdots+c_{d}X_d^{n_d}-bX_{d+1}^{q-1}=0)=
(q-1)N(c₀X₀^{n₀}+\cdots+c_{d}X_d^{n_d}=b)+N(c₀X₀^{n₀}+\cdots+c_{d}X_d^{n_d}=0).
$$

D'où (pour $b$ non nul)
$$
N=q^d+(-1)^d\big(∑_{χ'} χ'(c,-b)J(χ')-∑_χ χ(c)J(χ)\big),
$$
où la première somme se fait relativement à l'algèbre $A'=A×F$, 
$χ'$ parcourt l'ensemble $\chap{{A'}^×/F^×}^{\mathtextrm{nouv}}[(n,q-1)]$
et $χ$ parcourt l'ensemble $\chap{A^×/F^×}^{\mathtextrm{nouv}}[n]$.

(Remarquer que $q^{d+1}-q^d=(q-1)q^d$.)

\begin{lemme2}
Soit $ζ_p$ une racine primitive $p$-ème de l'unité.
Pour tout caractère \emph{additif} $ψ$ de $F$, il existe
un unique $a∈F$ tel que $ψ(x)=ζ_p^{\Tr_{F/\FF_p}(ax)}$.
\end{lemme2}

\begin{démo}
On se ramène immédiatement à montrer que toute forme linéaire $f:F→\FF_p$ est
de la forme $x\mapsto \Tr_{F/\FF_p}(ax)$. Cela résulte du fait que 
la trace est non-dégénérée (l'extension $F/\FF_p$ est étale ; cf.
\refext{Alg}{pot-diag=geom-red=f-net} (v)).
% si $\Tr_{F/\FF_p}(ax)=0$ pour tout $x∈F$, alors, $a=0$. 
%Ce dernier point résulte à son tour du fait que la trace est surjective
%et, de façon équivalente, non nulle : le polynôme $X+X^p+\cdots+X^{p^{r-1}}$,
%qui a au plus $p^{r-1}$ racines dans $F$ (supposé de degré $r$ sur $\FF_p$), 
%ne peut donc s'annuler identiquement sur $F$. (C'est vrai plus généralement pour
%toute extension finie séparable de corps.)
\end{démo}


\begin{définition2}\label{definition-somme-Gauss}
Soit $A$ une $F$-algèbre étale de rang $d$, $ψ$ un caractère
(\emph{additif}) non trivial de $F$ et $χ$ un caractère de $A^×$.
On pose 
$$
𝔤(χ,ψ)=(-1)^{d}∑_{a∈A^×} ψ\big(\Tr_{A/F}(a)\big)χ^{-1}(a).
$$
\end{définition2}

Une telle somme est appelée \emph{somme de Gauß}. Elles semblent
avoir été introduites par Cauchy.
Par la suite, nous noterons $ψ_A$ le caractère (additif) $ψ\circ \Tr_{A/F}$.

Remarquons que $𝔤(χ,ψ)∈𝐐(ζ_p,ζ_{q-1})$.

\subsubsection{}\label{factorisation-somme-Gauss}Si $A$ est un produit de corps $K_i$, de degré $d_i$ sur $F$, on montre immédiatement l'égalité
$$
𝔤(χ,ψ)=ε(A)∏_i 𝔤(χ_i,ψ_{K_i}),
$$
où $ε(A)=(-1)^{∑_i (d_i+1)}$.

Le lien entre sommes de Jacobi et sommes de Gauß est donné par la formule
suivante, qui nous permettra bientôt de calculer le module
des sommes de Jacobi. Rappelons que si $A$ est une $F$-algèbre, tout caractère
de $A^×/F^×$ peut-être vu comme un caractère de $A^×$.

\begin{proposition2}\label{proposition-Gauss-Jacobi}
Soient $A$ une $F$-algèbre étale 
Pour tout un caractère non trivial $χ$ de $A^×/F^×$, 
et tout caractère (additif) non trivial $ψ$ de $F$,
on a l'égalité suivante :
$$
qJ(χ)=𝔤(χ,ψ).
$$
\end{proposition2}

\begin{démo}
On a :
$$
𝔤(χ,ψ)=(-1)^{\dim_F(A)}∑_{x∈A^×/F^×} \big(χ^{-1}(x)∑_{a\mapsto x} ψ_A(a)\big),
$$
où $a$ parcourt l'ensemble des relèvements de $x$ à $A^×$.
Si $\Tr(x)=0$, $∑_{a\mapsto x} ψ_A(a)=(q-1)$ ; dans le
cas contraire, elle vaut $∑_{t∈F^×} ψ(t)=-1$ (car $∑_{t∈F} ψ(t)=0$).
Ainsi, 
$$
𝔤(χ,ψ)=(-1)^{\dim_F(A)}\big(q ∑_{\substack{x∈A^×/F^×\\ \Tr(x)=0}} χ^{-1}(x) -
\underbrace{∑_{x∈A^×/F^×} χ^{-1}(x)}_{0}\big).
$$
\end{démo}

\begin{proposition2}
Soient $A$ une $F$-algèbre étale, $ψ$ un caractère (additif) non trivial
de $F$ et $χ∈\chap{A^×}^{\mathtextrm{nouv}}$ non trivial.
Alors, 
$$
|𝔤(χ,ψ)|=\sqrt{\# A}.
$$
\end{proposition2}

\begin{démo}
En faisant le changement de variable $y=xz$ dans la 
formule
$$
|𝔤(χ,ψ)|²=𝔤(χ,ψ)\sur{𝔤(χ,ψ)}=∑_{x,y∈{A'}^×}χ(\frac{y}{x})ψ\big(\Tr_{A'/F}(x-y)\big),
$$
on trouve immédiatement
$$
|𝔤(χ,ψ)|^2=∑_{x,z∈{A'}^×} χ(z)ψ(x(1-z))=∑_z χ(z)\Big(∑_x ψ\big(x(1-z)\big)\Big).
$$
Si $z=1$, la somme $∑_x ψ\big(x(1-z)\big)=∑_x 1$ vaut $\# {A'}^×$.
Si $A'$ est un \emph{corps} et $z≠1$, elle vaut $∑_{y∈{A'}^×}
ψ(y)=\big(∑_{y∈A'}ψ(y)\big)-1=-1$. Finalement, si $A'$ est un corps,
$$
|g|²=\# {A'}^× - ∑_{\substack{z≠1\\ z∈{A'}^×}} χ(z)=\# {A'}^×+1=\# A'.
$$
Le cas général se ramène à ce cas particulier grâce à la formule
\ref{factorisation-somme-Gauss}.
\end{démo}

\begin{corollaire2}
$$
|N(a₀X₀^{n₀}+\cdots+a_d X_d^{n_d}=0)-q^d|≤C_n q^{\frac{d+1}{2}},
$$
où $C_n$ est une constante explicite ne dépendant que de $n$.
De plus, $C_n≤∏_i n_i$.
\end{corollaire2}

\begin{démo}
Les deux propositions précédentes montrent que pour $A$ de dimension $d+1$ sur $F$,
et tout nouveau caractère non trivial, $|qJ(χ)|=q^{\frac{d+1}{2}}$.
La constante $C_n$ n'est autre que le cardinal des nouveaux
caractères de ${F^{d+1}}^×/F^×$ tués par $n$ et non triviaux.
C'est aussi le nombre de $(d+1)$-uplets de rationnels $0<α_i<1$
tels que $n_i α_i∈𝐙$ et $∑_i α_i∈𝐙$.
\end{démo}

Le lecteur exhibera sans peine une majoration semblable dans 
le cas $b≠0$.

\subsubsection{}À faire :

— Lien Gauß ↔ transformée de Fourier discrète et
fonctions $Γ$. (De même : Jacobi ↔ Bessel et $𝔤_{χ}
𝔤_{η}=𝔤_{χ η} J(χ,η)$ ↔ $Γ(x) Γ(y)=Γ(x+y)B(x,y)$.  Parseval. \XXX



— Montrer que transformée de Gauß puissance $n$ = somme de Kloosterman

— Hasse-Davenport \XXX

\begin{théorème2}[Hasse-Davenport]
\label{Hasse-Davenport}
Soit $F'$ une extension finie de $F$ de degré $r$. Alors,
$$
𝔤(χ_{F'},ψ_{F'})=𝔤(χ,ψ)^r.
$$
\end{théorème2}

\begin{démo}
Cf. \cite[chap. 11, §4]{Ireland-Rosen},
ou, mieux, SGA4½, [Sommes trigonométriques], ¶1.15.
\end{démo}

\subsection{Applications : cardinal des sphères, polygones réguliers et
réciprocité quadratique}

\subsubsection{Notations}

Soit $F$ un corps fini cardinal $q$ et de caractéristique $p≠2$. Le groupe $F^×$ a donc un unique
sous-groupe d'indice deux ; on note $χ_{\mathtextrm{quad}}$ le caractère
correspondant. On a donc $χ_{\mathtextrm{quad}}(x)=1$ si $x∈{F^×}²$ et $-1$ sinon.

C'est le seul caractère non trivial de $2$-torsion, de sorte que l'ensemble
des nouveaux caractères de $2$-torsion de $F^d$ est soit vide soit réduit à un seul
élément, suivant la parité de $d$.

Dans tout ce paragraphe, nous fixons une racine primitive $p$-ème 
de l'unité $ζ_p$ et considérons le caractère additif non trivial associé :
$ψ(x)=ζ_p^{\Tr_{F/\FF_p}(x)}$. Nous notons $g_{\mathtextrm{quad}}$ la 
somme de Gauß associée à ce caractère additif et au caractère (multiplicatif) quadratique.

\begin{proposition2}
\label{proposition-cardinal-spheres}
Soient $d≥0$ un entier et $N$ le nombre de solutions de l'équation 
$X₀²+\cdots+X_d²=1$.
\begin{enumerate}
\item $g_{\mathtextrm{quad}}²=qχ_{\mathtextrm{quad}}(-1)$ ;
\item $χ_{\mathtextrm{quad}}(-1)=(-1)^{\frac{q-1}{2}}$ ;
\item $N=q^d+χ_{\mathtextrm{quad}}(-1)^{\frac{d}{2}} q^{\frac{d}{2}}$ si $d$ est
pair ;
\item $N=q^d+χ_{\mathtextrm{quad}}(-1)^{\frac{d+1}{2}} q^{\frac{d-1}{2}}$ si $d$ est
impair. 
\end{enumerate}
\end{proposition2}

Rappelons que $χ_{\mathtextrm{quad}}(-1)^n=χ_{\mathtextrm{quad}}\big((-1)^n\big)$ vaut
$1$ si $(-1)^n$ est un carré dans $F$, $-1$ sinon.

\begin{démo}
(i) résulte de la formule générale : 
$$𝔤(χ,ψ)𝔤(\sur{χ},ψ)=χ(-1)^{-1}𝔤(χ,ψ)\sur{𝔤(χ,ψ)}=χ(-1)q.$$
(ii) Si $x∈{F^×}²$, $x^{\frac{q-1}{2}}=1$ et vice-versa pour des raisons
de cardinalité. Ainsi, $χ_{\mathtextrm{quad}}(x)=x^{\frac{q-1}{2}})$,
égalité ayant lieu dans $\{±1\}$, plongé dans $\mathbf{U}$ (terme
de gauche) et $F^×$ (terme de droite).
(iii) et (iv) résultent de la formule générale exprimant $N$ comme
une somme, de l'égalité $qJ=g$.
Pour (iii), on utilise également l'égalité
$χ_{\mathtextrm{quad}}(-1)\frac{g_{\mathtextrm{quad}}^{d+2}}{p}=χ_{\mathtextrm{quad}}(-1)^{\frac{d}{2}}q^{\frac{d}{2}}$,
qui découle de (i). L'égalité (iv) est semblable et laissée au lecteur.
\end{démo}

\begin{remarque2}
Insistons sur le caractère élémentaire de ces formules. 
Puisque $N(X²=a)=1+χ_{\mathtextrm{quad}}(a)$, en tire
$N=q^d+∑_{a₀+\cdots+a_d=1} ∏_i χ_{\mathtextrm{quad}}(a_i)$. Le second
terme est, au signe près, une somme de Jacobi.
Ce calcul a été fait bien avant le cas d'une hypersurface diagonale
générale, dû à Weil.
\end{remarque2}

\commentaire{Il faudrait dire que la convolution des $χ_i$
est $J ⋅ ∏_i χ_i$ si bien que l'on a $∏ ℱ(χ_i)=J ℱ(∏_i
χ_i)$, ce qui donne immédiatement [via Parseval] la norme
de $J$ suivant que $∏_i χ_i$ est trivial ou non (cf. $d$
pair ou impair).}

Généralisation : hypersurface diagonale.
$N_r$ est une somme de puissance $r$-ièmes. \XXX.
On verra en \refext{AC}{} une application à la rationalité
de la fonction $ζ$.

\subsubsection{Constructiblité des polygones réguliers}

Dans ce court paragraphe, on donne une démonstration élémentaire
de la constructiblité à la règle et au compas des polygones réguliers
à $p$ côtés si $p-1$ est une puissance de deux :
nous allons démontrer qu'il existe sous cette hypothèse une
suite d'extensions $𝐐=K₀⊂\cdots ⊂K_i ⊂ K_{i+1} ⊂\cdots ⊂K_n=𝐐(ζ_p)$,
avec $[K_{i+1}:K_i]=2$.

Posons $S=∑_χ 𝔤(χ,ψ)$, où $χ$ parcourt $\chap{F^×}$.
Par définition, $S=-∑_{x∈F^×} \big( ∑_χ χ(x)\big) ψ(x)$. 
Puisque $∑_χ χ(x)=0$ pour $x≠1$, $p-1$ sinon, et $ψ(1)=ζ_p$, on a donc
l'égalité 
$$
S=(1-p)ζ_p,
$$
de sorte que $𝐐(ζ_p)=𝐐(S)$.

Une somme de nombres constructibles étant constructible \XXX, il suffit donc de démontrer 
que chaque $𝔤(χ,ψ)$ est constructible, si $p-1$ est une puissance de deux, ce que nous supposerons dorénavant.

Observons que pour tout entier $m≥1$, un nombre $g$ est constructible si et seulement si $g^{2^m}$ l'est.
Or, tout caractère de $F^×$ est d'ordre divisant $p-1$ donc de la forme $2^m$,
$m≥0$, si bien que l'égalité $𝔤(χ,ψ)^{2^m}=pJ((χ,\dots,χ))$ (cf. \ref{proposition-Gauss-Jacobi})
ramène le problème à la constructibilité des sommes de Jacobi.
Ces dernières appartiennent à $𝐐(μ_{p-1})$ ; elles sont donc constructibles.
(Le cas $m=0$, c'est-à-dire $χ=1$, est à traiter séparément. Il est trivial.)

Selon la légende, c'est cette découverte — sensationnelle à l'époque —
qui aurait décidé Gauß (alors âgé d'un peu moins de 19 ans) à devenir mathématicien, et non linguiste.
Sa démonstration est exposée en détail dans ses \emph{disquisitiones arithmeticæ} (recherches
arithmétiques) \cite{Disquisitiones@Gauss}, §7. La découverte elle-même 
semble dater du 30 mars 1796. C'est la première entrée dans son
fameux \emph{Tagebuch} (\cite{Tagebuch@Gauss}) :
\begin{quote}
{\addfontfeatures{Ligatures=Historic}
Principia quibus innititur sectio circuli, ac divisibilitas eiusdem
geometrica in septemdecim partes etc.}
\end{quote}

On trouvera dans \refext{Radicaux}{racine-17e-de-1} un calcul
explicite lorsque $p=17$.

\subsubsection{Réciprocité quadratique}
Cf. \ref{reciprocite-quadratique}.

Soit $ℓ≠p$ un nombre premier impair.
Notons $χ=(χ_{\mathtextrm{quad}},\dots,χ_{\mathtextrm{quad}})$
le caractère de ${F^{ℓ+1}}^×$, où $F=\FF_p$. Il est nouveau, non trivial
mais diagonalement trivial car $χ_{\mathtextrm{quad}}^{ℓ+1}=1$.

Il résulte de la formule $pJ=g$ (\ref{proposition-Gauss-Jacobi}) et 
du calcul de $g²$ (\ref{proposition-cardinal-spheres}, (i-ii)) que l'on a
l'égalité :
  
$$p^{\frac{ℓ-1}{2}}(-1)^{(\frac{p-1}{2})(\frac{ℓ+1}{2})}=J(χ)=χ_{\mathtextrm{quad}}(-1)^ℓ∑_{∑x_i=1}χ_{\mathtextrm{quad}}(x₁)\cdots
χ_{\mathtextrm{quad}}(x_ℓ).
$$ 

L'égalité de droite est une traduction immédiate de la définition
des sommes de Jacobi. (On utilise le fait que
$χ_{\mathtextrm{quad}}=χ_{\mathtextrm{quad}}^{-1}$.)
En faisant passer le terme $χ_{\mathtextrm{quad}}(-1)^ℓ$ à gauche, on trouve :
$$
p^{\frac{ℓ-1}{2}}(-1)^{(\frac{p-1}{2})(\frac{ℓ-1}{2})}=∑_{\substack{∑x_i=1\\ x_i∈𝐅_p^×}}χ_{\mathtextrm{quad}}(x₁)\cdots
χ_{\mathtextrm{quad}}(x_ℓ).
$$

La somme de droite est une somme d'entiers égaux à $±1$.
Elle est congrue à $χ_{\mathtextrm{quad}}(ℓ)$ modulo $ℓ$ pour
la raison suivante. L'ensemble de sommation est naturellement un $𝐙/ℓ$-ensemble (action
par permutation cyclique des coordonnées) et la fonction
sommée est invariante par cette action. Il en résulte que,
modulo $ℓ$, seuls les points fixes contribuent. L'unique point
fixe est donné par $x₁=\cdots=x_ℓ=\frac{1}{ℓ}∈F^×$. Sa
contribution est $χ_{\mathtextrm{quad}}(ℓ)∈\{±1\}$.

Puisque $χ_{\mathtextrm{quad}}(ℓ)=(\frac{ℓ}{p})$ et que d'autre part,
modulo $ℓ$, $p^{\frac{ℓ-1}{2}}\equiv (\frac{p}{ℓ})$, on en tire :

\[
(\frac{ℓ}{p})(\frac{p}{ℓ})=(-1)^{(\frac{p-1}{2})(\frac{ℓ-1}{2})}.
\]

C'est la fameuse \emph{loi de réciprocité quadratique}.


\ifx\danslelivre\undefined
\bibliography{../biblio/bibliographie-livre}
\bibliographystyle{../biblio/style-bib-livre}
Git: \showgitstatus
\end{document}
\else
\endgroup
\fi