Olimpíadas ⇒ Função Parte Inteira Tópico resolvido

[goncalves3718]

Prove que, se [tex3]p [/tex3] é um número primo, então a diferença [tex3]\begin{pmatrix}
n \\
p
\end{pmatrix} - \left\lfloor \dfrac{n}{p} \right\rfloor[/tex3] é divisível por [tex3]p[/tex3]

[AnthonyC]

O que seria a notação de parênteses? Ou são só parênteses normais?

[Ittalo25MOD]

O que seria a notação de parênteses? Ou são só parênteses normais?

é o símbolo de Legendre

mas essa questão parece não fazer sentido

se p = 3 e n = 6:

[tex3]\left(\frac{6}{3}\right) - \left\lfloor \dfrac{6}{3} \right\rfloor = 0 - 2 = -2[/tex3]

e 3 não divide -2

[goncalves3718]

Não sei se é Legendre, será que não é binomial?

[Ittalo25MOD]

[tex3]\begin{pmatrix}
n \\
p
\end{pmatrix} - \left\lfloor \dfrac{n}{p} \right\rfloor = \frac{n! }{p! \cdot (n-p)!} - \left(\frac{n - (n \mod(p))}{p}\right) = [/tex3]

[tex3]\frac{n\cdot (n-1) \cdot (n-2) \cdot (n-3) \cdot .... (n-p+1) }{p!} - \frac{n-(n \mod(p))}{p} = [/tex3]

[tex3]\frac{n\cdot (n-1) \cdot (n-2) \cdot (n-3) \cdot .... (n-(p-1)) }{p!} - \frac{n-(n \mod(p))}{p} = [/tex3]

repare que dá para colocar em evidência:

[tex3]\frac{n-(n \mod(p))}{p} \cdot (\frac{\frac{n\cdot (n-1) \cdot (n-2) \cdot (n-3) \cdot .... (n-(p-1))}{n-(n \mod(p))} -(p-1)!}{(p-1)!}) = [/tex3]

Agora [tex3]mdc((p-1)!, p) = 1 [/tex3], então se o numerador for múltiplo de p está feito.

[tex3]-(p-1)! \equiv 1 \space \space mod(p)[/tex3] pelo teorema de Wilson

Então se [tex3]\frac{n\cdot (n-1) \cdot (n-2) \cdot (n-3) \cdot .... (n-(p-1))}{n-(n \mod(p))} \equiv -1 \mod(p) [/tex3] esta provado

e isso é verdade, repara o conjunto [tex3]\{0,1,2,3,4,...,p-1\} [/tex3]
Vamos pegar [tex3]n \equiv k \mod(p) [/tex3] onde [tex3]k \in \{0,1,2,3,4,...,p-1\} [/tex3], digamos: [tex3]k = 2 [/tex3]
Se fizermos:
[tex3]\{2-0,2-1,2-2,2-3,2-4,...,2-(p-1)\} \equiv \{2,1,0,-1,-2,...,3-p\} \equiv \{2,1,0,p-1,p-2,...,3\}[/tex3]

Ou seja, todos os restos vão continuar módulo p, apenas os termos do conjunto são "deslocados".

Repare bem que a classe de congruência do 0 não vai existir no produto pois ele já está "cancelado" no denominador [tex3]n-(n \mod(p)) [/tex3]

Ou seja:

[tex3]\frac{n\cdot (n-1) \cdot (n-2) \cdot (n-3) \cdot .... (n-(p-1))}{n-(n \mod(p))} \equiv \frac{0\cdot 1 \cdot 2 \cdot 3 \cdot ...(p-1)}{0} \equiv (p-1)! \equiv -1\mod(p) [/tex3]

e então está provado

[goncalves3718]

[quote=Ittalo25 post_id=250108 time=1607831091 user_id=10913]
[tex3]\begin{pmatrix}
n \\
p
\end{pmatrix} - \left\lfloor \dfrac{n}{p} \right\rfloor = \frac{n! }{p! \cdot (n-p)!} - \left(\frac{n - (n \mod(p))}{p}\right) = [/tex3]

Porque ficou [tex3]\left(\frac{n - (n \mod(p))}{p}\right)[/tex3] ?
Propriedade, definição? De onde saiu o [tex3]mod (p)[/tex3]

[Ittalo25MOD]

[tex3]\begin{pmatrix}
n \\
p
\end{pmatrix} - \left\lfloor \dfrac{n}{p} \right\rfloor = \frac{n! }{p! \cdot (n-p)!} - \left(\frac{n - (n \mod(p))}{p}\right) = [/tex3]

Porque ficou [tex3]\left(\frac{n - (n \mod(p))}{p}\right)[/tex3] ?
Propriedade, definição? De onde saiu o [tex3]mod (p)[/tex3]

O que realmente significa a função parte inteira?
Um número inteiro.
Para uma divisão resultar em um número inteiro, é preciso retirar o resto.
Se temos [tex3]\frac{n}{p}[/tex3] isso pode ser um número inteiro ou não.
Mas se retirarmos o resto de n na divisão por p: [tex3]\frac{n - (n\mod(p))}{p}[/tex3] temos certeza de que isso é um número inteiro.

[goncalves3718]

Entendi
Obrigado!