Exact Formulas for Coprime Representations of Even Integers Avoiding a Prime

Título: Fórmulas Exatas para Representações Coprimas de Inteiros Pares Evitando um Primo

Autor: Andrés M. Salazar
Data: 6 de abril de 2026 (Nota: Data futura no contexto do documento fornecido)

---

1. O Problema

O artigo aborda um problema clássico na teoria aditiva dos números: a enumeração exata das representações de um inteiro par $2n$ como a soma de dois inteiros positivos $h$ e $k$ ($h + k = 2n$), sujeitos a condições de coprimalidade específicas.

A função de contagem definida é:
$$g(2n, p) = \#\{(h, k) \in \mathbb{Z}_{>0}^2 : h + k = 2n, h \le k, \gcd(h, 6p) = \gcd(k, 6p) = 1\}$$

O objetivo é contar o número de pares $(h, k)$ tais que:

1. A soma seja $2n$.
2. $h \le k$.
3. Ambos os termos sejam coprimos com $6p$ (ou seja, não divisíveis por 2, 3 ou pelo primo fixo $p \ge 5$).

Embora estimativas assintóticas para funções relacionadas sejam bem conhecidas (via métodos de peneira e inversão de Möbius), obter fórmulas exatas e fechadas que revelem a estrutura interna da função de contagem é uma tarefa delicada que requer controle preciso das restrições de resíduos e condições de ordenação.

2. Metodologia

A abordagem do autor combina teoria dos números elementar, algoritmos de resíduos e análise combinatória para derivar fórmulas fechadas. Os pilares metodológicos são:

A. Operador de Resto Canônico ($\delta_k$)

O autor utiliza o operador $\delta_k(x) = x - k\lfloor x/k \rfloor$, que mapeia inteiros para seus representantes canônicos no intervalo $[0, k-1]$. Propriedades algébricas deste operador (compatibilidade com adição e multiplicação) são fundamentais para manipular as condições de congruência sem recorrer a classes de resíduos abstratas.

B. Soluções Mínimas de Equações de Resto

Um componente técnico central é a resolução explícita de equações da forma $\delta_k(a_0 x) = b_0$.

• O artigo deriva uma fórmula fechada para a solução mínima dessa equação utilizando o Algoritmo de Euclides.
• Ao invés de apenas afirmar a existência da solução, o autor constrói sequências recursivas baseadas no algoritmo de Euclides para expressar a solução diretamente em termos das operações de resto.

C. Redução das Condições de Coprimalidade

A condição $\gcd(h, 6p) = 1$ implica que $h$ não pode ser divisível por 2, 3 ou $p$.

• Inteiros coprimos com 6 são da forma $6x+1$ ou $6x+5$.
• A condição de evitar o primo $p$ é traduzida em equações de congruência lineares: $\delta_p(6x+1) = 0$ e $\delta_p(6x+5) = 0$.
• O autor define parâmetros $a(p)$ e $b(p)$ como as soluções mínimas dessas congruências. Esses parâmetros determinam quais classes de resíduos módulo $p$ devem ser excluídas.

D. Estrutura por Casos e Funções Indicadoras

A função de contagem é dividida com base no resíduo de $n$ módulo 3 ($\delta_3(n)$), pois isso determina a estrutura aditiva dos termos $h$ e $k$:

• Se $\delta_3(n) = 0$: Um termo é da forma $6x+1$ e o outro $6y+5$.
• Se $\delta_3(n) = 1$: Ambos são da forma $6x+1$.
• Se $\delta_3(n) = 2$: Ambos são da forma $6x+5$.

Para cada caso, o problema é reduzido a contar pares de inteiros não negativos com soma fixa, excluindo certos resíduos específicos. O autor utiliza funções de passo (Heaviside) e funções indicadoras para lidar com as condições de fronteira e a restrição de ordenação $h \le k$.

3. Principais Contribuições e Resultados

Teorema Principal (Teorema 4.13)

O resultado central do artigo é a derivação de fórmulas fechadas explícitas para $g(2n, p)$. A fórmula é afim por partes ao longo de progressões aritméticas de $n$, governada pelas classes de resíduos módulo 3 e módulo $p$.

A fórmula final expressa $g(2n, p)$ como:

• Uma combinação linear de produtos escalares entre vetores de contagem de "levantamento" (lifts) e vetores de resíduos admissíveis.
• Depende de parâmetros pré-calculados $a(p)$ e $b(p)$, que são as soluções mínimas de $6x \equiv -1 \pmod p$ e $6x \equiv -5 \pmod p$.

Complexidade Computacional

• Pré-cálculo: Os parâmetros $a(p)$ e $b(p)$ podem ser calculados em $O(\log p)$ usando o Algoritmo de Euclides.
• Avaliação: Após o pré-cálculo, cada avaliação de $g(2n, p)$ requer apenas $O(1)$ operações aritméticas (adição, multiplicação, divisão inteira e funções de resto).
• Comparação: Isso representa uma melhoria drástica em relação à enumeração direta (força bruta), que requer $O(n)$ operações.

Validação Computacional

O autor validou as fórmulas contra um oráculo de força bruta para:

• Todos os inteiros pares $2n \le 10^5$.
• Primos $p \in \{5, 7, 11, 13, 17, 19, 23\}$.
• O resultado foi de acordo perfeito em todos os 350.000 casos de teste.

4. Significado e Implicações

1. Estrutura Afim Oculta: O trabalho revela que a função de contagem, que parece complexa devido às múltiplas restrições de coprimalidade, possui uma estrutura geométrica simples (afim por partes) quando analisada através das lentes corretas (resíduos módulo 3 e $p$).
2. Eficiência Algorítmica: A transformação de um problema de enumeração $O(n)$ para $O(1)$ é significativa para aplicações em teoria dos números computacional, permitindo a análise de valores de $n$ extremamente grandes que seriam intratáveis por métodos diretos.
3. Generalização Potencial: O método desenvolvido não é limitado a evitar apenas um primo $p$. O autor sugere que a abordagem se estende naturalmente para conjuntos de exclusão $\{2, 3, p_1, \dots, p_k\}$, embora isso aumente a complexidade da análise de casos devido ao módulo composto $6p_1\dots p_k$.
4. Ferramentas Concretas: A derivação explícita das soluções mínimas via Algoritmo de Euclides fornece uma ferramenta prática para resolver equações de resto lineares em contextos de contagem combinatória.

Em resumo, o artigo fornece uma solução completa e computacionalmente eficiente para um problema de enumeração clássico, substituindo estimativas assintóticas e somas alternadas complexas por fórmulas fechadas simples e estruturadas.