Maple is a big fat calculator23*47;

NiMiJSIzIg==

C:=combinat[numbcomb];

NiM+SSJDRzYiSSludW1iY29tYkc2JEkqcHJvdGVjdGVkR0YoL0krbW9kdWxlbmFtZUdGJUkpY29tYmluYXRHNiRGKEkoX3N5c2xpYkdGJQ==

C(43,7);

NiMiKTlUQUs=

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

NiMiKTlUQUs=

2^11213-1;

NiMiW154Ij4jUidwKDN3OVJuaXoleSpvVDBvJCk9KFw5Q1U1eS0uRlYxISlcJVJeJEdOQmdSQ2cnZUYmPW5lbyZ5XHM/LjlwYyhvInpyVj1kYmNJWV5fWiZwKVI7ISk9biI9KHpXWEkpZmpkcktwTyczT0dDT05yVVRhc1pNUDJpZD13UlpaKjQuaiM0Sl14bmE1eCxPPklZOScpRydRPWdAWydcXlJBeFwwVl9eNC4kUXhIKkc9aj9jVUleLypmcTtoIlJDSTAyOz9BPCVcdXIwejA4NmlFXnh2MmUqKSoqKnl2MD9QNFJPNXFaKVsqPmFPa3Q/JFxAYnhtO10tLyZwXXQ2NFhnQXF3X1ByIilHcEJmPiRIc2owP0JOLic+ZXVbZEdKP1d2I1FuJyplU0Z1KFJQak1Zc0JMQCtcJDQlUTZgUU9qSi8uQEVlcEkvYm9TS3Qpb3V0LHN4JFsmNC9UO1orWU4xMTovPXl5R1tsR288eSJILXoqZWdgZik+PEEielAlXEcpKVJAQnRxcDZ4MWFQTUU7JjNNQSp6PydlJDNLJykqKlF4dlkleVRnTyV5L2FASUpjKD4vIjRTTEBUMyRIeT1cIUg6KDNlIipRVHY9LT54IVtMMVVkRiI+KjRqIm9uUldCYmpBcixLKUhINWV2VE1ndS8ud3NFVD5vKGYlPVZEQSM0YitqaSdHTidIPTE9eHdhTV1UXGpGNGpxMGImeUEjKTMpZU0nW0JiZykpKmUsR245Q20xT3hEZm0pNFRBIlxwZGdMKClRd1hvN3NoR1NGKDM/LyN5eVZVJD01dydILTp6bVJNTm9WRzRCM05zI3kjZjpXeEB6UydvUGFsK3MjemN4QiQpUSJceEZiYyV6Zj8raT4qUk0vPCdSLitHNUdwYzF2cTRoa0EoPSdHRXg/TVFvMDNSLC41Vj53YHlaQlRPYVVvWSZcKjMoXEIkek9wYUM3ZFdEVSxcO1V5LWYsdmdiIj1WOCt0JT54LisydGI/bWdociJlaFooPnAiUVYpKSozZmBaOjZLeTRjU2dgTmNzTi5pSC5qemgzYWlGTDEjKWVGQjRVdDZfZSI0XWxkXnAlZjdVIyo+SyZIJFw0cFVeWldKT3dvMSY0VCdRS0YlZWtnNWFEZl1qXFgpUUZfWzkwTDo7MVp1VG1ER3A6a3dlX2szaCplJVJ1MS5eKXl4KiplPWw9JXkiSDJTLWQnKXkoPSMpPTdgKCk+Z10qeWU/NmwkbyFSSUZHeC1NLFY+XmQ+MCEqKSp5QDguJUhdNmBbRC4wPj47JnlaRm9PX2UqKWZXczQjNDBfXURPQEdVMDArNyEpW3lKejwsRG9ARF1tPis7UF1obmR5J1JSLkMnPlokKip5WyEpWyRwalVWR0IoR2RPdVw2YU0xcT1BdTciUSNHLkAmeilbKnpoJz5DIlI+U144TSkqeUhGWDN5SyVSJEhYJDM2M1sqW2FQeGVwUyopUSpIekg7ZEtbSFNIUVxocTYjUlVEKVtleVAlR2paMldmIioqW1oxSjRReUQlPmgzITRWIWVKajE5azw8KCpSI0coPTpJRFkmNERbRyR6U3E1Jio9JjRDR2A+MV9iJDRSPycpPVlnL1pfbmU5MzVJTyY0Py1qYU5EUCFlWzl1QkAoejBNPEFoRTB3J1F2VzM6UyQ9TDh5Qyd5OT92NkJFMCMqR25kc2N6S1g9RVlxd3ooXCp5TkpjZSJRUy0tZGwnWyoqKSkzJFIxI2VEYjpaPVEub0skSEp3PyVIXGlBUjgzSyM0ajJVK2tlKyp6dCM+Typ6MlYrJ1JVZ2IvY0FSY2pLOVIxJT43RGRrJFEjW0spZlIvXF5NajxYNyFvLWdMJGYkPXh4NTQ7JSpwKFJsRyh5amptSE5qI3AncCJHRlBoRlFKOmx3Ym86dVBnYGQ8NFBtXy9ydV5ScjtcbGMiKSlvJEgqb09oczU/JCpHREBSOllSUiR5aUBUVE1MMmFVJFtcXUFcbjInKik0SmN6WSpHd0hAMyN5NXYiWyJ6OCxGWHQsPHZhayVvIz42T0F0X3RwaCdwcj9eZG0kUUQnXEItOWJPXSVRIXAoUi8nNCYzNi9oLmRDVillbkojKkgvSi09ZEo0LWFsQkt1IUdgeXlGeEgseU0qXCl5M24rbHpwP2dQTXhhNkBVdmJYJVIlPTR4JzRwNGdzUiQ0InlaJlIlW0w7MjRULHldRiNIZy9OaVEjKWZsZVVbUFheaU1WJj00aidSPW1vQU1ceFUtZnIwJDNPbHAwdDNZMm0lPnA1NjJFZWIhb0RWaUBvVHYzMGAhKT0oXExZbnFxdWMkPSV5a3FlZGNydkRkPVI5JTQoWzBSKnksPSkpPWssWENNUDoyTiYzJCp5KT51cURMY3UlNDoyIlFKd0Fvd15eWCRcJD5DKnl5K08sI1FpJz09PiVlVWUoSDokUkxKUChwOD82OUc=

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

NiMkIitVJFxhUCQhIic=

isprime(%%);

NiNJJXRydWVHSSpwcm90ZWN0ZWRHRiQ=

16! mod 17;

NiMiIzs=

18! mod 19;

NiMiIz0=

22! mod 23;

NiMiI0E=

22!;

NiMiNysrbzJ3eEYyK0M2

% mod 23;

NiMiI0E=

(p-1)! == p-1 mod p;

Error, `=` unexpected

The following command creates a sequence of integers 1...100 and selects the ones that are primeprimes100:=select(isprime,[seq(i,i=1..100)]);

NiM+SSpwcmltZXMxMDBHNiI3OyIiIyIiJCIiJiIiKCIjNiIjOCIjPCIjPiIjQiIjSCIjSiIjUCIjVCIjViIjWiIjYCIjZiIjaCIjbiIjciIjdCIjeiIjJCkiIyopIiMoKg==

Verify for all primes less than 100 that (p-1)! == p-1 mod pThis verifies Wilson's theorem for the primes less than 100for p in primes100 do print(p, (p-1)! mod p); end do;

NiQiIiMiIiI=NiQiIiQiIiM=NiQiIiYiIiU=NiQiIigiIic=NiQiIzYiIzU=NiQiIzgiIzc=NiQiIzwiIzs=NiQiIz4iIz0=NiQiI0IiI0E=NiQiI0giI0c=NiQiI0oiI0k=NiQiI1AiI08=NiQiI1QiI1M=NiQiI1YiI1U=NiQiI1oiI1k=NiQiI2AiI18=NiQiI2YiI2U=NiQiI2giI2c=NiQiI24iI20=NiQiI3IiI3E=NiQiI3QiI3M=NiQiI3oiI3k=NiQiIyQpIiMjKQ==NiQiIyopIiMpKQ==NiQiIygqIiMnKg==

with(numtheory);

Warning, the protected name order has been redefined and unprotected

NiM3UUkmR0lnY2RHNiJJKWJpZ29tZWdhR0YlSSZjZnJhY0dGJUkpY2ZyYWNwb2xHRiVJK2N5Y2xvdG9taWNHRiVJKWRpdmlzb3JzR0YlSSlmYWN0b3JFUUdGJUkqZmFjdG9yc2V0R0YlSSdmZXJtYXRHRiVJKWltYWd1bml0R0YlSSZpbmRleEc2JEkqcHJvdGVjdGVkR0YxSShfc3lzbGliR0YlSS9pbnRlZ3JhbF9iYXNpc0dGJUkpaW52Y2ZyYWNHRiVJJ2ludnBoaUdGJUkqaXNzcXJmcmVlR0YlSSdqYWNvYmlHRiVJKmtyb25lY2tlckdGJUknbGFtYmRhR0YlSSlsZWdlbmRyZUdGJUkpbWNvbWJpbmVHRiVJKW1lcnNlbm5lR0YlSShtaWdjZGV4R0YlSSptaW5rb3dza2lHRiVJKG1pcG9seXNHRiVJJW1sb2dHRiVJJ21vYml1c0dGJUkmbXJvb3RHRiVJJm1zcXJ0R0YlSSluZWFyZXN0cEdGJUkqbnRoY29udmVyR0YlSSludGhkZW5vbUdGJUkpbnRobnVtZXJHRiVJJ250aHBvd0dGJUkmb3JkZXJHRjFJKXBkZXhwYW5kR0YlSSRwaGlHRiVJI3BpR0YlSSpwcHJpbXJvb3RHRiVJKXByaW1yb290R0YlSShxdWFkcmVzR0YlSStyb290c3VuaXR5R0YlSSpzYWZlcHJpbWVHRiVJJnNpZ21hR0YlSSpzcTJmYWN0b3JHRiVJKHN1bTJzcXJHRiVJJHRhdUdGJUkldGh1ZUdGJQ==

phi;

NiNJJHBoaUc2JEkqcHJvdGVjdGVkR0YlL0krbW9kdWxlbmFtZUc2IkkqbnVtdGhlb3J5RzYkRiVJKF9zeXNsaWJHRig=

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

NiQiIiJGIw==NiQiIiMiIiI=NiQiIiQiIiM=NiQiIiUiIiM=NiQiIiYiIiU=NiQiIiciIiM=NiQiIigiIic=NiQiIikiIiU=NiQiIioiIic=NiQiIzUiIiU=NiQiIzYiIzU=NiQiIzciIiU=NiQiIzgiIzc=NiQiIzkiIic=NiQiIzoiIik=NiQiIzsiIik=NiQiIzwiIzs=NiQiIz0iIic=NiQiIz4iIz0=NiQiIz8iIik=NiQiI0AiIzc=NiQiI0EiIzU=

primes100;

NiM3OyIiIyIiJCIiJiIiKCIjNiIjOCIjPCIjPiIjQiIjSCIjSiIjUCIjVCIjViIjWiIjYCIjZiIjaCIjbiIjciIjdCIjeiIjJCkiIyopIiMoKg==

Recall in class we discovered:phi(p) = p-1phi(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;

NiMiJDcm

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<100for 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 2guess #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;

NiM+SSVmbGFnRzYiSSV0cnVlR0kqcHJvdGVjdGVkR0YnNiNRMURBVkV+aXN+cmlnaHQhISE2Ig==

Conjecture: phi(p^k) = p^k-p^(k-1) = p^(k-1)(p-1)primes20:=select(isprime,[seq(i,i=1..20)]);

NiM+SSlwcmltZXMyMEc2IjcqIiIjIiIkIiImIiIoIiM2IiM4IiM8IiM+

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;

NiM3JCIiIkYkNiM3JCIiIyIiIg==NiM3JCIiJCIiIw==NiM3JCIiJSIiIw==NiM3JCIiJiIiJQ==NiM3JCIiJyIiIw==NiM3JCIiKCIiJw==NiM3JCIiKSIiJQ==NiM3JCIiKiIiJw==NiM3JCIjNSIiJQ==NiM3JCIjNiIjNQ==NiM3JCIjNyIiJQ==NiM3JCIjOCIjNw==NiM3JCIjOSIiJw==NiM3JCIjOiIiKQ==NiM3JCIjOyIiKQ==NiM3JCIjPCIjOw==NiM3JCIjPSIiJw==NiM3JCIjPiIjPQ==NiM3JCIjPyIiKQ==

ifactor(294);

NiMqKC1JIUc2IjYjIiIjIiIiLUYlNiMiIiRGKS1GJTYjIiIoRig=