| T.R | Title | User | Personal
Name | Date | Lines |
|---|
| 208.1 | 111111111111111111111113 (23 '1's) | ZFC::DERAMO | Daniel V. D'Eramo | Thu Oct 29 1987 20:05 | 11 |
| >> In the series: 13
>> 1113
>> 111113
>> ...
>> (odd number of '1's followed by a '3'), what's the first prime after 13?
The numbers with k '1's followed by a '3' are prime for k
k = 1, 2, 4, 8, 10, 23, ..., so the next one with an odd
number of '1's is 111111111111111111111113 (k = 23).
Dan
|
| 208.2 | x**k + 1 is prime => k = 2**n | CLT::GILBERT | Builder | Fri Oct 30 1987 12:36 | 34 |
| > In the series: 101
> 1001
> 10001
> ...
>('1' followed by n '0's followed by '1'), what's the first prime after 101?
k
Consider the number x + 1. If k > 1 is odd, we have the factorization:
2*m+1 2*m-1 2*m-3
x + 1 = (x + 1) (x - x + ... + 1)
(if k = 1, then this is not really a factorization).
We also (trivially) have the factorizations:
r*(2*m+1) r r*(2*m-1) r*(2*m-3)
x + 1 = (x + 1) (x - x + ... + 1)
n
Hence, taking r = 2 , we have:
n n n n
2 *(2*m+1) 2 2 *(2*m-1) 2 *(2*m-3)
x + 1 = (x + 1) (x - x + ... + 1)
So we have factorizations for any odd k greater than one, and the above
formula gives a (true) factorization for even k, except when 2*m+1 = 1.
k n
Thus, if x + 1 is prime, (and k > 0) we can infer that k = 2 .
n
2
So what's the next prime 10 + 1 ?
|
| 208.3 | See also note 178.17 by TURTLE::STAN | ZFC::DERAMO | Daniel V. D'Eramo | Fri Oct 30 1987 13:16 | 6 |
| >> Numbers of the form 10**n + 1 can not be prime unless n is
>> a power of 2. This is easy to see because if n = pq and (say)
>> p is odd then 10**pq + 1 is divisible by 10**q + 1. These
>> are the base 10 analog of Fermat numbers 2**(2**n) + 1. There
>> are no base 10 Fermat primes other than 101 for n <= 15
>> of (10**(2**N)) + 1.
|
| 208.4 | | CLT::GILBERT | Builder | Tue Nov 03 1987 17:58 | 6 |
| Is it a mere coincidence that
n
2 - 1 n
2 2
10 + 1 has 2 + 1 as a prime factor, for n = 2, 3, and 4?
|
| 208.5 | Yes | ZFC::DERAMO | Daniel V. D'Eramo | Mon Nov 16 1987 17:55 | 1 |
| Yes
|
| 208.6 | | CLT::GILBERT | Builder | Tue Nov 17 1987 12:52 | 8 |
| Okay. The 2^(2^n)+1 are Fermat primes. For a few small values of n,
what are the values of K for which:
n
2 - 1 n
2 2
K + 1 has 2 + 1 as a factor?
|
| 208.7 | Could you expand on .5 a little more? | ZFC::DERAMO | Daniel V. D'Eramo | Tue Nov 17 1987 18:16 | 26 |
| Re: .4
>> Is it a mere coincidence that
>>
>> n
>> 2 - 1 n
>> 2 2
>> 10 + 1 has 2 + 1 as a prime factor, for n = 2, 3, and 4?
My "YES" in .5 was based on:
n
2 - 1 n
2 2
10 + 1 is not divisible by 2 + 1 for 5 <= n <= 10.
n
2 - 1 n
2 2
Also, 10 + 1 is not divisible by k2 + 1 for n = 5 and
1 <= k <= 10000; and for n = 6 and 1 <= k <= 5000.
All this assumes, of course, that there were no bugs in my
code! :^)
Dan
|
| 208.8 | Re .6: here are some K | ZFC::DERAMO | Daniel V. D'Eramo | Tue Nov 17 1987 19:33 | 38 |
| >> Okay. The 2^(2^n)+1 are Fermat primes. For a few small values of n,
>> what are the values of K for which:
>>
>> n
>> 2 - 1 n
>> 2 2
>> K + 1 has 2 + 1 as a factor?
I looked for such K with 3 <= K <= 100, and found the
following values of K for small n:
n = 2
3 5 6 7 10 11 12 14 20 22 23 24 27 28 29 31 37 39 40 41 44
45 46 48 54 56 57 58 61 62 63 65 71 73 74 75 78 79 80 82 88 90
91 92 95 96 97 99
n = 3
3 5 6 7 10 12 14 19 20 24 27 28 33 37 38 39 40 41 43 45 47
48 51 53 54 55 56 63 65 66 69 71 74 75 76 77 78 80 82 83 85 86
87 90 91 93 94 96 97
n = 4
3 5 6 7 10 11 12 14 20 22 23 24 27 28 29 31 39 40 41 43 44
45 46 47 48 51 54 56 57 58 59 61 62 63 65 67 73 75 78 80 82 83
85 86 88 89 90 91 92 94 95 96 99
n = 5
No such K, 3 <= K <= 100
I haven't checked for any patterns in this, but obviously
something happens when we reach n = 5. It is interesting
that the Fermat numbers stop being prime there ...
Dan
|
| 208.9 | Arrrrrggggghhhhhhhhhhh!!!!!!!!! | ZFC::DERAMO | Daniel V. D'Eramo | Wed Nov 18 1987 06:00 | 54 |
| Re: .4
Is it a mere coincidence that
>> n
>> 2 - 1 n
>> 2 2
>> 10 + 1 has 2 + 1 as a prime factor, for n = 2, 3, and 4?
Re: .5
>> Yes
Re: .6
>> Okay. The 2^(2^n)+1 are Fermat primes. For a few small values of n,
>> what are the values of K for which:
>>
>> n
>> 2 - 1 n
>> 2 2
>> K + 1 has 2 + 1 as a factor?
Re: .8
>> I haven't checked for any patterns in this, but obviously
>> something happens when we reach n = 5. It is interesting
>> that the Fermat numbers stop being prime there ...
I can't believe you slipped this one past me!! Just last
week I was using a theorem stated by Proth in 1878:
Let 0 < k < 2^m and n = k*2^n + 1. Suppose k is odd
and is not a perfect square modulo n. Then n is prime
if and only if it is a factor of a^(n-1)/2 + 1.
In the special case that k is also not divisible by 3
then 3 is suitable as the value of a for the test.
I verified the book's [Enrichment Mathematics for High
School] claim that 5*2^1947 + 1 was a prime using this test.
I was misled by a result that I read soon afterwards, that
composite Fermat primes are divisible by a prime of the form
k*2^m+2 + 1 [for Fm = 2^(2^m) + 1 composite, m > 1]. That
is why I did the testing in .6.
What I missed here was that K^(2^(2^m - 1)) *is* K^(n-1)/2
for n = Fm = 2^(2^n) + 1. So, by Proth's theorem, Fm =
2^(2^m) + 1 is prime if and only if a^(2^(2^m - 1)) + 1 is
divisible by Fm for a a quadratic nonresidue mod Fm. Things
stopped dividing at m=5 because that's where the Fermat
numbers stopped being prime. So I retarct .5: No, it is
not a coincidence.
Dan
|
| 208.10 | | CLT::GILBERT | Builder | Wed Nov 18 1987 11:14 | 47 |
| Re .8:
n = 1
K = {�2} (mod 5)
n = 2
K = {�3, �5, �6, �7} (mod 17)
n = 3
K = {�3, �5, �6, �7, �10, �12, �14, �19, �20, �24, ...} (mod 257)
I spent some time looking at 'squaring tables' like the following (for 17):
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 -1 <- K mod 17
0 4 9 -1 8 2 15 13 13 15 2 8 -1 9 4 <- K^2 mod 17
0 -1 13 13 4 4 -1 -1 4 4 13 13 -1 <- K^4 mod 17
0 -1 -1 -1 -1 -1 -1 -1 -1 <- K^8 mod 17
Omitted entries are 1 (once a column goes to 1, it stays there). So,
1
2
K + 1 is a multiple of 17, for K = {�4} (mod 17)
2
2
K + 1 is a multiple of 17, for K = {�2, �8} (mod 17)
3
2
K + 1 is a multiple of 17, for K = {�3, �5, �6, �7} (mod 17)
The above, and the trivial (K,m) = (16,0) are the only solutions
to K^(2^m)+1 = 0 (mod 17).
The 'squaring table' for modulo 33 is quite different -- not all
the numbers eventually cycle at 1. Note .9 indicates why (I think).
> composite Fermat primes are divisible by a prime of the form
> k*2^m+2 + 1 [for Fm = 2^(2^m) + 1 composite, m > 1].
Does this also apply to the K^(2^m)+1 analogy to Fermat numbers?
|
| 208.11 | What is a "composite Fermat prime"? :^) | ZFC::DERAMO | Daniel V. D'Eramo | Wed Nov 18 1987 13:25 | 24 |
| Re .9,.10
>> > composite Fermat primes are divisible by a prime of the form
>> > k*2^m+2 + 1 [for Fm = 2^(2^m) + 1 composite, m > 1].
>>
>> Does this also apply to the K^(2^m)+1 analogy to Fermat numbers?
I can't believe I called them "composite Fermat primes"!
I also stated it incorrectly. It should read
If a prime p divides the Fermat number Fm = 2^(2^m) + 1
for some m > 1, then p is of the form k * 2^(m+2) + 1
for some integer k.
I don't see this applying to the K^(2^m) + 1 numbers; those were
divisible by Fermat numbers Fm if and only if Fm is prime. I think
proving Proth's Theorem for Fermat numbers only is actually not
very difficult if you understand quadratic reciprocity. I will
try to generalize that proof [don't have the title of it here with
me] to a proof of Proth's Thm. and see if it is possible to
generalize it further to the K^(2^m) + 1 numbers.
Dan
|
| 208.12 | a correction to .9 | ZFC::DERAMO | Take my advice, I'm not using it | Sat Apr 02 1988 14:05 | 26 |
| Re my .9:
� a theorem stated by Proth in 1878:
�
� Let 0 < k < 2^m and n = k*2^n + 1. Suppose k is odd
� and is not a perfect square modulo n. Then n is prime
� if and only if it is a factor of a^(n-1)/2 + 1.
�
� In the special case that k is also not divisible by 3
� then 3 is suitable as the value of a for the test.
Sorry, I really messed that one up. The statement of the theorem
should read:
Let 0 < k < 2^m and n = k*2^m + 1. Suppose k is odd
and a is not a perfect square modulo n. Then n is prime
if and only if it is a factor of a^((n-1)/2) + 1.
In the special case that k is also not divisible by 3
then 3 is suitable as the value of a for the test.
I.e., the exponent of 2 is m in n=k*2^m + 1 [I had had n],
and it is the new constant "a" [not k] that is not a perfect
square modulo n.
Dan
|
| 208.13 | the proof of the first part | ZFC::DERAMO | Take my advice, I'm not using it | Sat Apr 02 1988 15:45 | 81 |
| Re my .9, as corrected in .12:
� a theorem stated by Proth in 1878:
�
� Let 0 < k < 2^m and n = k*2^m + 1. Suppose k is odd
� and a is not a perfect square modulo n. Then n is prime
� if and only if it is a factor of a^((n-1)/2) + 1.
�
� In the special case that k is also not divisible by 3
� then 3 is suitable as the value of a for the test.
A sketch of the proof of the first part follows.
Let 0 < k < 2^m and n = k*2^m + 1, where k is odd and
a is not a perfect square modulo n.
==> If n is prime then n is a factor of a^((n-1)/2) + 1.
a
The "Legendre symbol" (-) [the parenthesis should be drawn larger]
p
for prime p and integer a is defined to be 0 if p divides a,
1 if p does not divide a and a is a perfect square modulo p,
and -1 if p does not divide a and a is not a perfect square
modulo p. A theorem of Euler's is that for odd primes p and
any integer a,
a (p-1)/2
(-) = a (modulo p)
p
So if n is prime and a is not a perfect square mod n, then the
Legendre symbol on the left hand side is -1, and so Euler's
theorem says -1 = a^((n-1)/2) (modulo n), i.e., n divides
a^((n-1)/2) + 1.
Obviously, this is the easy half of the theorem.
<== If n is a factor of a^((n-1)/2) + 1, then n is prime.
It is given that n divides a^((n-1)/2) + 1, and so it follows that
a^((n-1)/2) = -1 (modulo n). Squaring both sides of that gives
a^(n-1) = 1 (modulo n), or n divides a^(n-1) - 1.
Let q be any prime divisor of n. n is odd so q is odd. Since q
divides n and n divides a^(n-1) - 1, then q divides a^(n-1) - 1,
or a^(n-1) = 1 (modulo q). There is a least positive integer,
call it y, such that a^y = 1 (modulo q), and such y must also
divide n-1.
Does 2^m divide y? Well, y divides n-1 = k*2^m where k is odd.
So we can write y as u*2^w where uv = k [so u and v are both odd]
and 0 <= w <= m. If w < m, i.e., 2^m does not divide y, then let
x = v*2^(m-w-1). Note that yx = (u*2^w)*(v*2^(m-w-1)) and
regrouping yx = (uv)*2^(m-1) = k*2^(m-1) = (n-1)/2. Now we know
that a^(yx) (modulo q) = (a^y)^x (modulo q) = 1^x (modulo q) =
1 (modulo q) so q divides a^(yx) - 1 = a^((n-1)/2) - 1. And
q divides n which divides a^((n-1)/2) + 1. So q divides both
these numbers and so divides their difference, which is 2.
But an odd prime cannot divide into 2; this a contradiction. So
the assumption that 2^m does not divide y is false, and it must
be the case that 2^m divides y.
Now, the order of a modulo q is divisible by 2^m and so the order
is at least 2^m. Also, Fermat's little theorem states a^(q-1) = 1
(modulo q) and so the order y is at most q-1. That is,
2^m <= y <= q-1. Therfore q >= 2^m + 1. Since 0 < k < 2^m, it
is also true that q > k + 1.
Now q is any prime dividing n. Let Q be the smallest divisor of n
that is greater than 1, i.e., the smallest prime divisor of n.
If n is not prime, then n/Q divides n, is not one, and so Q <= n/Q
i.e., Q^2 <= n. Multiplying Q >= 2^m + 1 and Q > k+1 gives
n >= Q^2 > (2^m + 1)(k + 1) = k*2^m + 1 + (k + 2^m) = n + (k +
2^m), i.e., n > n + (k + 2^m) which contradicts 0 < k < 2^m.
So Q, the smallest prime dividing n, must be n itself. So n is
prime.
Dan
|
| 208.14 | second part, special case (n prime, k=1) | ZFC::DERAMO | Take my advice, I'm not using it | Sat Apr 02 1988 15:58 | 36 |
| � a theorem stated by Proth in 1878:
�
� Let 0 < k < 2^m and n = k*2^m + 1. Suppose k is odd
� and a is not a perfect square modulo n. Then n is prime
� if and only if it is a factor of a^((n-1)/2) + 1.
�
� In the special case that k is also not divisible by 3
� then 3 is suitable as the value of a for the test.
A special case of the second part. Let k=1, so that n=2^m + 1.
If m>0 [because k < 2^m] is not a power of 2, then n is
composite. So let m=2^a, consider the Fermat number n=2^(2^a) +1.
According to the special case, we can let a be 3. So the Fermat
number n = 2^(2^a) + 1 is prime if and only if n divides
3^((n-1)/2) + 1.
If p = 2^(2^a) + 1 is indeed prime [a Fermat prime, instead of
just a Fermat number], then you can use the quadratic reciprocity
theorem to compute the Legendre symbols
3 p ((p-1)/2)((q-1)/2)
(-) * (-) = (-1)
p 3
and this will work out to (for p > 3, so use a > 0 in p = 2^(2^a) + 1)
show that
3
(-) = -1
p
which means that 3 is not a perfect square modulo p, which the
second part of Proth's theorem said it would be.
Dan
|
| 208.15 | trivia | ZFC::DERAMO | Take my advice, I'm not using it | Sat Apr 02 1988 16:07 | 14 |
| The previous two notes show that if a>1 and p = 2^(2^a) + 1
is a prime [a Fermat prime], then 3 is a primitive root for p.
This is true because 3^(p-1) = 1 (modulo p) but 3^y ~= 1 (modulo p)
for any smaller y. Such y would have to be a power of two
dividing (p-1)/2 [2 is the only prime dividing p-1] but we know
that 3^((p-1)/2) = -1 (modulo p). So 3 is a generator for the
cyclic group of nonzero integers modulo p, i.e., a primitive
root of p.
This is useful to know when constructing regular p-gons with
only compass and straight-edge. (see note 847).
Dan
|