### Site Tools

contest_2011-09-27

# Differences

This shows you the differences between two versions of the page.

 contest_2011-09-27 [2011/09/25 12:48]jtkorb contest_2011-09-27 [2011/09/27 11:00] (current)jtkorb Both sides previous revision Previous revision 2011/09/27 11:00 jtkorb 2011/09/27 06:02 jtkorb 2011/09/25 12:48 jtkorb 2011/09/25 12:42 jtkorb 2011/09/25 12:24 jtkorb 2011/09/25 11:56 jtkorb 2011/09/25 11:39 jtkorb 2011/09/25 10:16 jtkorb 2011/09/25 07:11 jtkorb 2011/09/25 07:10 jtkorb 2011/09/25 06:01 jtkorb 2011/09/25 05:31 jtkorb 2011/09/22 12:50 jtkorb created Next revision Previous revision 2011/09/27 11:00 jtkorb 2011/09/27 06:02 jtkorb 2011/09/25 12:48 jtkorb 2011/09/25 12:42 jtkorb 2011/09/25 12:24 jtkorb 2011/09/25 11:56 jtkorb 2011/09/25 11:39 jtkorb 2011/09/25 10:16 jtkorb 2011/09/25 07:11 jtkorb 2011/09/25 07:10 jtkorb 2011/09/25 06:01 jtkorb 2011/09/25 05:31 jtkorb 2011/09/22 12:50 jtkorb created Line 27: Line 27: * C: Observe that, if ''​k''​ is even, ''​n ^ k mod p''​ is ''​(n ^ (k/2) mod p) ^ 2 mod p''​. ​ Generalize and handle the case for ''​k''​ odd. * C: Observe that, if ''​k''​ is even, ''​n ^ k mod p''​ is ''​(n ^ (k/2) mod p) ^ 2 mod p''​. ​ Generalize and handle the case for ''​k''​ odd. * D: Combine the two preludes. * D: Combine the two preludes. - * E: The GCD algorithm ​given in the text solves this problem directly. + * E: The Extended Euclid Algorithm for GCD (given in the text), given in the text, solves this problem directly. - * F: + * F: Brute force factorization is fine.  You'll want to keep a table of ''​(p,​e)''​ pairs for each prime, ''​p'',​ that divides ''​e''​ times. * G: Theorem: The highest power of ''​p''​ that divides ''​n!''​ is ''​n/​p + n/p^2 + n/p^3 ...''​. ​ So, ''​p^e''​ divides ''​n!''​ if this sum is at least ''​e''​ before ''​n/​p^k''​ reaches 0. * G: Theorem: The highest power of ''​p''​ that divides ''​n!''​ is ''​n/​p + n/p^2 + n/p^3 ...''​. ​ So, ''​p^e''​ divides ''​n!''​ if this sum is at least ''​e''​ before ''​n/​p^k''​ reaches 0. - * H: Use the Diophantine solution method ​in the text. + * H: The text suggests using the Diophantine solution method ​given there. ​ Note that you don't actually need to compute ​the solution, just determine whether or not a solution exists.