Mathematics for Computer Science

15.13. A Magic Trick 497

Problems for Section 15.6

Exam Problems

Problem 15.17.
There is a robot that steps between integer positions in 3-dimensional space. Each
step of the robot increments one coordinate and leaves the other two unchanged.

(a)How many paths can the robot follow going from the origin.0;0;0/to.3;4;5/?

(b)How many paths can the robot follow going from the origin.i;j;k/to.m;n;p/?

Problems for Section 15.7

Practice Problems

Problem 15.18.
Find the coefficients ofx^10 y^5 in.19xC4y/^15

Class Problems

Problem 15.19.
Find the coefficients of

(a)x^5 in.1Cx/^11

(b)x^8 y^9 in.3xC2y/^17

(c)a^6 b^6 in.a^2 Cb^3 /^5

Problem 15.20. (a)Use the Multinomial Theorem 15.7.2 to prove that

.x 1 Cx 2 C


Cxn/pxp 1 Cxp 2 C


Cxpn .modp/ (15.11)

for all primesp. (Do not prove it using Fermat’s “little” Theorem. The point of
this problem is to offer an independent proof of Fermat’s theorem.)

Hint:Explain why

 p

k 1 ;k 2 ;:::;kn

is divisible bypif all theki’s are positive integers
less thanp.

(b)Explain how (15.11) immediately proves Fermat’s Little Theorem 8.6.4:np^1 
1 .modp/whennis not a multiple ofp.