A prime number test?
Given an integer n >= 2. Then: (a) If n is a factor of 2^n - 2, then n is prime, and (b) If n is not a factor of 2^n - 2, then n is not prime.
Are statements a and b both true? I test all the numbers up to 30, and it worked every time:
If n = 2, 2^2 - 2 = 2. 2 is a factor of 2, so 2 is prime.
If n = 3, 2^3 - 2 = 6. 3 is a factor of 6, so 3 is prime.
If n = 4, 2^4 - 2 = 14. 4 is not a factor of 14, so 4 is composite.
If n = 5, 2^5 - 2 = 30. 5 is a factor of 30, so 5 is prime.
If n = 6, 2^6 - 2 = 62. 6 is not a factor of 2, so 6 is composite.
If n = 7, 2^7 - 2 = 126. 7 is a factor of 126, so 7 is prime.
If n = 8, 2^8 - 2 = 254. 8 is not a factor of 254, so 8 is composite.
If n = 9, 2^9 - 2 = 510. 9 is not a factor of 510, so 9 is composite.
If n = 10, 2^10 - 2 = 1022. 10 is not a factor of 1022, so 10 is composite.
If n = 11, 2^11 - 2 = 2046. 11 is a factor of 2046, so 11 is prime.
If n = 12, 2^12 - 2 = 4094. 12 is not a factor of 4094, so 12 is composite.
If n = 13, 2^13 - 2 = 8190. 13 is a factor of 8190, so 13 is prime.
If n = 14, 2^14 - 2 = 16382. 14 is not a factor of 16382, so 14 is composite.
If n = 15, 2^15 - 2 = 32766. 15 is not a factor of 32766, so 15 is composite.
...and so on. If both statements are not true, where is the first counter-example??
2007-01-20
04:16:18
·
8 answers
·
asked by
Anonymous
in
Mathematics