[QUOTE=R. Gerbicz;594026]...furthermore: k*binomial(p,k)=p*binomial(p1,k1) is also true...[/QUOTE]
And we can do this combinatorially too: both are the way of choosing k elements from a set of p elements, where we label one of those k elements as "special". We get k*binomial(p,k) by choosing the set of k elements and then picking the special element, and p*binomial(p1,k1) by first picking the special element and then choosing the other k1 elements from the remaining p1 elements of our set. More famously, binomial(p1,k1)+binomial(p1,k)=binomial(p,k) is easiest to see combinatorially: we partition the binomial(p,k) choices of k elements from the numbers {1,...,p} into two, depending on whether they contain 1 or not. binomial(p1,k1) is the number of choices containing 1, and binomial(p1,k) is the number of choices not containing 1. 
[QUOTE=R. Gerbicz;594026]Modified your idea, close to a pure combinatorial proof:
The k=0 case is trivial, so assume that 0<k<p, it is known: binomial(p1,k1)+binomial(p1,k)=binomial(p,k) [for here you don't need that p is prime] <snip>[/QUOTE]Of course! And for 0 < k < p, [tex]\frac{p!}{k!(pk)!}[/tex] clearly is divisible by p because the denominator is composed of factors less than p. The result can be extended slightly. Since p divides binomial(p,k) for 0 < k < p when p is prime, we have the "freshman's dream" polynomial identity in [b]F[/b][sub]p[/sub][x,y] [tex](x\;+\;y)^{p}\;=\;x^{p}\;+\;y^{p}[/tex] Repeatedly raising to the p[sup]th[/sup] power, we see that in [b]F[/b][sub]p[/sub][x,y] for any positive integer n, [tex](x\;+\;y)^{p^{n}}\;=\;x^{p^{n}}\;+\;y^{p^{n}}[/tex] which shows that binomial(p[sup]n[/sup],k) is divisible by p for 0 < k < p[sup]n[/sup]. Then the above argument shows that for p prime and any positive integer n, [TEX]{p^{n}1\choose k}\equiv 1^k \;\pmod p[/TEX] 
more of this
I am excited about this.
*smile* 
Thanks a lot for all the replies, it will take me while to get through all that.
By "reduced" I meant, there would be no smaller integer congruent to them mod p. I forgot about that smaller could also mean "negative". 
And another one:
An exercise deals with an integer a having order 3 mod p. And it is to be shown that a+1 has order 6 mod p. As a hint they give: [TEX]a^2 + a + 1 \equiv 0 \pmod {p}[/TEX]. If I accept that, I can prove that a+1 will have order 6. But how do I get from [TEX]a^3 \equiv 1[/TEX] to [TEX]a^2 + a + 1 \equiv 0[/TEX]? My problem is that I don't know what I can transform the a^3 into. [TEX]a^4 \equiv a[/TEX], but does that help? I also tried writing it as [TEX]a^31 = r*p[/TEX] which also didn't get me anywhere. A small nudge in the right direction would be appreciated. 
Hint: how does a^31 factorize?

[QUOTE=bur;599143]And another one:
An exercise deals with an integer a having order 3 mod p. And it is to be shown that a+1 has order 6 mod p. As a hint they give: [TEX]a^2 + a + 1 \equiv 0 \pmod {p}[/TEX]. If I accept that, I can prove that a+1 will have order 6. But how do I get from [TEX]a^3 \equiv 1[/TEX] to [TEX]a^2 + a + 1 \equiv 0[/TEX]?[/QUOTE] That is a wrong way and it is not even true: let a=1 (and p>3) then a^3=1 mod p but a^2+a+1 != 0 mod p. The idea is only that, if you need just that order of (a+1) divides 6, then: (a+1)^6==1 mod p, but that is true, because a^2+a+1  (a+1)^61 for every a integer, here a^2+a+1 is divisible by p, so (a+1)^61 is also divisible by p, hence (a+1)^6==1 mod p. You need more, the order is 6, so it can't be 1,2 or 3 [we know that every "good exponent" is divisible by the order, so the order should divide 6]. If the order is odd, then: (a+1)^3==1 mod p in this case (a+1)^31(a^2+a+1)*(a+2)=2 but the left side is divisible by p, because (a+1)^31 and (a^2+a+1) is divisible by p. This would mean that 2 is divisible by p, but p=2 can't be. Now you need to handle only the order=2 case, so you can't have (a+1)^2==1 mod p. I left it for you. 
[QUOTE=bur;599143]And another one:
An exercise deals with an integer a having order 3 mod p. <snip>[/QUOTE]This means that a^3 == 1 (mod p) but a^1 =/= 1 (mod p); that is, a^3  1 == 0 (mod p) but a  1 =/= 0 (mod p). Supplementary exercise: If p is prime, n divides p1, and a^n == 1 (mod p), then the order of a (mod p) is exactly n if and only if a^d =/= 1 for any divisor d of n with n/d > 1. Refinement: If and only if a^(n/q) =/= 1 (mod p) for every prime factor q of n 
All times are UTC. The time now is 06:15. 
Powered by vBulletin® Version 3.8.11
Copyright ©2000  2022, Jelsoft Enterprises Ltd.