Could anyone please help me on the following problem:

  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!

Thanks in advance for your help.

  • $\begingroup$ $\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\}$? $\endgroup$ – user17762 Jan 2 '13 at 17:42
  • $\begingroup$ $\binom 9 3 = 84$ $\endgroup$ – Mark Bennet Jan 2 '13 at 17:46

This is not a full analysis ...

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.

  • $\begingroup$ What about when x and r are relatively prime? Can we say anything then? $\endgroup$ – AndrewG Jan 2 '13 at 18:16
  • $\begingroup$ @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. $\endgroup$ – 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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.