Question

...a question related to combinatorcs and number theory...

Answer 1

\(\Large p | \left(\begin{matrix}p \\ k\end{matrix}\right)\)

"p" is prime and k=1,2,3,...,p-1

Answer 2

prove...

Answer 3

Notice \(p \not | ~k\) as \(k\) is an integer less than \(p\)

Answer 4

i've got some idea...
\[\left(\begin{matrix}p \\ k\end{matrix}\right) = p \frac{ (p-1)! }{ k! (p-k)! }\]

so we should only prove that (p-1)! / k! (p-k)! is natural.

Answer 5

rearranging that formula gives \[k!\binom{p}{k} = p(p-1)(p-2)\cdots (p-k+1)\]

Answer 6

@ganeshie8 wait...please wait

Answer 7

okay

Answer 8

i think i got it let me continue...

Answer 9

so,
\[ p|k! \left(\begin{matrix}p \\ k\end{matrix}\right)\]
and as k is less than p so,
k! is not divisble to p so,
\[p | \left(\begin{matrix}p \\ k\end{matrix}\right)\]

Answer 10

Yes!

Answer 11

Thank you so much ;)

Answer 12

\[k!\binom{p}{k} = p(p-1)(p-2)\cdots (p-k+1)\]

that means \(p | k!\) or \(p | \binom{p}{k}\)

we figured out before that \(p \not | ~k\) so \( p \not|~k!\) as well
consequently \(p | \binom{p}{k}\)

Answer 13

yes that results from Euclid's lemma

Answer 14

right, are you doing number theory ?

Answer 15

yes

Answer 16

which textbook are u following

Answer 17

we can use this result to prove fermat's little thm

Answer 18

Fermat's little thm

if \(p\) is a prime, then below holds for all integers \(a\) : \[a^p \equiv a\pmod{p}\]

this can be proved inductively using the earlier result about binomial coefficients
give it a try when free, it is fun :)

Answer 19

you may know Maryam Mirzakhani,iranian person who won the field's prize...she had published a book , Number theory and i use it...\(\Large a^{\{\phi(m)\}} \equiv a\pmod{p}\)

Answer 20

and that theorem comes from it becuase phi(p) = p-1

Answer 21

yes proof of euler's generalization is bit more involved..
fermat's little thm is a subcase of euler's thm and the proof is bit easy compared to that

Answer 22

sry it was 1 and (mod m) ;) i copied it and forgot to correct it ;)

Answer 23

\[a^{\phi(n)} \equiv 1\pmod{n}\]

Answer 24

what topic are you studying now ?

Answer 25

now...i'm just solving some questions about prime numbers then i'll go to study Modular arithmetic ...after that i will study reduced residue system

Answer 26

number theory is too hard ... some questions are really frustrating...

Answer 27

ikr :) tag me in all your future posts, i love these problems

Answer 28

sure :)
thank you for this problem...