# This question involves Pascal's Triangle & Binomial Theorem. Full Question

1. Factorize the expression $P(n)=n^x-n$ for $x=2,3,4,5$ Determine if the expression is always divisible by the corresponding $x$. If divisible use mathematical induction to prove your results by showing whether $P(k+1)-P(k)$ is always divisible by $x$. Using appropriate technology, explore more cases, summarize your results and make a conjecture for when $n^x-n$is divisible by$x$. (Not divisible by$\ 4$. Thus I concluded that $x$ is prime.)

2.Explain how to obtain the entries in Pascal's Triangle, and using appropriate technology, generate the first 15 rows. State the relationship between the expression $P(k+1)-P(k)$ and Pascal's Triangle. Reconsider your conjecture and revise if necessary. (Here, my previous conjecture appeared incorrect, because $x$=prime numbers did not work out for 11 and 13 from the Triangle).

And on this part I am experiencing a bit of trouble as I am saying that $x=2,3,5,7$. But this does not work for all $r$...I decided that $k$ is a multiple of $x$ when $x=2, 3, 5, 7, 9$. However, $r$ is different for each of the $x$ ...

Write an expression for the xth row of Pascal's Triangle. You will have noticed that ($x$ choose $r)=k$, $k$ is $N$. Determine when $k$ is a multiple of $x$.

1. make conclusions regarding the last result in part 2 and the form of proof by induction used i nthis assignment. Refine your conjecture if necessary, and prove it.

I believe that I am not getting this correctly, help is greatly appreciated!

• $\dbinom{x}1 = x$ a multiple of $x$. Do you want it to be $>x$ and still a multiple of $x$ i.e. do you want $r \in \{2,3,\ldots,x-1\}$? – user17762 Jan 2 '13 at 17:42
• $\binom 9 3 = 84$ – Mark Bennet Jan 2 '13 at 17:46

If $x$ is prime and $0<r<x$ then $\binom x r$ is divisible by $x$.
If $p$ is a prime factor of $x$ then $\binom x p$ is not divisible by $x$ - there is a factor of $p$ which cancels - work it out.
• @AndrewGibson Given the edit to the question I think I'll go with my own instinct to leave some things to be investigated and explored. It is very easy to generate the first n binomial coefficients using a spreadsheet for modest values of n. In the case you ask about you might want to take a prime factor $p$ of $x$ and see whether you can work out something about the power of $p$ which divides the binomial coefficient. – Mark Bennet Jan 2 '13 at 18:36
The first question also leads to interesting things. As you conjectured, if $x$ is prime, then $n^x-n$ is divisible by $x$. This is one version of Fermat's (little) Theorem.
However, from knowing that $n^x-n$ is always divisible by $x$, we cannot conclude that $x$ is prime. Of course $n^1-n$ is always divisible by $1$. That is uninteresting. But, for example, $n^{561}-n$ is always divisible by $561$, and $561=3\cdot 11\cdot 17$. For more information, you might want to look at the Wikipedia article on Carmichael numbers.