Eine Fermat-Zahl, benannt nach dem französischen Mathematiker Pierre de Fermat, ist eine Zahl der Form
mit einer ganzen Zahl . Die ersten Fermat-Zahlen lauten 3, 5 und 17.
Im August 1640 vermutete Fermat fälschlicherweise, dass alle Zahlen dieser Form (die später nach ihm benannt wurden) Primzahlen seien. Dies wurde jedoch 1732 von Leonhard Euler widerlegt, der zeigte, dass schon die sechste Fermatzahl F5 durch 641 teilbar ist. Man kennt außer den ersten fünf (3, 5, 17, 257, 65537) derzeit keine weitere Fermat-Zahl, die gleichzeitig Primzahl ist, und vermutet, dass es außer diesen fünf Zahlen auch keine weitere gibt (siehe Abschnitt weiter unten).
Fermat-Zahlen Bearbeiten
Die ersten Fermat-Zahlen lauten und .
Eine etwas längere Liste bis findet man in der folgenden aufklappbaren Box.
Liste der ersten 15 Fermat-Zahlen
| n | Dezimal- stellen von Fn | Fn |
|---|---|---|
| 0 | 1 | 3 |
| 1 | 1 | 5 |
| 2 | 2 | 17 |
| 3 | 3 | 257 |
| 4 | 5 | 65.537 |
| 5 | 10 | 4.294.967.297 |
| 6 | 20 | 18.446.744.073.709.551.617 |
| 7 | 39 | 340.282.366.920.938.463.463.374.607.431.768.211.457 |
| 8 | 78 | 115.792.089.237.316.195.423.570.985.008.687.907.853.269.984.665.640.564.039.457.584.007.913.129.639.937 |
| 9 | 155 | 13.407.807.929.942.597.099.574.024.998.205.846.127.479.365.820.592.393.377.723.561.443.721.764.030.073.546.976.801.874.298.166.903.427.690.031.858.186.486.050.853.753.882.811.946.569.946.433.649.006.084.097 |
| 10 | 309 | 179.769.313.486.231.590.772.930.519.078.902.473.361.797.697.894.230.657.273.430.081.157.732.675.805.500.963.132.708.477.322.407.536.021.120.113.879.871.393.357.658.789.768.814.416.622.492.847.430.639.474.124.377.767.893.424.865.485.276.302.219.601.246.094.119.453.082.952.085.005.768.838.150.682.342.462.881.473.913.110.540.827.237.163.350.510.684.586.298.239.947.245.938.479.716.304.835.356.329.624.224.137.217 |
| 11 | 617 | 32.317.006.071.311.007.300.714.876.688.669.951.960.444.102.669.715.484.032.130.345.427.524.655.138.867.890.893.197.201.411.522.913.463.688.717.960.921.898.019.494.119.559.150.490.921.095.088.152.386.448.283.120.630.877.367.300.996.091.750.197.750.389.652.106.796.057.638.384.067.568.276.792.218.642.619.756.161.838.094.338.476.170.470.581.645.852.036.305.042.887.575.891.541.065.808.607.552.399.123.930.385.521.914.333.389.668.342.420.684.974.786.564.569.494.856.176.035.326.322.058.077.805.659.331.026.192.708.460.314.150.258.592.864.177.116.725.943.603.718.461.857.357.598.351.152.301.645.904.403.697.613.233.287.231.227.125.684.710.820.209.725.157.101.726.931.323.469.678.542.580.656.697.935.045.997.268.352.998.638.215.525.166.389.437.335.543.602.135.433.229.604.645.318.478.604.952.148.193.555.853.611.059.596.230.657 |
| 12 | 1234 | 1.044.388.881.413.152.506.691.752.710.716.624.382.579.964.249.047.383.780.384.233.483.283.953.907.971.557.456.848.826.811.934.997.558.340.890.106.714.439.262.837.987.573.438.185.793.607.263.236.087.851.365.277.945.956.976.543.709.998.340.361.590.134.383.718.314.428.070.011.855.946.226.376.318.839.397.712.745.672.334.684.344.586.617.496.807.908.705.803.704.071.284.048.740.118.609.114.467.977.783.598.029.006.686.938.976.881.787.785.946.905.630.190.260.940.599.579.453.432.823.469.303.026.696.443.059.025.015.972.399.867.714.215.541.693.835.559.885.291.486.318.237.914.434.496.734.087.811.872.639.496.475.100.189.041.349.008.417.061.675.093.668.333.850.551.032.972.088.269.550.769.983.616.369.411.933.015.213.796.825.837.188.091.833.656.751.221.318.492.846.368.125.550.225.998.300.412.344.784.862.595.674.492.194.617.023.806.505.913.245.610.825.731.835.380.087.608.622.102.834.270.197.698.202.313.169.017.678.006.675.195.485.079.921.636.419.370.285.375.124.784.014.907.159.135.459.982.790.513.399.611.551.794.271.106.831.134.090.584.272.884.279.791.554.849.782.954.323.534.517.065.223.269.061.394.905.987.693.002.122.963.395.687.782.878.948.440.616.007.412.945.674.919.823.050.571.642.377.154.816.321.380.631.045.902.916.136.926.708.342.856.440.730.447.899.971.901.781.465.763.473.223.850.267.253.059.899.795.996.090.799.469.201.774.624.817.718.449.867.455.659.250.178.329.070.473.119.433.165.550.807.568.221.846.571.746.373.296.884.912.819.520.317.457.002.440.926.616.910.874.148.385.078.411.929.804.522.981.857.338.977.648.103.126.085.903.001.302.413.467.189.726.673.216.491.511.131.602.920.781.738.033.436.090.243.804.708.340.403.154.190.337 |
| 13 | 2467 | 1.090.748.135.619.415.929.462.984.244.733.782.862.448.264.161.996.232.692.431.832.786.189.721.331.849.119.295.216.264.234.525.201.987.223.957.291.796.157.025.273.109.870.820.177.184.063.610.979.765.077.554.799.078.906.298.842.192.989.538.609.825.228.048.205.159.696.851.613.591.638.196.771.886.542.609.324.560.121.290.553.901.886.301.017.900.252.535.799.917.200.010.079.600.026.535.836.800.905.297.805.880.952.350.501.630.195.475.653.911.005.312.364.560.014.847.426.035.293.551.245.843.928.918.752.768.696.279.344.088.055.617.515.694.349.945.406.677.825.140.814.900.616.105.920.256.438.504.578.013.326.493.565.836.047.242.407.382.442.812.245.131.517.757.519.164.899.226.365.743.722.432.277.368.075.027.627.883.045.206.501.792.761.700.945.699.168.497.257.879.683.851.737.049.996.900.961.120.515.655.050.115.561.271.491.492.515.342.105.748.966.629.547.032.786.321.505.730.828.430.221.664.970.324.396.138.635.251.626.409.516.168.005.427.623.435.996.308.921.691.446.181.187.406.395.310.665.404.885.739.434.832.877.428.167.407.495.370.993.511.868.756.359.970.390.117.021.823.616.749.458.620.969.857.006.263.612.082.706.715.408.157.066.575.137.281.027.022.310.927.564.910.276.759.160.520.878.304.632.411.049.364.568.754.920.967.322.982.459.184.763.427.383.790.272.448.438.018.526.977.764.941.072.715.611.580.434.690.827.459.339.991.961.414.242.741.410.599.117.426.060.556.483.763.756.314.527.611.362.658.628.383.368.621.157.993.638.020.878.537.675.545.336.789.915.694.234.433.955.666.315.070.087.213.535.470.255.670.312.004.130.725.495.834.508.357.439.653.828.936.077.080.978.550.578.912.967.907.352.780.054.935.621.561.090.795.845.172.954.115.972.927.479.877.527.738.560.008.204.118.558.930.004.777.748.727.761.853.813.510.493.840.581.861.598.652.211.605.960.308.356.405.941.821.189.714.037.868.726.219.481.498.727.603.653.616.298.856.174.822.413.033.485.438.785.324.024.751.419.417.183.012.281.078.209.729.303.537.372.804.574.372.095.228.703.622.776.363.945.290.869.806.258.422.355.148.507.571.039.619.387.449.629.866.808.188.769.662.815.778.153.079.393.179.093.143.648.340.761.738.581.819.563.002.994.422.790.754.955.061.288.818.308.430.079.648.693.232.179.158.765.918.035.565.216.157.115.402.992.120.276.155.607.873.107.937.477.466.841.528.362.987.708.699.450.152.031.231.862.594.203.085.693.838.944.657.061.346.236.704.234.026.821.102.958.954.951.197.087.076.546.186.622.796.294.536.451.620.756.509.351.018.906.023.773.821.539.532.776.208.676.978.589.731.966.330.308.893.304.665.169.436.185.078.350.641.568.336.944.530.051.437.491.311.298.834.367.265.238.595.404.904.273.455.928.723.949.525.227.184.617.404.367.854.754.610.474.377.019.768.025.576.605.881.038.077.270.707.717.942.221.977.090.385.438.585.844.095.492.116.099.852.538.903.974.655.703.943.973.086.090.930.596.963.360.767.529.964.938.414.598.185.705.963.754.561.497.355.827.813.623.833.288.906.309.004.288.017.321.424.808.663.962.671.333.528.009.232.758.350.873.059.614.118.723.781.422.101.460.198.615.747.386.855.096.896.089.189.180.441.339.558.524.822.867.541.113.212.638.793.675.567.650.340.362.970.031.930.023.397.828.465.318.547.238.244.232.028.015.189.689.660.418.822.976.000.815.437.610.652.254.270.163.595.650.875.433.851.147.123.214.227.266.605.403.581.781.469.090.806.576.468.950.587.661.997.186.505.665.475.715.792.897 |
| 14 | 4933 | 1.189.731.495.357.231.765.085.759.326.628.007.130.763.444.687.096.510.237.472.674.821.233.261.358.180.483.686.904.488.595.472.612.039.915.115.437.484.839.309.258.897.667.381.308.687.426.274.524.698.341.565.006.080.871.634.366.004.897.522.143.251.619.531.446.845.952.345.709.482.135.847.036.647.464.830.984.784.714.280.967.845.614.138.476.044.338.404.886.122.905.286.855.313.236.158.695.999.885.790.106.357.018.120.815.363.320.780.964.323.712.757.164.290.613.406.875.202.417.365.323.950.267.880.089.067.517.372.270.610.835.647.545.755.780.793.431.622.213.451.903.817.859.630.690.311.343.850.657.539.360.649.645.193.283.178.291.767.658.965.405.285.113.556.134.369.793.281.725.888.015.908.414.675.289.832.538.063.419.234.888.599.898.980.623.114.025.121.674.472.051.872.439.321.323.198.402.942.705.341.366.951.274.739.014.593.816.898.288.994.445.173.400.364.617.928.377.138.074.411.345.791.848.573.595.077.170.437.644.191.743.889.644.885.377.684.738.322.240.608.239.079.061.399.475.675.334.739.784.016.491.742.621.485.229.014.847.672.335.977.897.158.397.334.226.349.734.811.441.653.077.758.250.988.926.030.894.789.604.676.153.104.257.260.141.806.823.027.588.003.441.951.455.327.701.598.071.281.589.597.169.413.965.608.439.504.983.171.255.062.282.026.626.200.048.042.149.808.200.002.060.993.433.681.237.623.857.880.627.479.727.072.877.482.838.438.705.048.034.164.633.337.013.385.405.998.040.701.908.662.387.301.605.018.188.262.573.723.766.279.240.798.931.717.708.807.901.740.265.407.930.976.419.648.877.869.604.017.517.691.938.687.988.088.008.944.251.258.826.969.688.364.194.133.945.780.157.844.364.946.052.713.655.454.906.327.187.428.531.895.100.278.695.119.323.496.808.703.630.436.193.927.592.692.344.820.812.834.297.364.478.686.862.064.169.042.458.555.136.532.055.050.508.189.891.866.846.863.799.917.647.547.291.371.573.500.701.015.197.559.097.453.040.033.031.520.683.518.216.494.195.636.696.077.748.110.598.284.901.343.611.469.214.274.121.810.495.077.979.275.556.645.164.983.850.062.051.066.517.084.647.369.464.036.640.569.339.464.837.172.183.352.956.873.912.042.640.003.611.618.789.278.195.710.052.094.562.761.306.703.551.840.330.110.645.101.995.435.167.626.688.669.627.763.820.604.342.480.357.906.415.354.212.732.946.756.073.006.907.088.870.496.125.050.068.156.659.252.761.297.664.065.498.347.492.661.798.824.062.312.210.409.274.584.565.587.264.846.417.650.160.123.175.874.034.726.261.957.289.081.466.197.651.553.830.744.424.709.698.634.753.627.770.356.227.126.145.052.549.125.229.448.040.149.114.795.681.359.875.968.512.808.575.244.271.871.455.454.084.894.986.155.020.794.806.980.939.215.658.055.319.165.641.681.105.966.454.159.951.476.908.583.129.721.503.298.816.585.142.073.061.480.888.021.769.818.338.417.129.396.878.371.459.575.846.052.583.142.928.447.249.703.698.548.125.295.775.920.936.450.022.651.427.249.949.580.708.203.966.082.847.550.921.891.152.133.321.048.011.973.883.636.577.825.533.325.988.852.156.325.439.335.021.315.312.134.081.390.451.021.255.363.707.903.495.916.963.125.924.201.167.877.190.108.935.255.914.539.488.216.897.117.943.269.373.608.639.074.472.792.751.116.715.127.106.396.425.081.353.553.137.213.552.890.539.802.602.978.645.319.795.100.976.432.939.091.924.660.228.878.912.900.654.210.118.287.298.298.707.382.159.717.184.569.540.515.403.029.173.307.292.454.391.789.568.674.219.640.761.451.173.600.617.752.186.991.913.366.837.033.887.201.582.071.625.868.247.133.104.513.315.097.274.713.442.728.340.606.642.890.406.496.636.104.443.217.752.811.227.470.029.162.858.093.727.701.049.646.499.540.220.983.981.932.786.613.204.254.226.464.243.689.610.107.429.923.197.638.681.545.837.561.773.535.568.984.536.053.627.234.424.277.105.760.924.864.023.781.629.665.526.314.910.906.960.488.073.475.217.005.121.136.311.870.439.925.762.508.666.032.566.213.750.416.695.719.919.674.223.210.606.724.721.373.471.234.021.613.540.712.188.239.909.701.971.943.944.347.480.314.217.903.886.317.767.779.921.539.892.177.334.344.368.907.550.318.800.833.546.852.344.370.327.089.284.147.501.640.589.448.482.001.254.237.386.680.074.457.341.910.933.774.891.959.681.016.516.069.106.149.905.572.425.810.895.586.938.833.067.490.204.900.368.624.166.301.968.553.005.687.040.285.095.450.484.840.073.528.643.826.570.403.767.157.286.512.380.255.109.954.518.857.013.476.588.189.300.004.138.849.715.883.139.866.071.547.574.816.476.727.635.116.435.462.804.401.112.711.392.529.180.570.794.193.422.686.818.353.212.799.068.972.247.697.191.474.268.157.912.195.973.794.192.807.298.886.952.361.100.880.264.258.801.320.928.040.011.928.153.970.801.130.741.339.550.003.299.015.924.978.259.936.974.358.726.286.143.980.520.112.454.369.271.114.083.747.919.007.803.406.596.321.353.417.004.068.869.443.405.472.140.675.963.640.997.405.009.225.803.505.672.726.465.095.506.267.339.268.892.424.364.561.897.661.906.898.424.186.770.491.035.344.080.399.248.327.097.911.712.881.140.170.384.182.058.601.614.758.284.200.750.183.500.329.358.499.691.864.066.590.539.660.709.069.537.381.601.887.679.046.657.759.654.588.001.937.117.771.344.698.326.428.792.622.894.338.016.112.445.533.539.447.087.462.049.763.409.147.542.099.248.815.521.395.929.388.007.711.172.017.894.897.793.706.604.273.480.985.161.028.815.458.787.911.160.979.113.422.433.557.549.170.905.442.026.397.275.695.283.207.305.331.845.419.990.749.347.810.524.006.194.197.200.591.652.147.867.193.696.254.337.864.981.603.833.146.354.201.700.628.817.947.177.518.115.217.674.352.016.511.172.347.727.727.075.220.056.177.748.218.928.597.158.346.744.541.337.107.358.427.757.919.660.562.583.883.823.262.178.961.691.787.226.118.865.632.764.934.288.772.405.859.754.877.759.869.235.530.653.929.937.901.193.611.669.007.472.354.746.360.764.601.872.442.031.379.944.139.824.366.828.698.790.212.922.996.174.192.728.625.891.720.057.612.509.349.100.482.545.964.152.046.477.925.114.446.500.732.164.109.099.345.259.799.455.690.095.576.788.686.397.487.061.948.854.749.024.863.607.921.857.834.205.793.797.188.834.779.656.273.479.112.388.585.706.424.836.379.072.355.410.286.787.018.527.401.653.934.219.888.361.061.949.671.961.055.068.686.961.468.019.035.629.749.424.086.587.195.041.004.404.915.266.476.272.761.070.511.568.387.063.401.264.136.517.237.211.409.916.458.796.347.624.949.215.904.533.937.210.937.520.465.798.300.175.408.017.538.862.312.719.042.361.037.129.338.896.586.028.150.046.596.078.872.444.365.564.480.545.689.033.575.955.702.988.396.719.744.528.212.984.142.578.483.954.005.084.264.327.730.840.985.420.021.409.069.485.412.320.805.268.520.094.146.798.876.110.414.583.170.390.473.982.488.899.228.091.818.213.934.288.295.679.717.369.943.152.460.447.027.290.669.964.066.817 |
Wegen hat die Fermatzahl doppelt so viele oder um eine weniger als doppelt so viele Stellen wie ihr Vorgänger .
Fermatsche Primzahlen Bearbeiten
Die Idee hinter Fermatschen Primzahlen ist der Satz, dass nur für und für mit prim sein kann:
Beweis des Satzes:
Beweis durch Widerspruch: Man führt die Annahme, dass das zu Beweisende falsch sei, zu einem Widerspruch.
Die Umkehrung dieses Satzes, dass also nicht nur (wegen offensichtlich) , sondern auch jede Fermat-Zahl prim sei, ist falsch. bis sind sogar die einzigen bisher bekannten Fermatschen Primzahlen:
Schon Fermat zeigte, dass diese ersten fünf Fermat-Zahlen Primzahlen sind, und vermutete 1640, dass dies auf alle Fermat-Zahlen zutreffe. Diese Vermutung wurde aber schon 1732 von Leonhard Euler einfach widerlegt, indem er mit 641 einen echten Teiler von F5 = 4.294.967.297 fand.
Man vermutet inzwischen, dass außer den ersten fünf keine weiteren Fermatschen Primzahlen existieren. Diese Vermutung beruht auf statistischen Abschätzungen: Der Primzahlsatz besagt, dass die Anzahl der Primzahlen, die nicht größer als x sind, näherungsweise gleich x / ln x ist. Die Primzahldichte oder Wahrscheinlichkeit dafür, dass Fn als ungerade Zahl eine Primzahl ist, beträgt daher näherungsweise 2 / ln Fn ≈ 3/2n. Die Wahrscheinlichkeit, dass die Fermatzahl Fn oder eine der folgenden Fermatzahlen eine Primzahl ist, ergibt sich durch Summation der geometrische Reihe ungefähr zu 6/2n.
Für verbliebene weder teilweise noch vollständig faktorisierte Fermat-Zahlen ist diese Wahrscheinlichkeit mit etwa 6 · 10−10 mittlerweile aber sehr klein geworden.
Faktorisierungsergebnisse von Fermat-Zahlen Bearbeiten
Die Zahlen F0 bis F4 sind, wie schon Fermat erkannt hat, Primzahlen:
| n | Fermat-Primzahl Fn |
|---|---|
| 0 | 3 |
| 1 | 5 |
| 2 | 17 |
| 3 | 257 |
| 4 | 65537 |
Die Zahlen F5 bis F11 sind entgegen der Vermutung Fermats zusammengesetzt. Sie sind bereits vollständig faktorisiert:
Liste der zusammengesetzten und vollständig faktorisierten Fermat-Zahlen
| n | Entdecker der Faktoren | Primfaktorenzerlegung von Fn |
|---|---|---|
| 5 | Leonhard Euler (1732) | 4.294.967.297 (10 Stellen) = 641 (3 Stellen) × 6.700.417 (7 Stellen) |
| 6 | Clausen (1855), Landry & Le Lasseur (1880) | 18.446.744.073.709.551.617 (20 Stellen) = 274.177 (6 Stellen) × 67.280.421.310.721 (14 Stellen) |
| 7 | Morrison & Brillhart (1970) | 340.282.366.920.938.463.463.374.607.431.768.211.457 (39 Stellen) = 59.649.589.127.497.217 (17 Stellen) × 5.704.689.200.685.129.054.721 (22 Stellen) |
| 8 | Brent & Pollard (1980) | 115.792.089.237.316.195.423.570.985.008.687.907.853.269.984.665.640.564.039.457.584.007.913.129.639.937 (78 Stellen) = 1.238.926.361.552.897 (16 Stellen) × 93.461.639.715.357.977.769.163.558.199.606.896.584.051.237.541.638.188.580.280.321 (62 Stellen) |
| 9 | Western (1903), Lenstra & Manasse (1990) | 13.407.807.929.942.597.099.574.024.998.205.846.127.479.365.820.592.393.377.723.561.443.721.764.030.073.546.976.801.874.298.166.903.427.690.031. 858.186.486.050.853.753.882.811.946.569.946.433.649.006.084.097 (155 Stellen) = 2.424.833 (7 Stellen) × 7.455.602.825.647.884.208.337.395.736.200.454.918.783.366.342.657 (49 Stellen) × 741.640.062.627.530.801.524.787.141.901.937.474.059.940.781.097.519.023.905.821.316.144.415.759.504.705.008.092.818.711.693.940.737 (99 Stellen) |
| 10 | Selfridge (1953), Brillhart (1962), Brent (1995) | 179.769.313.486.231.590.772.930 … 304.835.356.329.624.224.137.217 (309 Stellen) = 45.592.577 (8 Stellen) × 6.487.031.809 (10 Stellen) × 4.659.775.785.220.018.543.264.560.743.076.778.192.897 (40 Stellen) × 130.439.874.405.488.189.727.484 … 806.217.820.753.127.014.424.577 (252 Stellen) |
| 11 | Cunningham (1899), Brent & Morain (1988) | 32.317.006.071.311.007.300.714.8 … 193.555.853.611.059.596.230.657 (617 Stellen) = 319.489 (6 Stellen) × 974.849 (6 Stellen) × 167.988.556.341.760.475.137 (21 Stellen) × 3.560.841.906.445.833.920.513 (22 Stellen) × 173.462.447.179.147.555.430.258 … 491.382.441.723.306.598.834.177 (564 Stellen) |
Ab F12 ist keine Fermat-Zahl mehr vollständig faktorisiert. Die ersten acht lauten:
Liste der ersten acht der nur teilweise faktorisierten Fermat-Zahlen
| n | Entdecker der Faktoren | Primfaktorenzerlegung von Fn |
|---|---|---|
| 12 | Lucas & Perwuschin (1877), Western (1903), Hallyburton & Brillhart (1974), Baillie (1986), Vang, Zimmermann & Kruppa (2010) | 1.044.388.881.413.152.506.691.752.710.716 … 340.403.154.190.337 (1234 Stellen) = 114.689 (6 Stellen) × 26.017.793 (8 Stellen) × 63.766.529 (8 Stellen) × 190.274.191.361 (12 Stellen) × 1.256.132.134.125.569 (16 Stellen) |
| 13 | Hallyburton & Brillhart (1974), Crandall (1991), Brent (1995) | 1.090.748.135.619.415.929.462.984.244.733 … 665.475.715.792.897 (2467 Stellen) = 2.710.954.639.361 (13 Stellen) × 2.663.848.877.152.141.313 (19 Stellen) |
| 14 | Rajala & Woltman (2010) | 1.189.731.495.357.231.765.085.759.326.628 … 290.669.964.066.817 (4933 Stellen) = 116.928.085.873.074.369.829.035.993.834.596.371.340.386.703.423.373.313 (54 Stellen) × zusammengesetzte Zahl (4880 Stellen) |
| 15 | Kraitchik (1925), Gostin (1987), Crandall & van Halewyn (1997) | 1.415.461.031.044.954.789.001.553.027.744 … 104.633.712.377.857 (9865 Stellen) = 1.214.251.009 (10 Stellen) × 2.327.042.503.868.417 (16 Stellen) × 168.768.817.029.516.972.383.024.127.016.961 (33 Stellen) |
| 16 | Selfridge (1953), Crandall & Dilcher (1996) | 2.003.529.930.406.846.464.979.072.351.560 … 895.905.719.156.737 (19729 Stellen) = 825.753.601 (9 Stellen) × 188.981.757.975.021.318.420.037.633 (27 Stellen) |
| 17 | Gostin (1978), Bessell & Woltman (2011) | 4.014.132.182.036.063.039.166.060.606.038 … 318.570.934.173.697 (39457 Stellen) = 31.065.037.602.817 (14 Stellen) × 7.751.061.099.802.522.589.358.967.058.392.886.922.693.580.423.169 (49 Stellen) |
| 18 | Western (1903), Crandall, McIntosh & Tardif (1999) | 16.113.257.174.857.604.736.195.721.184.520 … 349.934.298.300.417 (78914 Stellen) = 13.631.489 (8 Stellen) × 81.274.690.703.860.512.587.777 (23 Stellen) |
| 19 | Riesel (1962), Wrathall (1963), Bessell & Woltman (2009) | 259.637.056.783.100.077.612.659.649.572.688 … 528.226.185.773.057 (157827 Stellen) = 70.525.124.609 (11 Stellen) × 646.730.219.521 (12 Stellen) × 37.590.055.514.133.754.286.524.446.080.499.713 (35 Stellen) |
Von F12 bis F32 und von einigen größeren Fermat-Zahlen ist bekannt, dass sie zusammengesetzt sind – hauptsächlich, weil ein oder mehrere Faktoren gefunden wurden. Von zwei Fermat-Zahlen (F20 und F24) kennt man zwar keinen Faktor, hat aber auf andere Art gezeigt, dass sie zusammengesetzt sind.
Für F14 wurde am 3. Februar 2010 ein Faktor veröffentlicht, für F22 am 25. März 2010.
Die kleinste Fermat-Zahl, von der bislang nicht bekannt ist, ob sie prim oder zusammengesetzt ist, ist F33. Diese Zahl hat 2.585.827.973 Stellen. Insgesamt weiß man von den ersten 50 Fermat-Zahlen nur von 10 nicht, ob sie zusammengesetzt sind oder nicht.
F18.233.954 ist die größte Fermat-Zahl, von der ein Faktor bekannt ist, nämlich die Primzahl 7 · 218.233.956 + 1. Dieser Faktor wurde am 5. Oktober 2020 von Ryan Propper mit Computer-Programmen von Geoffrey Reynolds, Jean Penné und Jim Fougeron entdeckt und hat 5.488.969 Stellen. Die Fermat-Zahl F18.233.954 selbst hat allerdings mehr als 105.488.966 Stellen.
Versuch einer anschaulichen Erklärung der Größe der Fermat-Zahl F18.233.954
Es gibt keine sinnvolle Methode, sich die Menge an Papier, die man benötigt sie aufzuschreiben – oder gar die Zahl selber – vorzustellen: Selbst mit den hypothetisch kleinsten Teilchen aufgeschrieben, ist das Universum spätestens mit F615 vollgeschrieben und für jeden weiteren Schritt bis F18233954 würde sich der Platz zum Aufschreiben jeweils verdoppeln. Nur hat man mit F615 ja quasi damit noch nicht mal richtig angefangen! Ein wissenschaftlicher Taschenrechner würde eine etwa 27 Kilometer lange Zeile oder alternativ eine 27 Meter mal 10 Meter große Tafel allein für das Anschreiben der Anzahl der Stellen, also von 105488966, als Dezimalzahl benötigen.
Insgesamt weiß man von 324 Fermat-Zahlen, dass sie zusammengesetzt sind. 368 Primfaktoren sind bisher bekannt (Stand: 30. Juli 2023).
Der folgenden Tabelle kann man entnehmen, in welchem Intervall wie viele zusammengesetzte Fermat-Zahlen bekannt sind (Stand: 30. Juli 2023):
|
|
Die kleinsten 25 Fermat-Primfaktoren sind die folgenden:
Um von einer Fermat-Zahl nachzuweisen, dass sie zusammengesetzt ist, benutzt man in der Regel den Pépin-Test und den Suyama-Test, die beide besonders auf diese Zahlen zugeschnitten und sehr schnell sind.
Die folgenden 16 Primfaktoren von Fermat-Zahlen wurden vor 1950 entdeckt.
Vor 1950 ohne Zuhilfenahme programmgesteuerter Rechenmaschinen entdeckte Primfaktoren von Fermat-Zahlen
| Jahr | Entdecker | Fermat- Zahl | Dezimal- stellen von Fn | Faktor | Dezimal- stellen dieses Faktors | Faktor ausgeschrieben |
|---|---|---|---|---|---|---|
| 1732 | Leonhard Euler | F5 (a) | 10 | 5 · 27 + 1 | 3 | 641 |
| 1732 | Leonhard Euler | F5 (a) | 10 | 52347 · 27 + 1 | 7 | 6.700.417 |
| 1855 | Thomas Clausen | F6 (a) | 20 | 1071 · 28 + 1 | 6 | 274.177 |
| 1855 | Thomas Clausen | F6 (a) | 20 | 262814145745 · 28 + 1 | 14 | 67.280.421.310.721 |
| 1877 | Iwan Perwuschin | F12 | 1.234 | 7 · 214 + 1 | 6 | 114.689 |
| 1878 | Iwan Perwuschin | F23 | 2.525.223 | 5 · 225 + 1 | 9 | 167.772.161 |
| 1886 | Paul Peter Heinrich Seelhoff | F36 | 20.686.623.784 | 5 · 239 + 1 | 13 | 2.748.779.069.441 |
| 1899 | Allan Joseph Champneys Cunningham | F11 | 617 | 39 · 213 + 1 | 6 | 319.489 |
| 1899 | Allan Joseph Champneys Cunningham | F11 | 617 | 119 · 213 + 1 | 6 | 974.849 |
| 1903 | Alfred Edward Western | F9 | 155 | 37 · 216 + 1 | 7 | 2.424.833 |
| 1903 | Alfred Edward Western | F12 | 1.234 | 397 · 216 + 1 | 8 | 26.017.793 |
| 1903 | Alfred Edward Western | F12 | 1.234 | 973 · 216 + 1 | 8 | 63.766.529 |
| 1903 | Alfred Edward Western | F18 | 78.914 | 13 · 220 + 1 | 8 | 13.631.489 |
| 1903 | James Cullen | F38 | 82.746.495.136 | 3 · 241 + 1 | 13 | 6.597.069.766.657 |
| 1906 | James Caddall Morehead | F73 | 2.843.147.923.723.958.896.933 | 5 · 275 + 1 | 24 | 188.894.659.314.785.808.547.841 |
| 1925 | Maurice Borissowitsch Kraitchik | F15 | 9.865 | 579 · 221 + 1 | 10 | 1.214.251.009 |
(a)
Diese Zahlen waren damit vollständig faktorisiert.
Seit 1950 wurden alle weiteren Faktoren durch Einsatz von Computern gefunden.
Mit Zuhilfenahme programmgesteuerter Rechenmaschinen entdeckte Primfaktoren von Fermat-Zahlen
|
|
|
|
|
|
|
|
Es wurden somit bisher 352 Primfaktoren von Fermat-Zahlen mit Computern gefunden (Stand: 30. Juli 2023).
Eigenschaften Bearbeiten
- Für hat jeder Teiler von die Form (bewiesen von Euler und Lucas, siehe auch Artikel Quadratisches Reziprozitätsgesetz, Unterabschnitt Teiler von Fermat- und Mersenne-Zahlen).
- Fermat-Zahlen lassen sich auf folgende Arten rekursiv berechnen:
Beweis der vier Behauptungen:
Zwei der vier Beweise funktionieren mittels vollständiger Induktion. Man zeigt, dass die Behauptungen für den Anfang gelten (Induktionsanfang), nimmt an, dass die Behauptung für gilt (Induktionsvoraussetzung) und beweist, dass die Behauptung dadurch auch für gelten muss (Induktionsschluss).
Beweis der ersten Behauptung: für
Beweis der zweiten Behauptung: für
Beweis der dritten Behauptung: für
Beweis der vierten Behauptung: für
- Es gelten folgende Darstellungen von :
Beweis der vier Behauptungen:
Beweis der ersten Behauptung:
Beweis der zweiten Behauptung:
Beweis der dritten Behauptung:
Beweis der vierten Behauptung:
- Sei die -te Fermat-Zahl. Dann gilt:
- kann niemals als Differenz von zwei p-ten Potenzen geschrieben werden, wenn und p ungerade Primzahlen sind:
Beweis der vier Behauptungen:
Beweis der ersten Behauptung:
Beweis der zweiten Behauptung:
Beweis der dritten Behauptung:
Beweis der vierten Behauptung:
- Sei die -te Fermat-Zahl und sei die Anzahl der Stellen von . Dann gilt:
- Sei die -te Fermat-Zahl mit . Dann gilt:
Beweis der Behauptung:
Der Beweis funktioniert direkt. Man startet mit dem linken Teil der Aussage und zeigt, dass daraus die rechte folgert. Danach startet man mit dem rechten Teil der Aussage und zeigt, dass daraus die linke Seite folgert.
Beweis:
- Für gilt:
- Sei , und prim. Dann gilt:
Beweis der ersten Behauptung:
Der Beweis funktioniert direkt. Man startet mit einer bekannten richtigen Aussage und beweist mittels Umformungen und Modulo-Rechnungen das Gewünschte.
Beweis der ersten Behauptung:
- Somit gilt:
- Für erhält man:
- Setzt man nun in obiges Ergebnis ein, dann erhält man:
- Die Zahl ist als Potenz von 2 durch jede kleinere Potenz von 2 teilbar, somit für auch durch . Es existiert also eine positive ganze Zahl mit . Wenn man dies in obiges Ergebnis einsetzt, erhält man:
Veröffentlichungsdatum:
Eine Fermat Zahl benannt nach dem franzosischen Mathematiker Pierre de Fermat ist eine Zahl der Form F n 2 2 n 1 displaystyle F n 2 2 n 1 mit einer ganzen Zahl n 0 displaystyle n geq 0 Die ersten Fermat Zahlen lauten 3 5 und 17 Im August 1640 vermutete Fermat falschlicherweise dass alle Zahlen dieser Form die spater nach ihm benannt wurden Primzahlen seien 1 Dies wurde jedoch 1732 von Leonhard Euler widerlegt der zeigte dass schon die sechste Fermatzahl F5 durch 641 teilbar ist 2 Man kennt ausser den ersten funf 3 5 17 257 65537 derzeit keine weitere Fermat Zahl die gleichzeitig Primzahl ist und vermutet dass es ausser diesen funf Zahlen auch keine weitere gibt siehe Abschnitt weiter unten Inhaltsverzeichnis 1 Fermat Zahlen 2 Fermatsche Primzahlen 3 Faktorisierungsergebnisse von Fermat Zahlen 4 Eigenschaften 5 Ungeloste Probleme 6 Warum es wahrscheinlich keine weiteren Fermat Primzahlen gibt 7 Geometrische Anwendung der Fermatschen Primzahlen 8 Verallgemeinerte Fermatsche Zahlen 8 1 Verallgemeinerte Fermatsche Zahlen der Form Fn b 8 2 Liste der Primzahlen der Form Fn b 8 3 Die 10 grossten bekannten verallgemeinerten Fermatschen Primzahlen 9 Siehe auch 10 Literatur 11 Weblinks 12 EinzelnachweiseFermat Zahlen BearbeitenDie ersten Fermat Zahlen lauten F 0 3 F 1 5 F 2 17 F 3 257 displaystyle F 0 3 F 1 5 F 2 17 F 3 257 nbsp und F 4 65537 displaystyle F 4 65537 nbsp 3 Eine etwas langere Liste bis F 14 displaystyle F 14 nbsp findet man in der folgenden aufklappbaren Box Liste der ersten 15 Fermat Zahlen n Dezimal stellen von Fn Fn0 0 1 30 1 1 50 2 2 170 3 3 2570 4 5 65 5370 5 10 4 294 967 2970 6 20 18 446 744 073 709 551 6170 7 39 340 282 366 920 938 463 463 374 607 431 768 211 4570 8 78 115 792 089 237 316 195 423 570 985 008 687 907 853 269 984 665 640 564 039 457 584 007 913 129 639 9370 9 155 13 407 807 929 942 597 099 574 024 998 205 846 127 479 365 820 592 393 377 723 561 443 721 764 030 073 546 976 801 874 298 166 903 427 690 031 858 186 486 050 853 753 882 811 946 569 946 433 649 006 084 09710 309 179 769 313 486 231 590 772 930 519 078 902 473 361 797 697 894 230 657 273 430 081 157 732 675 805 500 963 132 708 477 322 407 536 021 120 113 879 871 393 357 658 789 768 814 416 622 492 847 430 639 474 124 377 767 893 424 865 485 276 302 219 601 246 094 119 453 082 952 085 005 768 838 150 682 342 462 881 473 913 110 540 827 237 163 350 510 684 586 298 239 947 245 938 479 716 304 835 356 329 624 224 137 21711 617 32 317 006 071 311 007 300 714 876 688 669 951 960 444 102 669 715 484 032 130 345 427 524 655 138 867 890 893 197 201 411 522 913 463 688 717 960 921 898 019 494 119 559 150 490 921 095 088 152 386 448 283 120 630 877 367 300 996 091 750 197 750 389 652 106 796 057 638 384 067 568 276 792 218 642 619 756 161 838 094 338 476 170 470 581 645 852 036 305 042 887 575 891 541 065 808 607 552 399 123 930 385 521 914 333 389 668 342 420 684 974 786 564 569 494 856 176 035 326 322 058 077 805 659 331 026 192 708 460 314 150 258 592 864 177 116 725 943 603 718 461 857 357 598 351 152 301 645 904 403 697 613 233 287 231 227 125 684 710 820 209 725 157 101 726 931 323 469 678 542 580 656 697 935 045 997 268 352 998 638 215 525 166 389 437 335 543 602 135 433 229 604 645 318 478 604 952 148 193 555 853 611 059 596 230 65712 1234 1 044 388 881 413 152 506 691 752 710 716 624 382 579 964 249 047 383 780 384 233 483 283 953 907 971 557 456 848 826 811 934 997 558 340 890 106 714 439 262 837 987 573 438 185 793 607 263 236 087 851 365 277 945 956 976 543 709 998 340 361 590 134 383 718 314 428 070 011 855 946 226 376 318 839 397 712 745 672 334 684 344 586 617 496 807 908 705 803 704 071 284 048 740 118 609 114 467 977 783 598 029 006 686 938 976 881 787 785 946 905 630 190 260 940 599 579 453 432 823 469 303 026 696 443 059 025 015 972 399 867 714 215 541 693 835 559 885 291 486 318 237 914 434 496 734 087 811 872 639 496 475 100 189 041 349 008 417 061 675 093 668 333 850 551 032 972 088 269 550 769 983 616 369 411 933 015 213 796 825 837 188 091 833 656 751 221 318 492 846 368 125 550 225 998 300 412 344 784 862 595 674 492 194 617 023 806 505 913 245 610 825 731 835 380 087 608 622 102 834 270 197 698 202 313 169 017 678 006 675 195 485 079 921 636 419 370 285 375 124 784 014 907 159 135 459 982 790 513 399 611 551 794 271 106 831 134 090 584 272 884 279 791 554 849 782 954 323 534 517 065 223 269 061 394 905 987 693 002 122 963 395 687 782 878 948 440 616 007 412 945 674 919 823 050 571 642 377 154 816 321 380 631 045 902 916 136 926 708 342 856 440 730 447 899 971 901 781 465 763 473 223 850 267 253 059 899 795 996 090 799 469 201 774 624 817 718 449 867 455 659 250 178 329 070 473 119 433 165 550 807 568 221 846 571 746 373 296 884 912 819 520 317 457 002 440 926 616 910 874 148 385 078 411 929 804 522 981 857 338 977 648 103 126 085 903 001 302 413 467 189 726 673 216 491 511 131 602 920 781 738 033 436 090 243 804 708 340 403 154 190 33713 2467 1 090 748 135 619 415 929 462 984 244 733 782 862 448 264 161 996 232 692 431 832 786 189 721 331 849 119 295 216 264 234 525 201 987 223 957 291 796 157 025 273 109 870 820 177 184 063 610 979 765 077 554 799 078 906 298 842 192 989 538 609 825 228 048 205 159 696 851 613 591 638 196 771 886 542 609 324 560 121 290 553 901 886 301 017 900 252 535 799 917 200 010 079 600 026 535 836 800 905 297 805 880 952 350 501 630 195 475 653 911 005 312 364 560 014 847 426 035 293 551 245 843 928 918 752 768 696 279 344 088 055 617 515 694 349 945 406 677 825 140 814 900 616 105 920 256 438 504 578 013 326 493 565 836 047 242 407 382 442 812 245 131 517 757 519 164 899 226 365 743 722 432 277 368 075 027 627 883 045 206 501 792 761 700 945 699 168 497 257 879 683 851 737 049 996 900 961 120 515 655 050 115 561 271 491 492 515 342 105 748 966 629 547 032 786 321 505 730 828 430 221 664 970 324 396 138 635 251 626 409 516 168 005 427 623 435 996 308 921 691 446 181 187 406 395 310 665 404 885 739 434 832 877 428 167 407 495 370 993 511 868 756 359 970 390 117 021 823 616 749 458 620 969 857 006 263 612 082 706 715 408 157 066 575 137 281 027 022 310 927 564 910 276 759 160 520 878 304 632 411 049 364 568 754 920 967 322 982 459 184 763 427 383 790 272 448 438 018 526 977 764 941 072 715 611 580 434 690 827 459 339 991 961 414 242 741 410 599 117 426 060 556 483 763 756 314 527 611 362 658 628 383 368 621 157 993 638 020 878 537 675 545 336 789 915 694 234 433 955 666 315 070 087 213 535 470 255 670 312 004 130 725 495 834 508 357 439 653 828 936 077 080 978 550 578 912 967 907 352 780 054 935 621 561 090 795 845 172 954 115 972 927 479 877 527 738 560 008 204 118 558 930 004 777 748 727 761 853 813 510 493 840 581 861 598 652 211 605 960 308 356 405 941 821 189 714 037 868 726 219 481 498 727 603 653 616 298 856 174 822 413 033 485 438 785 324 024 751 419 417 183 012 281 078 209 729 303 537 372 804 574 372 095 228 703 622 776 363 945 290 869 806 258 422 355 148 507 571 039 619 387 449 629 866 808 188 769 662 815 778 153 079 393 179 093 143 648 340 761 738 581 819 563 002 994 422 790 754 955 061 288 818 308 430 079 648 693 232 179 158 765 918 035 565 216 157 115 402 992 120 276 155 607 873 107 937 477 466 841 528 362 987 708 699 450 152 031 231 862 594 203 085 693 838 944 657 061 346 236 704 234 026 821 102 958 954 951 197 087 076 546 186 622 796 294 536 451 620 756 509 351 018 906 023 773 821 539 532 776 208 676 978 589 731 966 330 308 893 304 665 169 436 185 078 350 641 568 336 944 530 051 437 491 311 298 834 367 265 238 595 404 904 273 455 928 723 949 525 227 184 617 404 367 854 754 610 474 377 019 768 025 576 605 881 038 077 270 707 717 942 221 977 090 385 438 585 844 095 492 116 099 852 538 903 974 655 703 943 973 086 090 930 596 963 360 767 529 964 938 414 598 185 705 963 754 561 497 355 827 813 623 833 288 906 309 004 288 017 321 424 808 663 962 671 333 528 009 232 758 350 873 059 614 118 723 781 422 101 460 198 615 747 386 855 096 896 089 189 180 441 339 558 524 822 867 541 113 212 638 793 675 567 650 340 362 970 031 930 023 397 828 465 318 547 238 244 232 028 015 189 689 660 418 822 976 000 815 437 610 652 254 270 163 595 650 875 433 851 147 123 214 227 266 605 403 581 781 469 090 806 576 468 950 587 661 997 186 505 665 475 715 792 89714 4933 1 189 731 495 357 231 765 085 759 326 628 007 130 763 444 687 096 510 237 472 674 821 233 261 358 180 483 686 904 488 595 472 612 039 915 115 437 484 839 309 258 897 667 381 308 687 426 274 524 698 341 565 006 080 871 634 366 004 897 522 143 251 619 531 446 845 952 345 709 482 135 847 036 647 464 830 984 784 714 280 967 845 614 138 476 044 338 404 886 122 905 286 855 313 236 158 695 999 885 790 106 357 018 120 815 363 320 780 964 323 712 757 164 290 613 406 875 202 417 365 323 950 267 880 089 067 517 372 270 610 835 647 545 755 780 793 431 622 213 451 903 817 859 630 690 311 343 850 657 539 360 649 645 193 283 178 291 767 658 965 405 285 113 556 134 369 793 281 725 888 015 908 414 675 289 832 538 063 419 234 888 599 898 980 623 114 025 121 674 472 051 872 439 321 323 198 402 942 705 341 366 951 274 739 014 593 816 898 288 994 445 173 400 364 617 928 377 138 074 411 345 791 848 573 595 077 170 437 644 191 743 889 644 885 377 684 738 322 240 608 239 079 061 399 475 675 334 739 784 016 491 742 621 485 229 014 847 672 335 977 897 158 397 334 226 349 734 811 441 653 077 758 250 988 926 030 894 789 604 676 153 104 257 260 141 806 823 027 588 003 441 951 455 327 701 598 071 281 589 597 169 413 965 608 439 504 983 171 255 062 282 026 626 200 048 042 149 808 200 002 060 993 433 681 237 623 857 880 627 479 727 072 877 482 838 438 705 048 034 164 633 337 013 385 405 998 040 701 908 662 387 301 605 018 188 262 573 723 766 279 240 798 931 717 708 807 901 740 265 407 930 976 419 648 877 869 604 017 517 691 938 687 988 088 008 944 251 258 826 969 688 364 194 133 945 780 157 844 364 946 052 713 655 454 906 327 187 428 531 895 100 278 695 119 323 496 808 703 630 436 193 927 592 692 344 820 812 834 297 364 478 686 862 064 169 042 458 555 136 532 055 050 508 189 891 866 846 863 799 917 647 547 291 371 573 500 701 015 197 559 097 453 040 033 031 520 683 518 216 494 195 636 696 077 748 110 598 284 901 343 611 469 214 274 121 810 495 077 979 275 556 645 164 983 850 062 051 066 517 084 647 369 464 036 640 569 339 464 837 172 183 352 956 873 912 042 640 003 611 618 789 278 195 710 052 094 562 761 306 703 551 840 330 110 645 101 995 435 167 626 688 669 627 763 820 604 342 480 357 906 415 354 212 732 946 756 073 006 907 088 870 496 125 050 068 156 659 252 761 297 664 065 498 347 492 661 798 824 062 312 210 409 274 584 565 587 264 846 417 650 160 123 175 874 034 726 261 957 289 081 466 197 651 553 830 744 424 709 698 634 753 627 770 356 227 126 145 052 549 125 229 448 040 149 114 795 681 359 875 968 512 808 575 244 271 871 455 454 084 894 986 155 020 794 806 980 939 215 658 055 319 165 641 681 105 966 454 159 951 476 908 583 129 721 503 298 816 585 142 073 061 480 888 021 769 818 338 417 129 396 878 371 459 575 846 052 583 142 928 447 249 703 698 548 125 295 775 920 936 450 022 651 427 249 949 580 708 203 966 082 847 550 921 891 152 133 321 048 011 973 883 636 577 825 533 325 988 852 156 325 439 335 021 315 312 134 081 390 451 021 255 363 707 903 495 916 963 125 924 201 167 877 190 108 935 255 914 539 488 216 897 117 943 269 373 608 639 074 472 792 751 116 715 127 106 396 425 081 353 553 137 213 552 890 539 802 602 978 645 319 795 100 976 432 939 091 924 660 228 878 912 900 654 210 118 287 298 298 707 382 159 717 184 569 540 515 403 029 173 307 292 454 391 789 568 674 219 640 761 451 173 600 617 752 186 991 913 366 837 033 887 201 582 071 625 868 247 133 104 513 315 097 274 713 442 728 340 606 642 890 406 496 636 104 443 217 752 811 227 470 029 162 858 093 727 701 049 646 499 540 220 983 981 932 786 613 204 254 226 464 243 689 610 107 429 923 197 638 681 545 837 561 773 535 568 984 536 053 627 234 424 277 105 760 924 864 023 781 629 665 526 314 910 906 960 488 073 475 217 005 121 136 311 870 439 925 762 508 666 032 566 213 750 416 695 719 919 674 223 210 606 724 721 373 471 234 021 613 540 712 188 239 909 701 971 943 944 347 480 314 217 903 886 317 767 779 921 539 892 177 334 344 368 907 550 318 800 833 546 852 344 370 327 089 284 147 501 640 589 448 482 001 254 237 386 680 074 457 341 910 933 774 891 959 681 016 516 069 106 149 905 572 425 810 895 586 938 833 067 490 204 900 368 624 166 301 968 553 005 687 040 285 095 450 484 840 073 528 643 826 570 403 767 157 286 512 380 255 109 954 518 857 013 476 588 189 300 004 138 849 715 883 139 866 071 547 574 816 476 727 635 116 435 462 804 401 112 711 392 529 180 570 794 193 422 686 818 353 212 799 068 972 247 697 191 474 268 157 912 195 973 794 192 807 298 886 952 361 100 880 264 258 801 320 928 040 011 928 153 970 801 130 741 339 550 003 299 015 924 978 259 936 974 358 726 286 143 980 520 112 454 369 271 114 083 747 919 007 803 406 596 321 353 417 004 068 869 443 405 472 140 675 963 640 997 405 009 225 803 505 672 726 465 095 506 267 339 268 892 424 364 561 897 661 906 898 424 186 770 491 035 344 080 399 248 327 097 911 712 881 140 170 384 182 058 601 614 758 284 200 750 183 500 329 358 499 691 864 066 590 539 660 709 069 537 381 601 887 679 046 657 759 654 588 001 937 117 771 344 698 326 428 792 622 894 338 016 112 445 533 539 447 087 462 049 763 409 147 542 099 248 815 521 395 929 388 007 711 172 017 894 897 793 706 604 273 480 985 161 028 815 458 787 911 160 979 113 422 433 557 549 170 905 442 026 397 275 695 283 207 305 331 845 419 990 749 347 810 524 006 194 197 200 591 652 147 867 193 696 254 337 864 981 603 833 146 354 201 700 628 817 947 177 518 115 217 674 352 016 511 172 347 727 727 075 220 056 177 748 218 928 597 158 346 744 541 337 107 358 427 757 919 660 562 583 883 823 262 178 961 691 787 226 118 865 632 764 934 288 772 405 859 754 877 759 869 235 530 653 929 937 901 193 611 669 007 472 354 746 360 764 601 872 442 031 379 944 139 824 366 828 698 790 212 922 996 174 192 728 625 891 720 057 612 509 349 100 482 545 964 152 046 477 925 114 446 500 732 164 109 099 345 259 799 455 690 095 576 788 686 397 487 061 948 854 749 024 863 607 921 857 834 205 793 797 188 834 779 656 273 479 112 388 585 706 424 836 379 072 355 410 286 787 018 527 401 653 934 219 888 361 061 949 671 961 055 068 686 961 468 019 035 629 749 424 086 587 195 041 004 404 915 266 476 272 761 070 511 568 387 063 401 264 136 517 237 211 409 916 458 796 347 624 949 215 904 533 937 210 937 520 465 798 300 175 408 017 538 862 312 719 042 361 037 129 338 896 586 028 150 046 596 078 872 444 365 564 480 545 689 033 575 955 702 988 396 719 744 528 212 984 142 578 483 954 005 084 264 327 730 840 985 420 021 409 069 485 412 320 805 268 520 094 146 798 876 110 414 583 170 390 473 982 488 899 228 091 818 213 934 288 295 679 717 369 943 152 460 447 027 290 669 964 066 817 Wegen F n 1 F n 2 displaystyle F n 1 approx F n 2 nbsp hat die Fermatzahl F n 1 displaystyle F n 1 nbsp doppelt so viele oder um eine weniger als doppelt so viele Stellen wie ihr Vorganger F n displaystyle F n nbsp Fermatsche Primzahlen BearbeitenDie Idee hinter Fermatschen Primzahlen ist der Satz dass 2 k 1 displaystyle 2 k 1 nbsp nur fur k 0 displaystyle k 0 nbsp und fur k 2 n displaystyle k 2 n nbsp mit n 0 displaystyle n geq 0 nbsp prim sein kann 2 k 1 P k 0 n N 0 k 2 n displaystyle 2 k 1 in mathbb P Rightarrow k 0 lor exists n in mathbb N 0 colon k 2 n nbsp Beweis des Satzes Beweis durch Widerspruch Man fuhrt die Annahme dass das zu Beweisende falsch sei zu einem Widerspruch Annahme k gt 0 displaystyle k gt 0 nbsp und 2 k 1 displaystyle 2 k 1 nbsp ist prim und die Hochzahl k displaystyle k nbsp hat einen ungeraden Teiler c gt 1 displaystyle c gt 1 nbsp Dann gilt2 k 1 2 k c c 1 2 k c c 1 c displaystyle 2 k 1 2 frac k c cdot c 1 2 frac k c c 1 c nbsp dd mit einer ganzen Zahl k c displaystyle k c nbsp Nach Annahme ist c displaystyle c nbsp ungerade also ist diese Summe bekanntlich durch die Summe 2 k c 1 displaystyle 2 frac k c 1 nbsp der beiden Basen teilbar 2 k 1 2 k c c 1 c 2 k c 1 j 0 c 1 1 j 2 k c j displaystyle 2 k 1 2 frac k c c 1 c 2 frac k c 1 cdot sum j 0 c 1 1 j cdot 2 frac k c j nbsp dd Weil die Zahl 2 k 1 displaystyle 2 k 1 nbsp prim ist muss ihr Teiler 2 k c 1 displaystyle 2 frac k c 1 nbsp gleich 1 oder gleich 2 k 1 displaystyle 2 k 1 nbsp sein Aber in Widerspruch dazu ist 2 k c 1 displaystyle 2 frac k c 1 nbsp wegen 2 k c gt 0 displaystyle 2 frac k c gt 0 nbsp grosser als 1 und wegen k gt 0 k c lt k displaystyle k gt 0 Rightarrow k c lt k nbsp kleiner als 2 k 1 displaystyle 2 k 1 nbsp Die Annahme dass sowohl 2 k 1 displaystyle 2 k 1 nbsp prim ist als auch dass k displaystyle k nbsp positiv ist und einen ungeraden Teiler c gt 1 displaystyle c gt 1 nbsp hat muss daher fallengelassen werden 2 k 1 displaystyle 2 k 1 nbsp kann nur prim sein wenn k displaystyle k nbsp gleich 0 oder gleich einer Zweierpotenz 2 n displaystyle 2 n nbsp mit n 0 displaystyle n geq 0 nbsp ist was zu zeigen war displaystyle Box nbsp Die Umkehrung dieses Satzes dass also nicht nur wegen 2 0 1 1 1 2 P displaystyle 2 0 1 1 1 2 in mathbb P nbsp offensichtlich 2 0 1 displaystyle 2 0 1 nbsp sondern auch jede Fermat Zahl F n 2 2 n 1 displaystyle F n 2 2 n 1 nbsp prim sei ist falsch F 0 displaystyle F 0 nbsp bis F 4 displaystyle F 4 nbsp sind sogar die einzigen bisher bekannten Fermatschen Primzahlen Schon Fermat zeigte dass diese ersten funf Fermat Zahlen Primzahlen sind und vermutete 1640 dass dies auf alle Fermat Zahlen zutreffe Diese Vermutung wurde aber schon 1732 von Leonhard Euler einfach widerlegt indem er mit 641 einen echten Teiler von F5 4 294 967 297 fand 4 Man vermutet inzwischen dass ausser den ersten funf keine weiteren Fermatschen Primzahlen existieren Diese Vermutung beruht auf statistischen Abschatzungen Der Primzahlsatz besagt dass die Anzahl der Primzahlen die nicht grosser als x sind naherungsweise gleich x ln x ist Die Primzahldichte oder Wahrscheinlichkeit dafur dass Fn als ungerade Zahl eine Primzahl ist betragt daher naherungsweise 2 ln Fn 3 2n Die Wahrscheinlichkeit dass die Fermatzahl Fn oder eine der folgenden Fermatzahlen eine Primzahl ist ergibt sich durch Summation der geometrische Reihe ungefahr zu 6 2n Fur verbliebene weder teilweise noch vollstandig faktorisierte Fermat Zahlen ist diese Wahrscheinlichkeit mit etwa 6 10 10 mittlerweile aber sehr klein geworden Faktorisierungsergebnisse von Fermat Zahlen BearbeitenDie Zahlen F0 bis F4 sind wie schon Fermat erkannt hat Primzahlen n Fermat Primzahl Fn0 0 30 1 50 2 170 3 2570 4 65537Die Zahlen F5 bis F11 sind entgegen der Vermutung Fermats zusammengesetzt Sie sind bereits vollstandig faktorisiert 5 Liste der zusammengesetzten und vollstandig faktorisierten Fermat Zahlen n Entdecker der Faktoren Primfaktorenzerlegung von Fn0 5 Leonhard Euler 1732 4 294 967 297 10 Stellen 641 3 Stellen 6 700 417 7 Stellen 0 6 Clausen 1855 Landry amp Le Lasseur 1880 18 446 744 073 709 551 617 20 Stellen 274 177 6 Stellen 67 280 421 310 721 14 Stellen 0 7 Morrison amp Brillhart 1970 6 340 282 366 920 938 463 463 374 607 431 768 211 457 39 Stellen 59 649 589 127 497 217 17 Stellen 5 704 689 200 685 129 054 721 22 Stellen 0 8 Brent amp Pollard 1980 115 792 089 237 316 195 423 570 985 008 687 907 853 269 984 665 640 564 039 457 584 007 913 129 639 937 78 Stellen 1 238 926 361 552 897 16 Stellen 93 461 639 715 357 977 769 163 558 199 606 896 584 051 237 541 638 188 580 280 321 62 Stellen 0 9 Western 1903 Lenstra amp Manasse 1990 13 407 807 929 942 597 099 574 024 998 205 846 127 479 365 820 592 393 377 723 561 443 721 764 030 073 546 976 801 874 298 166 903 427 690 031 858 186 486 050 853 753 882 811 946 569 946 433 649 006 084 097 155 Stellen 2 424 833 7 Stellen 7 455 602 825 647 884 208 337 395 736 200 454 918 783 366 342 657 49 Stellen 741 640 062 627 530 801 524 787 141 901 937 474 059 940 781 097 519 023 905 821 316 144 415 759 504 705 008 092 818 711 693 940 737 99 Stellen 10 Selfridge 1953 Brillhart 1962 Brent 1995 179 769 313 486 231 590 772 930 304 835 356 329 624 224 137 217 309 Stellen 45 592 577 8 Stellen 6 487 031 809 10 Stellen 4 659 775 785 220 018 543 264 560 743 076 778 192 897 40 Stellen 130 439 874 405 488 189 727 484 806 217 820 753 127 014 424 577 252 Stellen 11 Cunningham 1899 Brent amp Morain 1988 32 317 006 071 311 007 300 714 8 193 555 853 611 059 596 230 657 617 Stellen 319 489 6 Stellen 974 849 6 Stellen 167 988 556 341 760 475 137 21 Stellen 3 560 841 906 445 833 920 513 22 Stellen 173 462 447 179 147 555 430 258 491 382 441 723 306 598 834 177 564 Stellen Ab F12 ist keine Fermat Zahl mehr vollstandig faktorisiert Die ersten acht lauten Liste der ersten acht der nur teilweise faktorisierten Fermat Zahlen n Entdecker der Faktoren Primfaktorenzerlegung von Fn12 Lucas amp Perwuschin 1877 Western 1903 Hallyburton amp Brillhart 1974 Baillie 1986 Vang Zimmermann amp Kruppa 2010 1 044 388 881 413 152 506 691 752 710 716 340 403 154 190 337 1234 Stellen 114 689 6 Stellen 26 017 793 8 Stellen 63 766 529 8 Stellen 190 274 191 361 12 Stellen 1 256 132 134 125 569 16 Stellen 568 630 647 535 356 955 169 033 410 940 867 804 839 360 742 060 818 433 54 Stellen zusammengesetzte Zahl 1133 Stellen 13 Hallyburton amp Brillhart 1974 Crandall 1991 Brent 1995 1 090 748 135 619 415 929 462 984 244 733 665 475 715 792 897 2467 Stellen 2 710 954 639 361 13 Stellen 2 663 848 877 152 141 313 19 Stellen 3 603 109 844 542 291 969 19 Stellen 319 546 020 820 551 643 220 672 513 27 Stellen zusammengesetzte Zahl 2391 Stellen 14 Rajala amp Woltman 2010 1 189 731 495 357 231 765 085 759 326 628 290 669 964 066 817 4933 Stellen 116 928 085 873 074 369 829 035 993 834 596 371 340 386 703 423 373 313 54 Stellen zusammengesetzte Zahl 4880 Stellen 15 Kraitchik 1925 Gostin 1987 Crandall amp van Halewyn 1997 1 415 461 031 044 954 789 001 553 027 744 104 633 712 377 857 9865 Stellen 1 214 251 009 10 Stellen 2 327 042 503 868 417 16 Stellen 168 768 817 029 516 972 383 024 127 016 961 33 Stellen zusammengesetzte Zahl 9808 Stellen 16 Selfridge 1953 Crandall amp Dilcher 1996 2 003 529 930 406 846 464 979 072 351 560 895 905 719 156 737 19729 Stellen 825 753 601 9 Stellen 188 981 757 975 021 318 420 037 633 27 Stellen zusammengesetzte Zahl 19694 Stellen 17 Gostin 1978 Bessell amp Woltman 2011 4 014 132 182 036 063 039 166 060 606 038 318 570 934 173 697 39457 Stellen 31 065 037 602 817 14 Stellen 7 751 061 099 802 522 589 358 967 058 392 886 922 693 580 423 169 49 Stellen zusammengesetzte Zahl 39395 Stellen 18 Western 1903 Crandall McIntosh amp Tardif 1999 16 113 257 174 857 604 736 195 721 184 520 349 934 298 300 417 78914 Stellen 13 631 489 8 Stellen 81 274 690 703 860 512 587 777 23 Stellen zusammengesetzte Zahl 78884 Stellen 19 Riesel 1962 Wrathall 1963 Bessell amp Woltman 2009 259 637 056 783 100 077 612 659 649 572 688 528 226 185 773 057 157827 Stellen 70 525 124 609 11 Stellen 646 730 219 521 12 Stellen 37 590 055 514 133 754 286 524 446 080 499 713 35 Stellen zusammengesetzte Zahl 157770 Stellen Von F12 bis F32 und von einigen grosseren Fermat Zahlen ist bekannt dass sie zusammengesetzt sind hauptsachlich weil ein oder mehrere Faktoren gefunden wurden Von zwei Fermat Zahlen F20 und F24 kennt man zwar keinen Faktor hat aber auf andere Art gezeigt dass sie zusammengesetzt sind 7 8 Fur F14 wurde am 3 Februar 2010 ein Faktor veroffentlicht 9 fur F22 am 25 Marz 2010 10 Die kleinste Fermat Zahl von der bislang nicht bekannt ist ob sie prim oder zusammengesetzt ist ist F33 Diese Zahl hat 2 585 827 973 Stellen Insgesamt weiss man von den ersten 50 Fermat Zahlen nur von 10 nicht ob sie zusammengesetzt sind oder nicht 11 F18 233 954 ist die grosste Fermat Zahl von der ein Faktor bekannt ist namlich die Primzahl 7 218 233 956 1 Dieser Faktor wurde am 5 Oktober 2020 von Ryan Propper mit Computer Programmen von Geoffrey Reynolds Jean Penne und Jim Fougeron entdeckt und hat 5 488 969 Stellen Die Fermat Zahl F18 233 954 selbst hat allerdings mehr als 105 488 966 Stellen 12 Versuch einer anschaulichen Erklarung der Grosse der Fermat Zahl F18 233 954 Es gibt keine sinnvolle Methode sich die Menge an Papier die man benotigt sie aufzuschreiben oder gar die Zahl selber vorzustellen Selbst mit den hypothetisch kleinsten Teilchen aufgeschrieben ist das Universum spatestens mit F615 vollgeschrieben und fur jeden weiteren Schritt bis F18233954 wurde sich der Platz zum Aufschreiben jeweils verdoppeln Nur hat man mit F615 ja quasi damit noch nicht mal richtig angefangen Ein wissenschaftlicher Taschenrechner wurde eine etwa 27 Kilometer lange Zeile oder alternativ eine 27 Meter mal 10 Meter grosse Tafel allein fur das Anschreiben der Anzahl der Stellen also von 105488966 als Dezimalzahl benotigen Insgesamt weiss man von 324 Fermat Zahlen dass sie zusammengesetzt sind 368 Primfaktoren sind bisher bekannt Stand 30 Juli 2023 5 13 Der folgenden Tabelle kann man entnehmen in welchem Intervall wie viele zusammengesetzte Fermat Zahlen bekannt sind Stand 30 Juli 2023 nachweislich keine Primzahln bekannt zusammengesetzt Anteil0 5 n 32 0 28 100 0 0 33 n 100 0 32 0 47 1 101 n 500 0 64 0 16 0 0 501 n 1000 0 22 00 4 4 1001 n 5000 0 53 00 1 3 0 5001 n 10000 0 27 00 0 5 TOTAL 226 00 2 3 nachweislich keine Primzahln bekannt zusammengesetzt Anteil10001 n 50000 38 0 09500 0 50001 n 100000 11 0 02200 100001 n 500000 26 0 00650 0 500001 n 1000000 0 7 0 00140 1000001 n 5000000 13 0 00033 0 5000001 n 20000000 0 3 0 00006 TOTAL 98 0 00049 Die kleinsten 25 Fermat Primfaktoren sind die folgenden 3 5 17 257 641 65 537 114 689 274 177 319 489 974 849 2 424 833 6 700 417 13 631 489 26 017 793 45 592 577 63 766 529 167 772 161 825 753 601 1 214 251 009 6 487 031 809 70 525 124 609 190 274 191 361 646 730 219 521 2 710 954 639 361 2 748 779 069 441 Folge A023394 in OEIS Um von einer Fermat Zahl nachzuweisen dass sie zusammengesetzt ist benutzt man in der Regel den Pepin Test und den Suyama Test die beide besonders auf diese Zahlen zugeschnitten und sehr schnell sind Die folgenden 16 Primfaktoren von Fermat Zahlen wurden vor 1950 entdeckt Vor 1950 ohne Zuhilfenahme programmgesteuerter Rechenmaschinen entdeckte Primfaktoren von Fermat Zahlen Jahr Entdecker Fermat Zahl Dezimal stellen von Fn Faktor Dezimal stellen dieses Faktors Faktor ausgeschrieben1732 Leonhard Euler F5 a 10 5 27 1 3 6411732 Leonhard Euler F5 a 10 52347 27 1 7 6 700 4171855 Thomas Clausen F6 a 20 1071 28 1 6 274 1771855 Thomas Clausen F6 a 20 262814145745 28 1 14 67 280 421 310 7211877 Iwan Perwuschin F12 1 234 7 214 1 6 114 6891878 Iwan Perwuschin F23 2 525 223 5 225 1 9 167 772 1611886 Paul Peter Heinrich Seelhoff F36 20 686 623 784 5 239 1 13 2 748 779 069 4411899 Allan Joseph Champneys Cunningham F11 617 39 213 1 6 319 4891899 Allan Joseph Champneys Cunningham F11 617 119 213 1 6 974 8491903 Alfred Edward Western F9 155 37 216 1 7 2 424 8331903 Alfred Edward Western F12 1 234 397 216 1 8 26 017 7931903 Alfred Edward Western F12 1 234 973 216 1 8 63 766 5291903 Alfred Edward Western F18 78 914 13 220 1 8 13 631 4891903 James Cullen F38 82 746 495 136 3 241 1 13 6 597 069 766 6571906 James Caddall Morehead F73 2 843 147 923 723 958 896 933 5 275 1 24 188 894 659 314 785 808 547 8411925 Maurice Borissowitsch Kraitchik F15 9 865 579 221 1 10 1 214 251 009 a Diese Zahlen waren damit vollstandig faktorisiert Seit 1950 wurden alle weiteren Faktoren durch Einsatz von Computern gefunden 14 Mit Zuhilfenahme programmgesteuerter Rechenmaschinen entdeckte Primfaktoren von Fermat Zahlen Jahr Teiler1951 0 1952 0 1953 0 21954 0 1955 0 1956 141957 0 61958 0 1959 0 1960 0 TOTAL 22 Jahr Teiler1961 0 1962 0 21963 111964 0 1965 0 1966 0 1967 0 1968 0 1969 0 1970 0 2TOTAL 15 Jahr Teiler1971 0 1972 0 1973 0 1974 0 21975 0 1976 0 21977 0 41978 0 21979 131980 0 9TOTAL 32 Jahr Teiler1981 0 31982 0 21983 0 21984 0 71985 0 21986 121987 0 51988 0 41989 0 1990 0 8TOTAL 45 Jahr Teiler1991 121992 101993 101994 0 11995 0 81996 0 71997 0 41998 0 81999 0 92000 13TOTAL 82 Jahr Teiler2001 222002 0 82003 0 82004 0 22005 0 72006 0 12007 0 42008 0 62009 0 62010 0 7TOTAL 71 Jahr Teiler2011 0 92012 162013 0 72014 0 72015 0 62016 0 72017 0 52018 0 72019 0 32020 0 5TOTAL 72 Jahr Teiler2021 0 52022 0 2023 0 82024202520262027202820292030TOTAL 13Es wurden somit bisher 352 Primfaktoren von Fermat Zahlen mit Computern gefunden Stand 30 Juli 2023 Eigenschaften BearbeitenFur n gt 1 displaystyle n gt 1 nbsp hat jeder Teiler von F n displaystyle F n nbsp die Form k 2 n 2 1 displaystyle k cdot 2 n 2 1 nbsp bewiesen von Euler und Lucas siehe auch Artikel Quadratisches Reziprozitatsgesetz Unterabschnitt Teiler von Fermat und Mersenne Zahlen Beispiele Der Teiler 641 von F5 641 5 27 1 5 128 1 Der Teiler 6700417 von F5 6700417 52347 27 1 52347 128 1 dd Fermat Zahlen lassen sich auf folgende Arten rekursiv berechnen F n F n 1 1 2 1 displaystyle F n F n 1 1 2 1 nbsp fur n 1 displaystyle n geq 1 nbsp F n F n 1 2 2 n 1 F 0 F 1 F n 2 displaystyle F n F n 1 2 2 n 1 cdot F 0 cdot F 1 cdot ldots cdot F n 2 nbsp fur n 2 displaystyle n geq 2 nbsp F n F n 1 2 2 F n 2 1 2 displaystyle F n F n 1 2 2 cdot F n 2 1 2 nbsp fur n 2 displaystyle n geq 2 nbsp F n F 0 F 1 F n 1 2 displaystyle F n F 0 cdot F 1 cdot ldots cdot F n 1 2 nbsp fur n 1 displaystyle n geq 1 nbsp Beweis der vier Behauptungen Zwei der vier Beweise funktionieren mittels vollstandiger Induktion Man zeigt dass die Behauptungen fur den Anfang gelten Induktionsanfang nimmt an dass die Behauptung fur n displaystyle n nbsp gilt Induktionsvoraussetzung und beweist dass die Behauptung dadurch auch fur n 1 displaystyle n 1 nbsp gelten muss Induktionsschluss Beweis der ersten Behauptung F n F n 1 1 2 1 displaystyle F n F n 1 1 2 1 nbsp fur n 1 displaystyle n geq 1 nbsp Der Beweis funktioniert direkt F n 2 2 n 1 2 2 2 n 1 1 2 2 n 1 2 1 2 2 n 1 1 1 2 1 F n 1 1 2 1 displaystyle F n 2 2 n 1 2 2 cdot 2 n 1 1 2 2 n 1 2 1 color red 2 2 n 1 1 1 2 1 color red F n 1 1 2 1 nbsp was zu zeigen war displaystyle Box nbsp dd Beweis der zweiten Behauptung F n F n 1 2 2 n 1 F 0 F 1 F n 2 displaystyle F n F n 1 2 2 n 1 cdot F 0 cdot F 1 cdot ldots cdot F n 2 nbsp fur n 2 displaystyle n geq 2 nbsp Der Beweis funktioniert mittels vollstandiger Induktion Induktionsanfang 17 F 2 F 1 2 2 2 1 F 0 5 2 2 1 3 5 2 2 3 5 4 3 17 displaystyle 17 F 2 F 1 2 2 2 1 cdot F 0 5 2 2 1 cdot 3 5 2 2 cdot 3 5 4 cdot 3 17 nbsp 257 F 3 F 2 2 2 3 1 F 0 F 1 17 2 4 3 5 17 16 3 5 17 240 257 displaystyle 257 F 3 F 2 2 2 3 1 cdot F 0 cdot F 1 17 2 4 cdot 3 cdot 5 17 16 cdot 3 cdot 5 17 240 257 nbsp dd Induktionsvoraussetzung F n F n 1 2 2 n 1 F 0 F 1 F n 2 displaystyle F n F n 1 2 2 n 1 cdot F 0 cdot F 1 cdot ldots cdot F n 2 nbsp bzw umgeformt F 0 F 1 F n 2 F n F n 1 2 2 n 1 displaystyle F 0 cdot F 1 cdot ldots cdot F n 2 frac F n F n 1 2 2 n 1 nbsp Induktionsschluss zu zeigen F n 1 F n 2 2 n F 0 F 1 F n 1 displaystyle F n 1 F n 2 2 n cdot F 0 cdot F 1 cdot ldots cdot F n 1 nbsp F n 1 F n 1 2 1 erste obige Behauptung F n 2 2 F n 1 1 F n 1 2 2 n 1 F 0 F 1 F n 2 2 2 F n 1 2 2 n 1 F 0 F 1 F n 2 2 Induktionsvoraussetzung F n 1 2 2 2 2 n 1 F 0 F 1 F n 2 F n 1 2 2 n 1 2 F 0 2 F 1 2 F n 2 2 2 F n 1 2 2 2 n 1 F 0 F 1 F n 2 2 F n 1 2 2 F n 1 1 1 2 2 n 1 F 0 F 1 F n 2 2 F n 1 2 2 n 1 F 0 F 1 F n 2 2 F n 1 1 2 1 2 2 n F 0 F 1 F n 2 2 2 2 n 1 F n 1 F 0 F 1 F n 2 2 2 2 n 1 F n 2 2 n F 0 F 1 F n 2 2 2 2 n 1 F n 1 F n F n 1 2 2 n 1 2 2 2 n 1 umgeformte Induktionsvoraussetzung F n 2 2 n F 0 F 1 F n 2 2 F n 1 F n F n 1 2 2 2 n 1 F n 2 2 n F 0 F 1 F n 2 F n 1 F n 2 2 2 n 1 F n 2 2 n F 0 F 1 F n 2 2 2 n 1 1 2 2 n 1 2 2 2 n 1 Definition von Fermat Zahlen F n 2 2 n F 0 F 1 F n 2 2 2 n 1 2 2 n 2 2 n 1 F n 2 2 n F 0 F 1 F n 2 2 2 n 1 1 2 2 n 1 2 2 n 1 F n 2 2 n F 0 F 1 F n 2 2 2 n 1 1 F n 2 2 n F 0 F 1 F n 2 F n 1 Definition von Fermat Zahlen displaystyle begin array rcll F n 1 amp amp F n 1 2 1 amp text erste obige Behauptung amp amp color red F n 2 2 color magenta F n 1 1 amp amp color red F n 1 2 2 n 1 F 0 F 1 ldots F n 2 2 2 cdot color magenta F n 1 2 2 n 1 F 0 F 1 ldots F n 2 2 amp text Induktionsvoraussetzung amp amp F n 1 2 2 cdot 2 2 n 1 F 0 F 1 ldots F n 2 F n 1 2 2 n 1 2 F 0 2 F 1 2 ldots F n 2 2 2F n 1 2 cdot 2 2 n 1 F 0 F 1 ldots F n 2 2 amp amp F n 1 2 2F n 1 1 1 2 2 n 1 F 0 F 1 ldots F n 2 cdot 2F n 1 2 2 n 1 F 0 F 1 ldots F n 2 2 amp amp color magenta F n 1 1 2 1 2 2 n F 0 F 1 ldots F n 2 cdot frac 2 2 2 n 1 F n 1 color red F 0 F 1 ldots F n 2 frac 2 2 2 n 1 amp amp color magenta F n 2 2 n F 0 F 1 ldots F n 2 cdot frac 2 2 2 n 1 F n 1 color red frac F n F n 1 2 2 n 1 frac 2 2 2 n 1 amp text umgeformte Induktionsvoraussetzung amp amp F n 2 2 n F 0 F 1 ldots F n 2 cdot frac 2F n 1 F n F n 1 2 2 2 n 1 amp amp F n 2 2 n F 0 F 1 ldots F n 2 cdot frac color red F n 1 color magenta F n 2 2 2 n 1 amp amp F n 2 2 n F 0 F 1 ldots F n 2 cdot frac color red 2 2 n 1 1 color magenta 2 2 n 1 2 2 2 n 1 amp text Definition von Fermat Zahlen amp amp F n 2 2 n F 0 F 1 ldots F n 2 cdot frac 2 2 n 1 2 2 n 2 2 n 1 amp amp F n 2 2 n F 0 F 1 ldots F n 2 cdot frac 2 2 n 1 cdot 1 2 2 n 1 2 2 n 1 amp amp F n 2 2 n F 0 F 1 ldots F n 2 cdot color red 2 2 n 1 1 amp amp F n 2 2 n F 0 F 1 ldots F n 2 cdot color red F n 1 amp text Definition von Fermat Zahlen end array nbsp dd Was zu zeigen war displaystyle Box nbsp Beweis der dritten Behauptung F n F n 1 2 2 F n 2 1 2 displaystyle F n F n 1 2 2 cdot F n 2 1 2 nbsp fur n 2 displaystyle n geq 2 nbsp Der Beweis funktioniert direkt F n 2 2 n 1 2 2 2 n 1 2 2 2 n 1 1 2 2 2 n 1 2 2 n 1 2 2 2 2 n 1 1 2 2 2 2 n 2 2 2 n 1 1 2 2 2 2 n 2 2 F n 1 2 2 2 2 n 2 1 1 2 F n 1 2 2 F n 2 1 2 displaystyle begin array rcll F n 2 2 n 1 amp amp 2 2 cdot 2 n 1 2 cdot 2 2 n 1 1 2 cdot 2 2 n 1 amp amp 2 2 n 1 2 2 cdot 2 2 n 1 1 2 cdot 2 2 cdot 2 n 2 amp amp color red 2 2 n 1 1 2 2 cdot 2 2 n 2 2 amp amp color red F n 1 2 2 cdot 2 2 n 2 1 1 2 amp amp F n 1 2 2 cdot F n 2 1 2 end array nbsp dd Was zu zeigen war displaystyle Box nbsp Beweis der vierten Behauptung F n F 0 F 1 F n 1 2 displaystyle F n F 0 cdot F 1 cdot ldots cdot F n 1 2 nbsp fur n 1 displaystyle n geq 1 nbsp Der Beweis funktioniert mittels vollstandiger Induktion Induktionsanfang 5 F 1 F 0 2 3 2 5 displaystyle 5 F 1 F 0 2 3 2 5 nbsp 17 F 2 F 0 F 1 2 3 5 2 15 2 17 displaystyle 17 F 2 F 0 cdot F 1 2 3 cdot 5 2 15 2 17 nbsp dd Induktionsvoraussetzung F n F 0 F 1 F n 1 2 displaystyle F n F 0 cdot F 1 cdot ldots cdot F n 1 2 nbsp Induktionsschluss zu zeigen F n 1 F 0 F 1 F n 2 displaystyle F n 1 F 0 cdot F 1 cdot ldots cdot F n 2 nbsp F n 1 F n 1 2 1 erste obige Behauptung F n 2 2 F n 1 1 F 0 F 1 F n 1 2 2 2 F 0 F 1 F n 1 2 2 Induktionsvoraussetzung F 0 2 F 1 2 F n 1 2 4 F 0 F 1 F n 1 4 2 F 0 F 1 F n 1 4 2 F 0 2 F 1 2 F n 1 2 2 F 0 F 1 F n 1 2 F 0 F 1 F n 1 F 0 F 1 F n 1 2 2 F 0 F 1 F n 1 F n 2 Induktionsvoraussetzung displaystyle begin array rcll F n 1 amp amp F n 1 2 1 amp text erste obige Behauptung amp amp color red F n 2 2 color magenta F n 1 1 amp amp color red F 0 F 1 ldots F n 1 2 2 2 color magenta F 0 F 1 ldots F n 1 2 2 amp text Induktionsvoraussetzung amp amp F 0 2 F 1 2 ldots F n 1 2 4F 0 F 1 ldots F n 1 4 2F 0 F 1 ldots F n 1 4 2 amp amp F 0 2 F 1 2 ldots F n 1 2 2F 0 F 1 ldots F n 1 2 amp amp F 0 F 1 ldots F n 1 cdot color red F 0 F 1 ldots F n 1 2 2 amp amp F 0 F 1 ldots F n 1 cdot color red F n 2 amp text Induktionsvoraussetzung end array nbsp dd Was zu zeigen war displaystyle Box nbsp Es gelten folgende Darstellungen von F n displaystyle F n nbsp Jede Fermat Zahl F n displaystyle F n nbsp mit n 1 displaystyle n geq 1 nbsp ist von der Form 6 m 1 displaystyle 6m 1 nbsp wobei m N displaystyle m in mathbb N nbsp positiv ganzzahlig ist mit anderen Worten F n 1 mod 6 displaystyle F n equiv 1 pmod 6 nbsp 15 Jede Fermat Zahl F n displaystyle F n nbsp mit n 1 displaystyle n geq 1 nbsp ist von der Form 4 m 1 displaystyle 4m 1 nbsp wobei m N displaystyle m in mathbb N nbsp positiv ganzzahlig ist mit anderen Worten F n 1 mod 4 displaystyle F n equiv 1 pmod 4 nbsp Jede Fermat Zahl F n displaystyle F n nbsp mit n 1 displaystyle n geq 1 nbsp ist von der Form 3 m 2 displaystyle 3m 2 nbsp wobei m N displaystyle m in mathbb N nbsp positiv ganzzahlig ist mit anderen Worten F n 2 mod 3 displaystyle F n equiv 2 pmod 3 nbsp Jede Fermat Zahl F n displaystyle F n nbsp mit n 2 displaystyle n geq 2 nbsp ist von der Form 10 m 7 displaystyle 10m 7 nbsp wobei m N displaystyle m in mathbb N nbsp positiv ganzzahlig ist mit anderen Worten F n 7 mod 10 displaystyle F n equiv 7 pmod 10 nbsp Anders formuliert Mit Ausnahme von F 0 3 displaystyle F 0 3 nbsp und F 1 5 displaystyle F 1 5 nbsp endet jede Fermat Zahl im Dezimalsystem mit der Ziffer 7 Die letzten beiden Ziffern sind 17 37 57 oder 97 16 dd Beweis der vier Behauptungen Beweis der ersten Behauptung F n 1 mod 6 displaystyle F n equiv 1 pmod 6 nbsp Der Beweis funktioniert direkt Man startet mit einer bekannten richtigen Aussage und beweist das Gewunschte Eine weiter oben angegebene Eigenschaft besagt dass F n F 0 F 1 F n 1 2 displaystyle F n F 0 cdot F 1 cdot ldots cdot F n 1 2 nbsp gilt fur n 1 displaystyle n geq 1 nbsp Somit gilt aber weil F 0 3 displaystyle F 0 3 nbsp ist F n 1 F 0 F 1 F n 1 3 3 F 1 F n 1 3 3 F 1 F n 1 1 displaystyle F n 1 F 0 cdot F 1 cdot ldots cdot F n 1 3 3 cdot F 1 cdot ldots cdot F n 1 3 3 cdot F 1 cdot ldots cdot F n 1 1 nbsp dd Der Ausdruck F 1 F n 1 displaystyle F 1 cdot ldots cdot F n 1 nbsp ist als Produkt von ungeraden Fermat Zahlen selber ungerade Addiert man 1 dazu erhalt man eine gerade Zahl Also ist F n 1 displaystyle F n 1 nbsp ein Produkt aus 3 und einer geraden Zahl und somit durch 6 teilbar Es gibt also ein m N displaystyle m in mathbb N nbsp mit F n 1 6 m displaystyle F n 1 6m nbsp Daher ist F n displaystyle F n nbsp von der Form 6 m 1 displaystyle 6m 1 nbsp was zu zeigen war displaystyle Box nbsp dd Beweis der zweiten Behauptung F n 1 mod 4 displaystyle F n equiv 1 pmod 4 nbsp F n 2 2 n 1 2 2 2 n 2 1 4 2 n 1 1 1 mod 4 displaystyle F n 2 2 n 1 2 2 frac 2 n 2 1 4 2 n 1 1 equiv 1 pmod 4 nbsp was zu zeigen war displaystyle Box nbsp Beweis der dritten Behauptung F n 2 mod 3 displaystyle F n equiv 2 pmod 3 nbsp Der dritte Beweis funktioniert mit vollstandiger Induktion Induktionsanfang F 1 2 2 1 1 5 3 1 2 2 mod 3 displaystyle F 1 2 2 1 1 5 3 cdot 1 2 equiv 2 pmod 3 nbsp F 2 2 2 2 1 17 3 5 2 2 mod 3 displaystyle F 2 2 2 2 1 17 3 cdot 5 2 equiv 2 pmod 3 nbsp dd Induktionsvoraussetzung F n 3 k 2 displaystyle F n 3 cdot k 2 nbsp Induktionsschluss zu zeigen F n 1 3 m 2 displaystyle F n 1 3 cdot m 2 nbsp fur ein m N displaystyle m in mathbb N nbsp F n 1 F n 1 2 1 erste Behauptung weiter oben F n 2 2 F n 1 1 3 k 2 2 2 3 k 2 2 Induktionsvoraussetzung 9 k 2 12 k 4 6 k 4 2 9 k 2 6 k 2 3 3 k 2 2 k 2 3 m 2 mit m 3 k 2 2 k displaystyle begin array rcll F n 1 amp amp F n 1 2 1 amp text erste Behauptung weiter oben amp amp color red F n 2 2 color magenta F n 1 1 amp amp color red 3k 2 2 2 cdot color magenta 3k 2 2 amp text Induktionsvoraussetzung amp amp 9k 2 12k 4 6k 4 2 amp amp 9k 2 6k 2 amp amp 3 cdot 3k 2 2k 2 amp amp 3m 2 amp text mit m 3k 2 2k text end array nbsp dd dd Was zu zeigen war displaystyle Box nbsp Beweis der vierten Behauptung F n 7 mod 10 displaystyle F n equiv 7 pmod 10 nbsp Der vierte Beweis funktioniert direkt Weiter oben wurde gezeigt dass F n F 0 F 1 F n 1 2 displaystyle F n F 0 cdot F 1 cdot ldots cdot F n 1 2 nbsp fur n 1 displaystyle n geq 1 nbsp gilt Daraus kann man folgern dass F n 2 mod F k displaystyle F n equiv 2 pmod F k nbsp fur k 0 1 n 1 displaystyle k 0 1 ldots n 1 nbsp gilt Im Speziellen gilt also fur k 1 displaystyle k 1 nbsp also fur F 1 5 displaystyle F 1 5 nbsp die Kongruenz F n 2 mod 5 displaystyle F n equiv 2 pmod 5 nbsp und somit entweder F n 2 mod 10 displaystyle F n equiv 2 pmod 10 nbsp oder F n 7 mod 10 displaystyle F n equiv 7 pmod 10 nbsp Weil aber Fermat Zahlen immer ungerade sind kann nur die Kongruenz F n 7 mod 10 displaystyle F n equiv 7 pmod 10 nbsp zutreffen was zu zeigen war Die Aussage dass die letzten beiden Ziffern 17 37 57 oder 97 sind kann man der Literatur 16 entnehmen displaystyle Box nbsp dd Sei F n 2 2 n 1 displaystyle F n 2 2 n 1 nbsp die n displaystyle n nbsp te Fermat Zahl Dann gilt F n displaystyle F n nbsp hat unendlich viele Darstellungen der Form F n x 2 2 y 2 displaystyle F n x 2 2y 2 nbsp mit x y N displaystyle x y in mathbb N nbsp positiv ganzzahlig fur alle n 2 displaystyle n geq 2 nbsp 17 F n displaystyle F n nbsp hat mindestens eine Darstellung der Form F n x 2 y 2 displaystyle F n x 2 y 2 nbsp mit x y N displaystyle x y in mathbb N nbsp positiv ganzzahlig Ist F n displaystyle F n nbsp zusammengesetzt gibt es mehrere Moglichkeiten dieser Darstellung 18 F n displaystyle F n nbsp kann niemals als Summe von zwei Primzahlen dargestellt werden fur alle n 2 displaystyle n geq 2 nbsp 19 F n p 1 p 2 displaystyle F n not p 1 p 2 nbsp fur alle p 1 p 2 P n 2 displaystyle p 1 p 2 in mathbb P n geq 2 nbsp dd F n displaystyle F n nbsp kann niemals als Differenz von zwei p ten Potenzen geschrieben werden wenn F n displaystyle F n nbsp und p ungerade Primzahlen sind 20 F n a p b p displaystyle F n not a p b p nbsp fur alle p P p 2 displaystyle p in mathbb P p not 2 nbsp dd dd Beweis der vier Behauptungen Beweis der ersten Behauptung F n x 2 2 y 2 displaystyle F n x 2 2y 2 nbsp Der Beweis funktioniert direkt Die Existenz einer solchen Darstellung konnte schon weiter oben mit x F n 1 displaystyle x F n 1 nbsp und y F n 2 1 displaystyle y F n 2 1 nbsp gezeigt werden F n x 2 2 y 2 F n 1 2 2 F n 2 1 2 displaystyle F n x 2 2y 2 F n 1 2 2 cdot F n 2 1 2 nbsp Um unendlich viele solche Darstellungen zu erhalten betrachte man folgende Identitat 3 x 4 y 2 2 2 x 3 y 2 9 x 2 24 x y 16 y 2 2 4 x 2 12 x y 9 y 2 9 x 2 24 x y 16 y 2 8 x 2 24 x y 18 y 2 x 2 2 y 2 displaystyle begin array rcl 3x 4y 2 2 cdot 2x 3y 2 amp amp 9x 2 24xy 16y 2 2 cdot 4x 2 12xy 9y 2 amp amp 9x 2 24xy 16y 2 8x 2 24xy 18y 2 amp amp x 2 2y 2 end array nbsp dd Weil x y N displaystyle x y in mathbb N nbsp ist gilt 3 x 4 y gt x displaystyle 3x 4y gt x nbsp und 2 x 3 y gt y displaystyle 2x 3y gt y nbsp Somit kann man aus dem Darstellungspaar x y displaystyle x y nbsp fur F n displaystyle F n nbsp ein grosseres Darstellungspaar 3 x 4 y 2 x 3 y displaystyle 3x 4y 2x 3y nbsp fur F n displaystyle F n nbsp konstruieren Aus diesem kann man mit obiger Identitat das nachste grossere Darstellungspaar fur F n displaystyle F n nbsp konstruieren und so fort Man erhalt also unendlich viele Darstellungspaare fur F n displaystyle F n nbsp und somit auch unendlich viele Darstellungen von F n displaystyle F n nbsp der Form F n x 2 2 y 2 displaystyle F n x 2 2y 2 nbsp was zu zeigen war displaystyle Box nbsp Beweis der zweiten Behauptung F n x 2 y 2 displaystyle F n x 2 y 2 nbsp Der Beweis funktioniert direkt Es gilt F n 2 2 n 1 2 2 n 2 2 n 1 2 2 n 2 2 n 2 2 2 n 1 1 2 2 n 2 2 n 1 1 2 2 2 n 1 2 displaystyle F n 2 2 n 1 2 2 n 2 2 n 1 2 2 n 2 2 n 2 cdot 2 2 n 1 1 2 2 n left 2 2 n 1 1 right 2 left 2 2 n 1 right 2 nbsp dd Somit hat man zwei Zahlen x 2 2 n 1 1 displaystyle x 2 2 n 1 1 nbsp und y 2 2 n 1 displaystyle y 2 2 n 1 nbsp gefunden sodass F n x 2 y 2 displaystyle F n x 2 y 2 nbsp also die Differenz von zwei Quadratzahlen ist was zu zeigen war Die Aussage dass es mehrere solche Darstellungsmoglichkeiten als Differenz von zwei Quadratzahlen gibt wenn F n displaystyle F n nbsp zusammengesetzt ist kann man der Literatur 18 entnehmen displaystyle Box nbsp Beweis der dritten Behauptung F n p 1 p 2 displaystyle F n not p 1 p 2 nbsp Der Beweis funktioniert indirekt Man startet mit einer Behauptung und zeigt dass sie falsch ist womit die Behauptung fallengelassen werden muss und das Gegenteil gilt Alle Fermat Zahlen F n 2 2 n 1 displaystyle F n 2 2 n 1 nbsp sind als Summe einer geraden und einer ungeraden Zahl 1 immer ungerade Zahlen Primzahlen sind bis auf die erste Primzahl p 2 displaystyle p 2 nbsp immer ungerade Wenn also die ungerade Zahl F n displaystyle F n nbsp Summe von zwei Primzahlen sein soll so durfen nicht beide Primzahlen ungerade sein weil die Summe zweier ungerader Zahlen eine gerade Zahl ergibt Eine davon muss gerade sein Weil es nur eine gerade Primzahl gibt muss also 2 eine der beiden Summanden sein Der andere prime Summand ist somit F n 2 displaystyle F n 2 nbsp und es gilt trivialerweise F n 2 F n 2 displaystyle F n 2 F n 2 nbsp Es gilt aber F n 2 2 2 n 1 2 2 2 n 1 2 2 n 1 1 2 2 n 1 1 displaystyle F n 2 2 2 n 1 2 2 2 n 1 2 2 n 1 1 cdot 2 2 n 1 1 nbsp dd Somit ist aber F n 2 displaystyle F n 2 nbsp fur n 2 displaystyle n geq 2 nbsp zusammengesetzt und keine Primzahl weil sogar der kleinere der beiden Faktoren 2 2 n 1 1 2 2 2 1 1 2 2 1 3 displaystyle 2 2 n 1 1 geq 2 2 2 1 1 2 2 1 3 nbsp ist und somit eine nichttriviale Faktorisierung von F n 2 displaystyle F n 2 nbsp existiert Wir erhalten einen Widerspruch Die Annahme dass man eine Fermat Zahl als Summe zweier Primzahlen darstellen kann muss fallengelassen werden was zu zeigen war displaystyle Box nbsp Beweis der vierten Behauptung F n a p b p displaystyle F n not a p b p nbsp Der Beweis funktioniert indirekt Man startet mit einer Behauptung und zeigt dass sie falsch ist womit die Behauptung fallengelassen werden muss und das Gegenteil gilt Angenommen p P displaystyle p in mathbb P nbsp ist eine ungerade Primzahl und F n displaystyle F n nbsp kann dargestellt werden als Differenz von zwei p ten Potenzen Es sei also F n a p b p displaystyle F n a p b p nbsp Dann gilt F n a p b p a b a p 1 a p 2 b a b p 2 b p 1 displaystyle F n a p b p a b cdot a p 1 a p 2 b ldots ab p 2 b p 1 nbsp mit a gt b displaystyle a gt b nbsp dd Weil F n displaystyle F n nbsp prim ist und somit nicht zwei Teiler haben darf muss a b 1 displaystyle a b 1 nbsp sein Wegen des kleinen fermatschen Satzes ist a p a mod p displaystyle a p equiv a pmod p nbsp und b p b mod p displaystyle b p equiv b pmod p nbsp und somit gilt F n a p b p a b 1 mod p displaystyle F n a p b p equiv a b equiv 1 pmod p nbsp dd Somit muss p displaystyle p nbsp ein Teiler von F n 1 2 2 n 1 1 2 2 n displaystyle F n 1 2 2 n 1 1 2 2 n nbsp sein was aber nicht sein kann weil 2 2 n displaystyle 2 2 n nbsp nur Zweierpotenzen als Teiler hat Die Annahme muss also fallengelassen werden F n displaystyle F n nbsp kann daher nicht dargestellt werden als Differenz von zwei p ten Potenzen Was zu zeigen war displaystyle Box nbsp Sei F n 2 2 n 1 displaystyle F n 2 2 n 1 nbsp die n displaystyle n nbsp te Fermat Zahl und sei D n displaystyle D n nbsp die Anzahl der Stellen von F n displaystyle F n nbsp Dann gilt 21 D n log 10 2 2 n 1 1 log 10 2 2 n 1 2 n log 10 2 1 displaystyle D n lfloor log 10 left 2 2 n 1 right 1 rfloor approx lfloor log 10 2 2 n 1 rfloor lfloor 2 n cdot log 10 2 1 rfloor nbsp wobei mit x displaystyle lfloor x rfloor nbsp die Floor Funktion gemeint ist also die grosste ganze Zahl die kleiner oder gleich x displaystyle x nbsp ist dd Sei F n 2 2 n 1 displaystyle F n 2 2 n 1 nbsp die n displaystyle n nbsp te Fermat Zahl mit n 1 displaystyle n geq 1 nbsp Dann gilt F n displaystyle F n nbsp ist eine Primzahl genau dann wenn gilt 3 F n 1 2 1 mod F n displaystyle 3 frac F n 1 2 equiv 1 pmod F n nbsp dd Mit anderen Worten Fur n 1 displaystyle n geq 1 nbsp gilt F n P 3 F n 1 2 1 mod F n displaystyle F n in mathbb P Longleftrightarrow 3 frac F n 1 2 equiv 1 pmod F n nbsp dd Dieser Satz nennt sich Pepin Test Beweis der Behauptung Der Beweis funktioniert direkt Man startet mit dem linken Teil der Aussage und zeigt dass daraus die rechte folgert Danach startet man mit dem rechten Teil der Aussage und zeigt dass daraus die linke Seite folgert Beweis displaystyle Rightarrow nbsp Sei F n P displaystyle F n in mathbb P nbsp eine Primzahl mit n 1 displaystyle n geq 1 nbsp Man muss zeigen dass 3 F n 1 2 1 mod F n displaystyle 3 frac F n 1 2 equiv 1 mod F n nbsp ist Es gilt nach dem Eulerschein Kriterium fur das Legendre Symbol die folgende Kongruenz 3 F n 1 2 3 F n mod F n displaystyle 3 frac F n 1 2 equiv left frac 3 F n right mod F n nbsp dd Weil F n 1 mod 4 displaystyle F n equiv 1 pmod 4 nbsp und F n 2 mod 3 displaystyle F n equiv 2 pmod 3 nbsp gilt wurde weiter oben bewiesen erhalt man wegen des Quadratischen Reziprozitatsgesetzes fur das Legendre Symbol 3 F n F n 3 2 3 1 3 2 1 8 1 displaystyle left frac 3 F n right left frac F n 3 right left frac 2 3 right 1 frac 3 2 1 8 1 nbsp dd Somit erhalt man 3 F n 1 2 3 F n 1 mod F n displaystyle 3 frac F n 1 2 equiv left frac 3 F n right 1 mod F n nbsp dd Damit ist eine Richtung des obigen Satzes gezeigt worden dd displaystyle Leftarrow nbsp Sei nun 3 F n 1 2 1 mod F n displaystyle 3 frac F n 1 2 equiv 1 mod F n nbsp Man muss zeigen dass F n P displaystyle F n in mathbb P nbsp eine Primzahl ist Quadriert man diese Kongruenz erhalt man 3 F n 1 2 2 3 F n 1 1 2 1 mod F n displaystyle 3 frac F n 1 2 2 3 F n 1 equiv 1 2 1 mod F n nbsp dd Nach dem verbesserten Lucas Test folgt dass F n displaystyle F n nbsp prim ist weil F n 1 2 2 n 1 1 2 2 n displaystyle F n 1 2 2 n 1 1 2 2 n nbsp nur einen einzigen Primteiler namlich p 2 displaystyle p 2 nbsp hat und fur diesen Primfaktor p 2 displaystyle p 2 nbsp auch laut Voraussetzung 3 F n 1 p 3 F n 1 2 1 1 mod F n displaystyle 3 frac F n 1 p 3 frac F n 1 2 equiv 1 not equiv 1 pmod F n nbsp gilt dd Damit sind beide Richtungen obiger Aussage bewiesen sie hat sich somit als richtig herausgestellt displaystyle Box nbsp Fur n 2 displaystyle n geq 2 nbsp gilt 22 F n F n 1 1 2 1 mod F n 1 displaystyle F n frac F n 1 1 2 equiv 1 pmod F n 1 nbsp Sei n 2 displaystyle n geq 2 nbsp k 1 displaystyle k geq 1 nbsp und F n k displaystyle F n k nbsp prim Dann gilt 22 F n F n k 1 2 1 mod F n k displaystyle F n frac F n k 1 2 equiv 1 pmod F n k nbsp Beweis der ersten Behauptung Der Beweis funktioniert direkt Man startet mit einer bekannten richtigen Aussage und beweist mittels Umformungen und Modulo Rechnungen das Gewunschte Beweis der ersten Behauptung F n 2 2 2 n 1 2 2 2 n 1 1 2 2 2 n F n 1 2 2 2 n 2 2 2 n mod F n 1 displaystyle F n 2 2 2 n 1 2 color red 2 2 n 1 1 2 cdot 2 2 n color red F n 1 2 cdot 2 2 n equiv 2 cdot 2 2 n pmod F n 1 nbsp Somit gilt F n 2 2 2 2 2 n 2 4 2 2 n 1 4 F n 1 1 4 F n 1 4 4 2 2 mod F n 1 displaystyle F n 2 2 equiv 2 cdot 2 2 n 2 4 cdot 2 2 n 1 4 cdot F n 1 1 4 cdot F n 1 4 equiv 4 equiv 2 2 pmod F n 1 nbsp Fur k 3 displaystyle k geq 3 nbsp erhalt man F n 2 k F n 2 2 2 k 2 2 2 2 k 2 2 2 k 1 mod F n 1 displaystyle F n 2 k F n 2 2 2 k 2 equiv 2 2 2 k 2 equiv 2 2 k 1 pmod F n 1 nbsp Setzt man nun k 2 n 1 1 displaystyle k 2 n 1 1 nbsp in obiges Ergebnis ein dann erhalt man F n 2 2 n 1 1 F n 2 2 n 1 2 F n 2 2 n 1 1 1 2 F n F n 1 1 2 2 2 2 n 1 2 mod F n 1 displaystyle F n 2 2 n 1 1 F n frac 2 2 n 1 2 F n frac color red 2 2 n 1 1 1 2 F n frac color red F n 1 1 2 equiv 2 2 2 n 1 2 pmod F n 1 nbsp Die Zahl 2 2 n 1 2 displaystyle 2 2 n 1 2 nbsp ist als Potenz von 2 durch jede kleinere Potenz von 2 teilbar somit fur n 2 displaystyle n geq 2 nbsp auch durch 2 n 1 displaystyle 2 n 1 nbsp Es existiert also eine positive ganze Zahl N N displaystyle N in mathbb N nbsp mit 2 2 n 1 2 2 n 1 2 N displaystyle 2 2 n 1 2 2 n 1 cdot 2N nbsp Wenn man dies in obiges Ergebnis einsetzt erhalt man F n F n 1 1 2 2 2 2 n 1 2 2 2 n 1 2 N 2 2 n 1 1 1 2 N F n 1 1 2 N 1 2 N 1 mo