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.