Bom dia!
Revisando a solução anterior.
1) Se mdc (n,m)= 1 então (n,m) é múltiplo de n.
Pois não existirá um primo que divida n e (n-m), que veremos a seguir que é
condicionante para que não seja múltiplo.
E engloba casos triviais como (n,1) e (n,n-1).
Nota: o item 2 é suficiente para determinar se é múltiplo ou não. O item 1)
é um teste fácil
2) Critério geral.
(n,m) = n! / [((n-m)! m!] = n * (n-1)! / [(n-m)! m!]
Se n divide (n,m) então, (n-1)! / [(n-m)! m!] pertence a |N.
Usando princípio de contagem é fácil observar que:
dado um primo p e usando critério de varredura de diversas contagens, temos
que:
*(i) se p^a || n! então a= [n/p] + [n/p^2] + [n/p^3] +....*
onde o símbolo || significa divide exatamente. Ou seja a=0 se p não divide
n! ou a é o expoente da fatoração de n! relativo ao primo p. E a expressão
entre colchetes simboliza a parte inteira do argumento.
Embora a série seja infinita, a partir de um dado valor do expoente de p, o
mínimo de x inteiro, que atenda a^x > n, todos os valores serão zero.
Seja (n-1)! = p1^a1 * p2^a2*p3^a3*...pj^aj
Seja (n-m)! = p1^b1 * p2^b2*p3^b3*...pk^ak, onde k<= j
Seja m!= p1^c1 * p2^c2*p3^c3*...pu^aû, onde u<= j
Para que (n-1)! / [(n-m)! m!] pertença a |N, basta que ai>= bi + ci para
todo 1<= i <= min(u,k)
Seja a' o expoente da fatoração de (n-1)! referente ao primo p'
Seja b' o expoente da fatoração de (n-p)! referente ao mesmo primo p'
Seja c' o expoente da fatoração de p! referente ao mesmo primo p'
Para que a' < b' + c' , deverá haver, por (i), pelo menos um valor de x
inteiro que satisfaça:
[(n-1)/p'^x] < [(n-m)/p'^x] + [m/p'^x]
Seja s= p'^x
[(n-1)/s] < [(n-m)/s] + [m/s]
(n-1) pode assumir as seguintes classes mods, que não sei como representar
a barra acima do número e também usarei o sinal de igual para representar
congruência, 0, 1, 2, ,3, s-1.
Como o objetivo é descobrir quando a' < b' + c', não serão considerados
os pares(m,n-m) cuja a soma dos restos de n e (n-m) por s dê maior ou
igual a s; pois, claramente teremos a' >= b' + c'.
Se n-1 = k mods e k<>s-1.
Temos:
[(n-1)/s]= (n-(k+1))/s
[m/s] = (m-w)/s e [(n-m)/s] = (n-m-z)/s, onde z+w = k+1; pois, m+(m-n) = n
= k+1 mods e devido a observação, detacada acima, não serão considerados os
casos que w+z = k+ s+1.
Então: [m/s] + [(n-m)/s] = (m-w)/s + (n-m-z)/s = (n-(K+1))/s = [(n-1)/s].
==> a'>= b' + c'
Se n-1 = s-1 mods.
Temos:
[(n-1)/s]= (n -s))/s
[m/s] = (m-w)/s e [(n-m)/s] = (n-m-z)/s, onde z+w = 0; pois, m+(m-n) = n
= 0 mods e devido a observação, detacada acima, não serão considerados os
casos em que w+z >= s. ==> w=z=0 ==> [m/s] + [(n-m)/s] = (m+ n- m)/s = n/s
> a'.
Se não é múltiplo temos que ter pelo menos um p' tal que n = 0 mods e m = n
= 0 mods, onde s= p'^x.
Ora mas se (n-1) = (s-1) mod s ==> n-1 = q.s + (s-1) com q inteiro ==> n-1
= q.p'^x + p'^x -1
n-1= (qp'^(x-1)+p'^(x-1)).p' + p'-1 e pelo fechamento da multiplicação e
adição em Z podemos afirmar que:
n-1 = p-1 mod p.
Então se atender para um p'^x atenderá para p', p'^2...p'^x
Todavia, a observação da nota anterior estava errônea, pois, a condição é
necessária, porém não suficiente.
Notar que se uma parcela ou um grupo de parcelas de a' forem menores que a
soma das correspondentes em b' e c', não implica que outras parcelas não
venham a compensar e ao final a'>= b' + c'.
Os primos passíveis de serem testados são o de f!, onde f=min(m,n-m), ou
seja, 1, 3 , 5...p onde p<f
Então o algoritmo corrigido fica:
bandeira = Verdadeiro
Se mdc(m,n) <> 1
Então
Início Então
i=1
f= min(m,n-m)
Faça enquanto (p(i) <=f ou bandeira = falso)
Início Faça enquanto
Se (m = 0 mod p(i) e (m-n) =0 mod p(i)
Então
Inícío Então
p=p(i)
a= [(n-1)/p] + [(n-1)/p^2] + [(n-1)/p^3] +....
b= [m/p] + [m/p^2] + [m/p^3] +....
c= [(n-m)/p] + [(n-m)/p^2] + [(n-m)/p^3] +....
Se a < b + c
Então
bandeira = falso
Fim Então
i = i +1
Fim faça Enquanto
Fim Então
Se bandeira = verdadeiro
Então
É múltiplo de n. SIM
Senão
Náo é múltiplo de NÃO
Nota p(i) é o primo de ordem i, assim p(1)= 2, p(2) =3 e ...
Vamos aos exemplos:
1) (38,17)
mdc(38,17)= 1 ==> É múltiplo.
2) (38,16)
mdc(38,16) <>1.
i=1
f= 16.
Bandeira = verdadeiro
p(1)=2
16 = 22 = 0 mod2
a = [37/2] + [37/4] + [37/8] + [37/16] + {37/32] = 18 + 9 + 4 + 3 + 1 = 35
b= [16/2] + [16/4] + [16/8] + [16/16] = 8 + 4 + 2 +1 = 15
c = [22/2] + [22/4] + [22/8] + [22/16] = 11 + 5 +2 + 1 = 19
a >= b + c
i=2
p(2) =3
16 <> 0 mod3
i=3
p(3)= 5
16 <> 0 mod5
e assim por diante, falharia para todos os demais primos, pois 16 é
potência de 2.
Então é múltiplo de 38. SIM
*Nota: pelo algoritmo anterior daria um resultado errado que não seria.*
Se calcular para cada primo os valores de a, b e c é o que é garantido.
Tentei reduzir o trabalho olhando apenas para os potenciais primos cujos
expoentes b e c somados possam exceder a.
Espero que esteja correto o critério de exclusão usado, ou seja, m <> 0
modp ou m-n <> 0 mod p.
Infelizmente só há como resolver se a fatoração de n não tiver um fator p
superior a 2^74.207.281-1.
Agora, creio que esteja correto.
Agradeço se alguém validar.
Saudações,
PJMS
--
Esta mensagem foi verificada pelo sistema de antiv�rus e
acredita-se estar livre de perigo.
