Congruências, divisibilidade e funções aritméticas
Introduzido| English | Significado |
|---|---|
| congruence/ˈkɒŋɡruːəns/ | congruência |
| Chinese remainder theorem/tʃaɪˈniːz rɪˈmeɪndə ˈθɪərəm/ | teorema chinês do resto |
| totient/ˈtəʊʃənt/ | função totiente |
Quando ciclos se alinham
- Um engrenagem se repete a cada $4$ minutos, outra a cada $7$. Estar na posição $2$ no primeiro ciclo e $3$ no segundo significa encontrar um tempo $x$ com $x\equiv2\pmod4$ e $x\equiv3\pmod7$.
- Congruências descrevem posições repetidas. O teorema chinês do resto as combina; testes de mdc, inversos modulares e expoentes primos indicam quais passos algébricos são válidos.
Congruência significa divisibilidade
- Uma congruência é uma afirmação de que dois inteiros têm o mesmo resto módulo um inteiro positivo especificado. Aqui todas as variáveis são inteiros e os módulos satisfazem $n\geq2$; $a\equiv b\pmod n$ significa exatamente que $n$ divide $a-b$.
- Para $ax\equiv b\pmod n$, coloque $d=\gcd(a,n)$. Qualquer solução dá $ax-b=kn$ para algum inteiro $k$. Como $d$ divide tanto $a$ quanto $n$, deve dividir $b$; se $d\nmid b$, não há solução.
Por que o mdc também conta soluções
- A condição $d\mid b$ é suficiente também. Bézout fornece inteiros $u,v$ com $ua+vn=d$; multiplicando por $b/d$ mostra que $x=u(b/d)$ é uma solução da congruência original.
- Se $d<n$, divida o coeficiente, o alvo e o módulo por $d$. O coeficiente reduzido é invertível módulo $n/d$, dando uma classe $x\equiv x_0\pmod{n/d}$. Seus levantamentos são $x_0+k(n/d)$ para $k=0,\ldots,d-1$: exatamente $d$ resíduos distintos módulo $n$. O caso $d=n$ é tratado separadamente abaixo.
How many solutions modulo 20 does $8x \equiv 12 \pmod{20}$ have?
Dificuldade 2/5 · Moedas 140 + pequeno bônus na primeira conclusão hoje
The gcd is 4 and divides 12, so there are four residues modulo 20. Reducing gives 2x ≡ 3 (mod 5), hence x ≡ 4 (mod 5). The four lifts are 4, 9, 14 and 19 modulo 20.
Reduzir, resolver e levantar
- Para $6x\equiv9\pmod{15}$, o mdc é $3$ e divide $9$. Divida os três números por $3$ para obter $2x\equiv3\pmod5$. Como $2^{-1}\equiv3\pmod5$, a solução reduzida é $x\equiv4\pmod5$.
- Levante de volta ao módulo original adicionando $5$: os resíduos são $4,9,14$ módulo $15$. Substituindo-os resulta em $24,54,84$, cada um congruente a $9$ módulo $15$; a contagem de soluções é $3$, não $1$.
Which congruence is equivalent to $6x\equiv9\pmod{15}$ after dividing by the gcd?
Dificuldade 1/5 · Moedas 100 + pequeno bônus na primeira conclusão hoje
The gcd is 3, so the coefficient 6, target 9 and modulus 15 all divide by 3. The reduced class modulo 5 lifts to three classes modulo 15.
Cancelamento e coeficiente zero
- Dividir apenas o coeficiente e o alvo altera o problema: substituir $6x\equiv9\pmod{15}$ por $2x\equiv3\pmod{15}$ daria apenas $x\equiv9\pmod{15}$ e perderia as outras duas soluções. O módulo deve encolher durante a etapa de divisão.
- Se $n\mid a$, então $ax\equiv0\pmod n$ para todo $x$. Há todos $n$ resíduos como soluções quando $n\mid b$, e nenhum caso contrário. Assim, $0x\equiv0\pmod6$ tem seis soluções, enquanto $0x\equiv1\pmod6$ não tem nenhuma; nenhum inverso módulo $1$ é necessário.
Quantas soluções existem?
Use mdc(a, n) para contar soluções de ax ≡ b (mod n).
How many residue classes modulo $6$ satisfy $0x\equiv0\pmod6$?
Dificuldade 2/5 · Moedas 140 + pequeno bônus na primeira conclusão hoje
Every residue 0, 1, 2, 3, 4 and 5 works. The gcd is gcd(0, 6) = 6, which divides the target 0.
Solve $18x\equiv30\pmod{42}$ and list every residue solution modulo $42$. Explain why your list is complete.
O mdc é $\gcd(18,42)=6$, que divide 30. Divida o coeficiente, o alvo e o módulo por 6 para obter $3x\equiv5\pmod7$. Como o inverso de 3 módulo 7 é 5, isso resulta em $x\equiv25\equiv4\pmod7$. As seis elevações módulo 42 são $4,11,18,25,32,39$. Cada elevação satisfaz a congruência original. Existem exatamente seis elevações distintas porque o período reduzido é 7 e o módulo original é 42.
Encontrar inversos pela Euclides estendida
- O inverso de $a$ módulo $n$ existe exatamente quando $\gcd(a,n)=1$. Para $7$ e $26$, Euclides dá $26=3\cdot7+5$, depois $7=5+2$, depois $5=2\cdot2+1$; o último resto não nulo é $1$.
- Como $2=7-5$, a retrosubstituição fornece $1=3\cdot5-2\cdot7$. Em seguida, use $5=26-3\cdot7$ para obter $1=3\cdot26-11\cdot7$. Logo, $7^{-1}\equiv-11\equiv15\pmod{26}$; verifique que $7\cdot15=105\equiv1\pmod{26}$.
Find the inverse of 5 modulo 13 (between 1 and 12).
Dificuldade 2/5 · Moedas 140 + pequeno bônus na primeira conclusão hoje
We need 5x ≡ 1 (mod 13). 5 · 8 = 40 = 3 · 13 + 1, so the inverse is 8. (The Euclidean algorithm finds it systematically.)
Combinar ciclos coprimos
- O teorema chinês do resto é o resultado de que congruências com módulos mutuamente primos têm exatamente uma classe de resíduo comum módulo o produto de seus módulos. Para dois módulos, substitua $x=r+mk$ em $x\equiv s\pmod n$; o coeficiente $m$ é invertível módulo $n$.
- No exemplo da engrenagem, escreva $x=2+4k$. A segunda condição torna-se $4k\equiv1\pmod7$, logo $k\equiv2\pmod7$ e $x\equiv10\pmod{28}$. O menor tempo positivo é $10$; o conjunto solução completo é $10+28t$ para inteiro $t$.
Find the least positive $x$ with $x \equiv 1 \pmod 3$ e $x \equiv 4 \pmod 5$.
Dificuldade 2/5 · Moedas 140 + pequeno bônus na primeira conclusão hoje
List numbers ≡ 4 (mod 5): 4, 9, 14, … The first, 4, already leaves remainder 1 when divided by 3, so x = 4. By the CRT the solution is unique mod 15.
Módulos não primos entre si: teste de compatibilidade
- Para $x\equiv r\pmod m$ e $x\equiv s\pmod n$, uma solução existe exatamente quando $\gcd(m,n)$ divide $s-r$. Substituindo $x=r+mk$ obtém-se $mk\equiv s-r\pmod n$, portanto o teste linear do mdc aplica-se. Um sistema compatível fornece uma classe módulo $\operatorname{lcm}(m,n)$.
- Para $x\equiv1\pmod4$ e $x\equiv3\pmod6$, substitua $x=1+4k$ para obter $4k\equiv2\pmod6$. Reduza a $2k\equiv1\pmod3$, resultando em $k\equiv2\pmod3$ e $x\equiv9\pmod{12}$. Porém, os resíduos $0$ módulo $4$ e $3$ módulo $6$ são incompatíveis: um exige número par, o outro ímpar.
Find the least positive integer $x$ with $x\equiv3\pmod8$ e $x\equiv7\pmod{12}$.
Dificuldade 2/5 · Moedas 140 + pequeno bônus na primeira conclusão hoje
The gcd is 4, which divides the difference 7 − 3. Put x = 3 + 8k. Then 8k ≡ 4 (mod 12), so 2k ≡ 1 (mod 3) and k ≡ 2 (mod 3). Thus x ≡ 19 (mod 24), with least positive member 19.
O período e a menor solução positiva
- Duas soluções do mesmo sistema diferem por um múltiplo comum dos módulos, ou seja, pelo seu mmc. Inversamente, somar o mmc a uma solução preserva ambas as condições. Isso prova o período alegado e a unicidade da classe de resíduo.
- Um representante mínimo não negativo pode não ser positivo. Para $x\equiv0\pmod4$ e $x\equiv0\pmod6$, a classe é $0$ módulo $12$; seu menor membro positivo é $12$, não $0$. Leia o intervalo solicitado antes de escolher o representante final.
Solve $x\equiv2\pmod6$, $x\equiv8\pmod{10}$. Give the full residue class and least positive solution. Then explain what changes if the first residue is changed to $1$.
O mdc é 2 e divide $8-2=6$, logo o primeiro sistema é compatível. Escreva $x=2+6k$; depois $6k\equiv6\pmod{10}$, logo $3k\equiv3\pmod5$ e $k\equiv1\pmod5$. Portanto $x\equiv8\pmod{30}$, onde $30=\operatorname{lcm}(6,10)$. Sua menor solução positiva é 8. Se o primeiro resíduo tornar-se 1, a diferença exigida é $8-1=7$, que não é divisível pelo mdc 2. Alternativamente, as duas congruências exigem paridade ímpar e par, logo não há solução.
Função totiente: conte os resíduos invertíveis
- O totiente é o número de classes de resíduo coprimas ao módulo. Para $n\geq2$, escreva essa contagem como $\varphi(n)$. Se os divisores primos distintos forem $p$, então $\varphi(n)=n\prod_{p\mid n}(1-1/p)$: cada primo entra no produto apenas uma vez, independentemente de seu expoente em $n$.
- Como $36=2^2\cdot3^2$, obtemos $\varphi(36)=36\cdot\dfrac12\cdot\dfrac23=12$. Para uma potência prima, $\varphi(p^k)=p^k-p^{k-1}$, pois exatamente os múltiplos de $p$ não são coprimos a $p^k$.
$\varphi(36)$ equals
Dificuldade 1/5 · Moedas 100 + pequeno bônus na primeira conclusão hoje
$36 \cdot \tfrac12 \cdot \tfrac23$.
Euler e Fermat exigem as condições corretas
- Se $\gcd(a,n)=1$, o teorema de Euler fornece $a^{\varphi(n)}\equiv1\pmod n$. A multiplicação por $a$ permuta os resíduos invertíveis; comparar seus produtos e cancelar o produto invertível demonstra o resultado.
- Para um primo $p$ e $p\nmid a$, isso se torna o teorema de Fermat $a^{p-1}\equiv1\pmod p$. A forma $a^p\equiv a\pmod p$ vale para todo inteiro $a$, incluindo múltiplos de $p$. Por exemplo, $\varphi(10)=4$ e $3^{100}=(3^4)^{25}\equiv1\pmod{10}$.
What is $7^{222} \bmod 10$?
Dificuldade 2/5 · Moedas 140 + pequeno bônus na primeira conclusão hoje
φ(10) = 4, 222 ≡ 2 mod 4, 7² = 49.
For integers $a$ e $n\geq2$, $a^{\varphi(n)}\equiv1\pmod n$ holds whenever $\gcd(a,n)=1$.
Dificuldade 1/5 · Moedas 100 + pequeno bônus na primeira conclusão hoje
True. Euler’s theorem requires coprimality. For example, 2 and 8 are not coprime, and $2^4\equiv0\pmod8$ rather than 1.
Reduza expoentes apenas para unidades
- Para um expoente não negativo $e$ e $\gcd(a,n)=1$, reduzir $e$ módulo $\varphi(n)$ preserva $a^e$ módulo $n$. Sem coprimalidade, isso pode falhar: reduzir $10$ módulo $\varphi(8)=4$ substituiria erroneamente $2^{10}$ por $2^2\equiv4\pmod8$.
- Elevação repetida funciona sem suposição de coprimalidade. Aqui $2^2\equiv4$, $2^4\equiv0$ e $2^8\equiv0\pmod8$. Como $10=8+2$, o resíduo real é $2^{10}\equiv0\pmod8$. Reduza os produtos intermediários, em vez de invocar Euler para um não-unitário.
Since $\varphi(8)=4$, reducing the exponent proves $2^{10}\equiv2^2\pmod8$.
Dificuldade 1/5 · Moedas 100 + pequeno bônus na primeira conclusão hoje
Euler exponent reduction requires an invertible base. The actual residues are 2¹⁰ ≡ 0 (mod 8) and 2² ≡ 4 (mod 8), so they differ.
Compute $5^{123}\bmod12$ e $6^{18}\bmod9$. Explain why the same exponent-reduction shortcut does not apply to both.
For the first power, $\gcd(5,12)=1$ e $\varphi(12)=4$. Since $123\equiv3\pmod4$, Euler gives $5^{123}\equiv5^3\equiv5\pmod{12}$. For the second, $\gcd(6,9)=3$, so Euler reduction is not justified. Instead $6^2=36\equiv0\pmod9$, hence $6^{18}=(6^2)^9\equiv0\pmod9$. Reducing 18 modulo $\varphi(9)=6$ would wrongly replace the power by $6^0=1$.
Divisibilidade torna-se desigualdades de expoentes primos
- Para um inteiro positivo $M$, seja $v_p(M)$ o expoente do primo $p$ em sua fatoração. Um inteiro positivo $D$ divide $M$ exatamente quando $v_p(D)\leq v_p(M)$ para todo primo $p$.
- Se $N^k$ deve ser divisível por $D$, com inteiro positivo $k$, exija $k\,v_p(N)\geq v_p(D)$. Escolha $v_p(N)=\lceil v_p(D)/k\rceil$ para primos que dividem $D$, e zero para outros primos. Todo $N$ admissível é múltiplo dessa escolha, sendo ela a menor positiva.
O menor inteiro cujo quadrado contém 360
- Fator $360=2^3\cdot3^2\cdot5$. Para que $N^2$ seja divisível por $360$, os expoentes de $2,3,5$ em $N$ devem ser pelo menos $2,1,1$. Assim, a menor escolha é $N=2^2\cdot3\cdot5=60$.
- Verifique $60^2=3600=10\cdot360$. O expoente de $2$ em $N$ arredonda para cima de $3/2$ para $2$; não pode arredondar para baixo. Primos extras ou expoentes maiores aumentam $N$ e não melhoram o mínimo.
What is the least positive integer $N$ such that $108$ divides $N^2$?
Dificuldade 2/5 · Moedas 140 + pequeno bônus na primeira conclusão hoje
Since 108 = 2²·3³, N needs at least one factor of 2 and two factors of 3. The least N is 2·3² = 18, and 18² = 324 = 3·108.
Preencha um produto para formar uma potência perfeita
- Para tornar $24N$ um cubo perfeito, comece com $24=2^3\cdot3$. Todo expoente primo no produto deve ser múltiplo de $3$. O expoente de $2$ já está adequado, mas o expoente de $3$ precisa de duas cópias a mais, logo o menor multiplicador é $N=3^2=9$.
- Verifique $24\cdot9=216=6^3$. Isso usa congruências de expoentes: $v_p(24)+v_p(N)\equiv0\pmod3$. O problema anterior de divisibilidade por quadrado usou desigualdades em vez disso. Escolha a condição que corresponda à formulação da questão.
O passo proposto funciona?
Verifique as premissas da redução de expoentes, períodos do TCC e expoentes mínimos.
What is the least positive integer $N$ such that $18N$ is a perfect cube?
Dificuldade 1/5 · Moedas 100 + pequeno bônus na primeira conclusão hoje
Factor 18 = 2·3². To make all product exponents multiples of 3, add two factors of 2 and one factor of 3. Thus N = 2²·3 = 12 and 18·12 = 216 = 6³.
Find the least positive integer $N$ such that $540$ divides $N^2$ e $40N$ is a perfect cube. Prove minimality using prime exponents.
Escreva $540=2^2\cdot3^3\cdot5$ e $40=2^3\cdot5$. Sejam os expoentes de 2, 3 e 5 em N iguais a a, b e c. A divisibilidade de N² exige $a\geq1$, $b\geq2$ e $c\geq1$. A condição de cubo exige que $a+3$, b e $c+1$ sejam múltiplos de 3. Portanto, os menores expoentes possíveis são $a=3$, $b=3$ e $c=2$, resultando em $N=2^3\cdot3^3\cdot5^2=5400$. Nenhum primo extra é necessário. Todo N admissível tem pelo menos esses expoentes, logo nenhum pode ser menor. Verifique que $5400^2/540=54000$ é um inteiro e $40\cdot5400=216000=60^3$.
Verifique existência, período e minimalidade
- Para uma congruência linear, teste o mdc, reduza todos os três números e eleve cada resíduo. Para um sistema, teste a compatibilidade e use o mmc como seu período; a menor resposta positiva pode diferir do menor representante não negativo.
- Use Euler apenas para resíduos inversíveis. Para problemas de divisibilidade de inteiros mínimos, fator primeiro e traduza cada requisito em uma desigualdade ou congruência para cada expoente primo.