Fermat Numbers.sagews

def fermatfactor(N):
       if N <= 0: return [N]
       if is_even(N): return [2,N/2]
       a = ceil(sqrt(N))
       while not is_square(a^2-N):
         a = a + 1
       b = sqrt(a^2-N)
       return [a - b,a + b]

#
#
#
#
#
#Fermat Numbers
#In mathematics a Fermat number, named after Pierre de Fermat who first studied them, is a positive integer of the form Fn = 2^2^n + 1 where n is a nonnegative integer.
#The first few Fermat numbers are: 3, 5, 17, 257, 65537, 4294967297, 18446744073709551617
#conjecture
#If Fn is prime, then it is called a Fermat Prime. Fermat conjectured that Fn is prime for all natural number n.

#a). Determine the factorization of the first few Fermat numbers.
#Do you believe Fermat's conjecture?
#F1
sage: print fermatfactor(2^2^1+1)

[1, 5]

#F2
sage: print fermatfactor(2^2^2+1)

[1, 17]

#F3
sage: print fermatfactor(2^2^3+1)

[1, 257]

#F4
#65537 is the largest known Fermat prime
sage: print fermatfactor(2^2^4+1)

[1, 65537]

#F5 is not prime, 2^2^5+1 = 4294967297 = 641*6700417
#so Fermat's conjecture is wrong
sage: print fermatfactor(2^2^5+1)

[641, 6700417]

#b). Find a recurrence relation that describes the Fermat numbers
#Fn = (Fn-1 - 1)^2 + 1 for n>=1 (can be proved by mathematical induction)
(3-1)^2+1
(5-1)^2+1
(17-1)^2+1
(257-1)^2+1
(65537-1)^2+1
(4294967297-1)^2+1

5 17 257 65537 4294967297 18446744073709551617

#Fn = F0*F1*...*Fn-1 + 2 (can be proved by mathematical induction)
3*5+2
3*5*17+2
3*5*17*257+2
3*5*17*257*65537+2
3*5*17*257*65537*4294967297+2

17 257 65537 4294967297 18446744073709551617

#c). Find the greatest common divisor of several pairs of Fermat numbers. Conjecture a general statement.
#conjecture: the greatest common divisor of Fermat numbers is always 1.

gcd(3,5)

1

gcd(17,65537)

1

gcd(17,257)

1

gcd(257,65537)

1

gcd(65537,4294967297)

1

#d). What can be said about the sum of the reciprocals of the Fermat numbers?
#    Does it converge? If yes, is the value a rational number?

1/3+1/5

8/15

1/3+1/5+1/17

151/255

1/3+1/5+1/17+1/257

39062/65535

1/3+1/5+1/17+1/257+1/65537

2560071829/4294967295

1/3+1/5+1/17+1/257+1/65537+1/4294967297

10995424787820943508/18446744073709551615

L=[[1,8/15],[2,151/255],[3,39062/65535],[4,2560071829/4294967295],[5,10995424787820943508/18446744073709551615]]
points(L)

#The sum of the reciprocals of all the Fermat numbers is irrational.
#the sum of the reciprocals of primes are diverges. (first five Fermat numbers are primes)

#e). Which Fermat numbers can be written as the sum of two primes?
#conjecture: only F1 can be written as the sum of two primes.
#F1 = 5 = 2+3
#prime numbers: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97 ......

#f). Which Fermat numbers can be written uniquely as the sum of two nonzero squares?
#conjecture: only F2 can be writte uniquely as the sum of two nonzero squares.
#17 = 1+16 = 1^2+4^2
#Fermat numbers: 3, 5, 17, 257, 65537, 4294967297, 18446744073709551617...
#nonzero squares: 1 4 9 16 25 36 49 64 81 100 121 144 169 196 225...

#i). What about more general Fermat numbers such as 2^n+1
#    1. For what n do you get a prime number?
#    2. Can you find a general form for n for which you always get a prime number?
#
#
#conjecture: 2^n+1 is prime only when n = 2^k for some positive integer k (form of Fermat numbers).
for n in range(1,50):
    D = 2^n+1
    print D
#only 3, 5 17, 257, 65537 are primes, which are the first five Fermat numbers (Fermat primes).

3 5 9 17 33 65 129 257 513 1025 2049 4097 8193 16385 32769 65537 131073 262145 524289 1048577 2097153 4194305 8388609 16777217 33554433 67108865 134217729 268435457 536870913 1073741825 2147483649 4294967297 8589934593 17179869185 34359738369 68719476737 137438953473 274877906945 549755813889 1099511627777 2199023255553 4398046511105 8796093022209 17592186044417 35184372088833 70368744177665 140737488355329 281474976710657 562949953421313

for n in range(2,100000):
    if not is_prime(n):
        carmichael = True
        for a in range(1,n):
            if Mod(a,n)^n != Mod(a,n):
                carmichael = False
                break
        if carmichael:
            print "n = ", n, "=", factor(n), "divisors of n-1   --->", factor(n-1)

n = 561 = 3 * 11 * 17 divisors of n-1 ---> 2^4 * 5 * 7 n = 1105 = 5 * 13 * 17 divisors of n-1 ---> 2^4 * 3 * 23 n = 1729 = 7 * 13 * 19 divisors of n-1 ---> 2^6 * 3^3 n = 2465 = 5 * 17 * 29 divisors of n-1 ---> 2^5 * 7 * 11 n = 2821 = 7 * 13 * 31 divisors of n-1 ---> 2^2 * 3 * 5 * 47 n = 6601 = 7 * 23 * 41 divisors of n-1 ---> 2^3 * 3 * 5^2 * 11 n = 8911 = 7 * 19 * 67 divisors of n-1 ---> 2 * 3^4 * 5 * 11 n = 10585 = 5 * 29 * 73 divisors of n-1 ---> 2^3 * 3^3 * 7^2 n = 15841 = 7 * 31 * 73 divisors of n-1 ---> 2^5 * 3^2 * 5 * 11 n = 29341 = 13 * 37 * 61 divisors of n-1 ---> 2^2 * 3^2 * 5 * 163 n = 41041 = 7 * 11 * 13 * 41 divisors of n-1 ---> 2^4 * 3^3 * 5 * 19 n = 46657 = 13 * 37 * 97 divisors of n-1 ---> 2^6 * 3^6 n = 52633 = 7 * 73 * 103 divisors of n-1 ---> 2^3 * 3^2 * 17 * 43 n = 62745 = 3 * 5 * 47 * 89 divisors of n-1 ---> 2^3 * 11 * 23 * 31 n = 63973 = 7 * 13 * 19 * 37 divisors of n-1 ---> 2^2 * 3^2 * 1777 n = 75361 = 11 * 13 * 17 * 31 divisors of n-1 ---> 2^5 * 3 * 5 * 157

carmichael

Error in lines 1-1 Traceback (most recent call last): File "/cocalc/lib/python2.7/site-packages/smc_sagews/sage_server.py", line 1188, in execute flags=compile_flags) in namespace, locals File "", line 1, in <module> NameError: name 'carmichael' is not defined

for n in range(2,200000):
    if not is_prime(n):
        carmichael = True
        for a in range(1,n):
            if Mod(a,n)^n != Mod(a,n):
                carmichael = False
                break
        if carmichael:
            print n, "=", factor(n)

561 = 3 * 11 * 17 1105 = 5 * 13 * 17 1729 = 7 * 13 * 19 2465 = 5 * 17 * 29 2821 = 7 * 13 * 31 6601 = 7 * 23 * 41 8911 = 7 * 19 * 67 10585 = 5 * 29 * 73 15841 = 7 * 31 * 73 29341 = 13 * 37 * 61 41041 = 7 * 11 * 13 * 41 46657 = 13 * 37 * 97 52633 = 7 * 73 * 103 62745 = 3 * 5 * 47 * 89 63973 = 7 * 13 * 19 * 37 75361 = 11 * 13 * 17 * 31 101101 = 7 * 11 * 13 * 101 115921 = 13 * 37 * 241 126217 = 7 * 13 * 19 * 73 162401 = 17 * 41 * 233 172081 = 7 * 13 * 31 * 61 188461 = 7 * 13 * 19 * 109

factor(101100)
factor(115920)
factor(126216)
factor(162400)
factor(172080)
factor(188460)

2^2 * 3 * 5^2 * 337 2^4 * 3^2 * 5 * 7 * 23 2^3 * 3^2 * 1753 2^5 * 5^2 * 7 * 29 2^4 * 3^2 * 5 * 239 2^2 * 3^3 * 5 * 349

Mod(21,6)

3

Mod(11^11^11,6)

121-25

96