Maple is a big fat calculator
> | 23*47; |
> | C:=combinat[numbcomb]; |
> | C(43,7); |
> | 43!/7!/(43-7)!; |
> | 2^11213-1; |
> | evalf(log(%)/log(10)); |
> | isprime(%%); |
> | 16! mod 17; |
> | 18! mod 19; |
> | 22! mod 23; |
> | 22!; |
> | % mod 23; |
> | (p-1)! == p-1 mod p; |
Error, `=` unexpected
The following command creates a sequence of integers 1...100 and selects the ones that are prime
> | primes100:=select(isprime,[seq(i,i=1..100)]); |
Verify for all primes less than 100 that (p-1)! == p-1 mod p
This verifies Wilson's theorem for the primes less than 100
> | for p in primes100 do
print(p, (p-1)! mod p); end do; |
> | with(numtheory); |
Warning, the protected name order has been redefined and unprotected
> | phi; |
> | for i from 1 to 22 do
print(i, phi(i)); od; |
> | primes100; |
Recall in class we discovered:
phi(p) = p-1
phi(2^k) = 2^(k-1)
phi(2p) = p-1 (we think because there was a step in the proof where I said "clearly" and it wasn't)
> | for p in primes100 do
printf("[%d, %d] ",p, phi(p)); od; |
[2, 1] [3, 2] [5, 4] [7, 6] [11, 10] [13, 12] [17, 16] [19, 18] [23, 22] [29, 28] [31, 30] [37, 36] [41, 40] [43, 42] [47, 46] [53, 52] [59, 58] [61, 60] [67, 66] [71, 70] [73, 72] [79, 78] [83, 82] [89, 88] [97, 96]
> | for k from 1 to 10 do
printf("[%d, %d] ",k,phi(2^k)); od; |
[1, 1] [2, 2] [3, 4] [4, 8] [5, 16] [6, 32] [7, 64] [8, 128] [9, 256] [10, 512]
> | 2^9; |
The following 'verifies' the conjecture that phi(2*p) = p-1 if the last two numbers in each bracket are all the same (note that they are)
> | for p in primes100 do
printf("[2*%d, %d, %d]",p,phi(2*p),p-1); od; |
[2*2, 2, 1][2*3, 2, 2][2*5, 4, 4][2*7, 6, 6][2*11, 10, 10][2*13, 12, 12][2*17, 16, 16][2*19, 18, 18][2*23, 22, 22][2*29, 28, 28][2*31, 30, 30][2*37, 36, 36][2*41, 40, 40][2*43, 42, 42][2*47, 46, 46][2*53, 52, 52][2*59, 58, 58][2*61, 60, 60][2*67, 66, 66][2*71, 70, 70][2*73, 72, 72][2*79, 78, 78][2*83, 82, 82][2*89, 88, 88][2*97, 96, 96]
The following statement calculates phi(p^3) for all primes p<100
> | for p in primes100 do
printf("[phi(%d^3) = %d = %d] ",p, phi(p^3),p^3-p^2); od; |
[phi(2^3) = 4 = 4] [phi(3^3) = 18 = 18] [phi(5^3) = 100 = 100] [phi(7^3) = 294 = 294] [phi(11^3) = 1210 = 1210] [phi(13^3) = 2028 = 2028] [phi(17^3) = 4624 = 4624] [phi(19^3) = 6498 = 6498] [phi(23^3) = 11638 = 11638] [phi(29^3) = 23548 = 23548] [phi(31^3) = 28830 = 28830] [phi(37^3) = 49284 = 49284] [phi(41^3) = 67240 = 67240] [phi(43^3) = 77658 = 77658] [phi(47^3) = 101614 = 101614] [phi(53^3) = 146068 = 146068] [phi(59^3) = 201898 = 201898] [phi(61^3) = 223260 = 223260] [phi(67^3) = 296274 = 296274] [phi(71^3) = 352870 = 352870] [phi(73^3) = 383688 = 383688] [phi(79^3) = 486798 = 486798] [phi(83^3) = 564898 = 564898] [phi(89^3) = 697048 = 697048] [phi(97^3) = 903264 = 903264]
observations: they all have a factor of 2
guess #1 = p^k-p^(k-1)
> | flag:=true;
for k from 2 to 20 do for p in primes100 do if phi(p^k) <> p^k-p^(k-1) then print("Dave is wrong!!!"); flag:=false; fi; od; od; if flag=true then print("DAVE is right!!!"); fi; |
Conjecture: phi(p^k) = p^k-p^(k-1) = p^(k-1)(p-1)
> | primes20:=select(isprime,[seq(i,i=1..20)]); |
> | for p in primes20 do
for q in primes20 do if p<>q then printf("phi(%d*%d) = %d = %d\n",p,q,phi(p*q),p*q-p-q+1); fi; od; od; |
phi(2*3) = 2 = 2
phi(2*5) = 4 = 4
phi(2*7) = 6 = 6
phi(2*11) = 10 = 10
phi(2*13) = 12 = 12
phi(2*17) = 16 = 16
phi(2*19) = 18 = 18
phi(3*2) = 2 = 2
phi(3*5) = 8 = 8
phi(3*7) = 12 = 12
phi(3*11) = 20 = 20
phi(3*13) = 24 = 24
phi(3*17) = 32 = 32
phi(3*19) = 36 = 36
phi(5*2) = 4 = 4
phi(5*3) = 8 = 8
phi(5*7) = 24 = 24
phi(5*11) = 40 = 40
phi(5*13) = 48 = 48
phi(5*17) = 64 = 64
phi(5*19) = 72 = 72
phi(7*2) = 6 = 6
phi(7*3) = 12 = 12
phi(7*5) = 24 = 24
phi(7*11) = 60 = 60
phi(7*13) = 72 = 72
phi(7*17) = 96 = 96
phi(7*19) = 108 = 108
phi(11*2) = 10 = 10
phi(11*3) = 20 = 20
phi(11*5) = 40 = 40
phi(11*7) = 60 = 60
phi(11*13) = 120 = 120
phi(11*17) = 160 = 160
phi(11*19) = 180 = 180
phi(13*2) = 12 = 12
phi(13*3) = 24 = 24
phi(13*5) = 48 = 48
phi(13*7) = 72 = 72
phi(13*11) = 120 = 120
phi(13*17) = 192 = 192
phi(13*19) = 216 = 216
phi(17*2) = 16 = 16
phi(17*3) = 32 = 32
phi(17*5) = 64 = 64
phi(17*7) = 96 = 96
phi(17*11) = 160 = 160
phi(17*13) = 192 = 192
phi(17*19) = 288 = 288
phi(19*2) = 18 = 18
phi(19*3) = 36 = 36
phi(19*5) = 72 = 72
phi(19*7) = 108 = 108
phi(19*11) = 180 = 180
phi(19*13) = 216 = 216
phi(19*17) = 288 = 288
Looking at the data we guess (Dave guesses):
phi(p*q) = p*q - p - q + 1 = (p-1)*(q-1)
Conjecutre #2 : phi(p*q) = (p-1)*(q-1)
Question still: What is phi(p^k*q), phi(p^k*q^l), phi(p*q*r), phi(p^k*q^l*r^j), phi(p1^k1*p2^k2*p3^k3*...*pm^km)
> | for p in primes20 do
for q in primes20 do if p<>q then printf("phi(%d^2*%d) = %d\n",p,q,phi(p^2*q)); fi; od; od; |
Conjecture: phi(p^2*q) = p*(p-1)*(q-1)
Conjecture: phi(p^3*q) = p^2*(p-1)*(q-1)
Conjecture: phi(p^k*q) = p^(k-1)*(p-1)*(q-1)
Conjecutre: phi(p^k*q^l) = p^(k-1)*q^(l-1)*(p-1)*(q-1)
...
Conjecture: phi(p1^k1*p2^k2*...pm^km) = p1^(k1-1)*(p1-1)*p2^(k2-1)*(p2-1)*...*pm^(km-1)*(pm-1)
> |
Check this for the first 20 integers:
> | for n from 1 to 20 do
print([n,phi(n)]); od; |
> |
> |
> | ifactor(294); |
> |