4

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.

Marc van Leeuwen
  • 115,048
Knowledge Seeker
  • 49

2 Answers2

1

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.

Mark Bennet
  • 100,194
  • What about when x and r are relatively prime? Can we say anything then? – AndrewG Jan 02 '13 at 18:16
  • @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 02 '13 at 18:36
1

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.

André Nicolas
  • 507,029