Maple is a big fat calculator

> 23*47;

1081

> C:=combinat[numbcomb];

C := numbcomb

> C(43,7);

32224114

> 43!/7!/(43-7)!;

32224114

> 2^11213-1;

28141120136973731333931529758425841918186623820136007878924193493455151766822763138107150947456332570741987893085350715373424450164188818017893905487094143918572575715657587064784183567470706746334971...28141120136973731333931529758425841918186623820136007878924193493455151766822763138107150947456332570741987893085350715373424450164188818017893905487094143918572575715657587064784183567470706746334971...28141120136973731333931529758425841918186623820136007878924193493455151766822763138107150947456332570741987893085350715373424450164188818017893905487094143918572575715657587064784183567470706746334971...28141120136973731333931529758425841918186623820136007878924193493455151766822763138107150947456332570741987893085350715373424450164188818017893905487094143918572575715657587064784183567470706746334971...28141120136973731333931529758425841918186623820136007878924193493455151766822763138107150947456332570741987893085350715373424450164188818017893905487094143918572575715657587064784183567470706746334971...28141120136973731333931529758425841918186623820136007878924193493455151766822763138107150947456332570741987893085350715373424450164188818017893905487094143918572575715657587064784183567470706746334971...28141120136973731333931529758425841918186623820136007878924193493455151766822763138107150947456332570741987893085350715373424450164188818017893905487094143918572575715657587064784183567470706746334971...28141120136973731333931529758425841918186623820136007878924193493455151766822763138107150947456332570741987893085350715373424450164188818017893905487094143918572575715657587064784183567470706746334971...28141120136973731333931529758425841918186623820136007878924193493455151766822763138107150947456332570741987893085350715373424450164188818017893905487094143918572575715657587064784183567470706746334971...28141120136973731333931529758425841918186623820136007878924193493455151766822763138107150947456332570741987893085350715373424450164188818017893905487094143918572575715657587064784183567470706746334971...28141120136973731333931529758425841918186623820136007878924193493455151766822763138107150947456332570741987893085350715373424450164188818017893905487094143918572575715657587064784183567470706746334971...28141120136973731333931529758425841918186623820136007878924193493455151766822763138107150947456332570741987893085350715373424450164188818017893905487094143918572575715657587064784183567470706746334971...28141120136973731333931529758425841918186623820136007878924193493455151766822763138107150947456332570741987893085350715373424450164188818017893905487094143918572575715657587064784183567470706746334971...28141120136973731333931529758425841918186623820136007878924193493455151766822763138107150947456332570741987893085350715373424450164188818017893905487094143918572575715657587064784183567470706746334971...28141120136973731333931529758425841918186623820136007878924193493455151766822763138107150947456332570741987893085350715373424450164188818017893905487094143918572575715657587064784183567470706746334971...28141120136973731333931529758425841918186623820136007878924193493455151766822763138107150947456332570741987893085350715373424450164188818017893905487094143918572575715657587064784183567470706746334971...28141120136973731333931529758425841918186623820136007878924193493455151766822763138107150947456332570741987893085350715373424450164188818017893905487094143918572575715657587064784183567470706746334971...28141120136973731333931529758425841918186623820136007878924193493455151766822763138107150947456332570741987893085350715373424450164188818017893905487094143918572575715657587064784183567470706746334971...28141120136973731333931529758425841918186623820136007878924193493455151766822763138107150947456332570741987893085350715373424450164188818017893905487094143918572575715657587064784183567470706746334971...28141120136973731333931529758425841918186623820136007878924193493455151766822763138107150947456332570741987893085350715373424450164188818017893905487094143918572575715657587064784183567470706746334971...28141120136973731333931529758425841918186623820136007878924193493455151766822763138107150947456332570741987893085350715373424450164188818017893905487094143918572575715657587064784183567470706746334971...28141120136973731333931529758425841918186623820136007878924193493455151766822763138107150947456332570741987893085350715373424450164188818017893905487094143918572575715657587064784183567470706746334971...28141120136973731333931529758425841918186623820136007878924193493455151766822763138107150947456332570741987893085350715373424450164188818017893905487094143918572575715657587064784183567470706746334971...28141120136973731333931529758425841918186623820136007878924193493455151766822763138107150947456332570741987893085350715373424450164188818017893905487094143918572575715657587064784183567470706746334971...28141120136973731333931529758425841918186623820136007878924193493455151766822763138107150947456332570741987893085350715373424450164188818017893905487094143918572575715657587064784183567470706746334971...

> evalf(log(%)/log(10));

3375.449342

> isprime(%%);

true

> 16! mod 17;

16

> 18! mod 19;

18

> 22! mod 23;

22

> 22!;

1124000727777607680000

> % mod 23;

22

> (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)]);

primes100 := [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]

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;

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

> with(numtheory);

Warning, the protected name order has been redefined and unprotected

[GIgcd, bigomega, cfrac, cfracpol, cyclotomic, divisors, factorEQ, factorset, fermat, imagunit, index, integral_basis, invcfrac, invphi, issqrfree, jacobi, kronecker, lambda, legendre, mcombine, merse...[GIgcd, bigomega, cfrac, cfracpol, cyclotomic, divisors, factorEQ, factorset, fermat, imagunit, index, integral_basis, invcfrac, invphi, issqrfree, jacobi, kronecker, lambda, legendre, mcombine, merse...[GIgcd, bigomega, cfrac, cfracpol, cyclotomic, divisors, factorEQ, factorset, fermat, imagunit, index, integral_basis, invcfrac, invphi, issqrfree, jacobi, kronecker, lambda, legendre, mcombine, merse...[GIgcd, bigomega, cfrac, cfracpol, cyclotomic, divisors, factorEQ, factorset, fermat, imagunit, index, integral_basis, invcfrac, invphi, issqrfree, jacobi, kronecker, lambda, legendre, mcombine, merse...

> phi;

phi

> for i from 1 to 22 do
 print(i, phi(i));

od;

1, 1

2, 1

3, 2

4, 2

5, 4

6, 2

7, 6

8, 4

9, 6

10, 4

11, 10

12, 4

13, 12

14, 6

15, 8

16, 8

17, 16

18, 6

19, 18

20, 8

21, 12

22, 10

> primes100;

[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]

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;

512

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;

flag := true

Conjecture: phi(p^k) = p^k-p^(k-1) = p^(k-1)(p-1)

> primes20:=select(isprime,[seq(i,i=1..20)]);

primes20 := [2, 3, 5, 7, 11, 13, 17, 19]

> 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;

[1, 1]

[2, 1]

[3, 2]

[4, 2]

[5, 4]

[6, 2]

[7, 6]

[8, 4]

[9, 6]

[10, 4]

[11, 10]

[12, 4]

[13, 12]

[14, 6]

[15, 8]

[16, 8]

[17, 16]

[18, 6]

[19, 18]

[20, 8]

>

>

> ifactor(294);

(2)*(3)*(7)^2

>