DEFINIÇÃO
Um número inteiro p é dito um número primo quando possui exatamente quatro divisores inteiros: ±p, ±1. Por outro lado, um inteiro é dito composto quando não é primo.
Exemplo:
2, 3, 5, 7, 11 são números primos, mas 6, 15, 21, 42 são números compostos.
Observação
O único número primo par é o 2.
Teorema: Se p é primo tal que p | ab, então p | a ou p | b (a | b significa que a divide b).
Teorema Fundamental da Aritmética: Todo inteiro maior do que 1 pode ser expresso de maneira única (a menos da ordem) como produto de fatores primos.
Exemplo:
5544 = 23 ⋅ 32 ⋅ 7 ⋅ 11
Assim, todo número inteiro n pode ser representado como 12 k np p p 12 k αα α = ⋅ ⋅⋅ (decomposição canônica), em que p1 , p2 , …, pk são números primos e α1 , α2 , …, αk são inteiros positivos.
Teorema (Euclides): Existem in nitos primos.
Demonstração: Suponha que existe um número nito de primos, digamos p1 , p2 , …, pn . Considere N = p1 p2
…pn + 1. É fácil ver que N não é divisível por nenhum dos pi ’s da lista de primos e que N é maior do que qualquer um dos pi ’s. Mas, pelo Teorema Fundamental da Aritmética, N é primo ou produto de primos e isto implica na existência
de um primo que não está na nossa lista, contradição. Assim, existem in nitos primos.
Teorema: Se n não é primo, então n possui, necessariamente, um fator primo menor ou igual a n.
Demonstração: Se n não é primo, podemos escrever n = ab, a, > 1. Supondo que todos os fatores primos de n são maiores que n, teremos a n > e b n > , o que nos dá n = ab > n, absurdo.
Esse último teorema motiva a construção de um algoritmo para determinar, dado um número N, os primos menores ou iguais a N, chamado Crivo de Eratóstenes.
O Crivo consiste no seguinte:
Listam-se todos os números primos menores ou iguais a N. Após, retiram-se da lista de números de 2 a N todos os múltiplos compostos dos números primos enumerados na primeira lista. Os números que restarem são primos.
Exemplo:
Obter todos os números primos menores do que 120.
2 3 4 5 6 7 8 9 10
11 12 13 14 15 16 17 18 19 20
21 22 23 24 25 26 27 28 29 30
31 32 33 34 35 36 37 38 39 40
41 42 43 44 45 46 47 48 49 50
51 52 53 54 55 56 57 58 59 60
61 62 63 64 65 66 67 68 69 70
71 72 73 74 75 76 77 78 79 80
81 82 83 84 85 86 87 88 89 90
91 92 93 94 95 96 97 98 99 100
101 102 103 104 105 106 107 108 109 110
111 112 113 114 115 116 117 118 119 120
Desta forma, os números primos menores do que 120 são: 2, 3, 5, 6, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113.
NÚMEROS PRIMOS ENTRE SI
Dois números são ditos primos entre sim quando o seu único divisor natural comum for a unidade (1).
Exemplo:
3 e 5 são primos entre si.
ProBizu
1 – Um número primo qualquer será primo relativo com qualquer outro número.
2 – Dois números consecutivos sempre serão primos entre si.
Propriedades:
• Dois números naturais sucessivos são sempre primos entre si.
• As potências de dois ou mais números primos entre si também são números primos entre si.
• Se dois números a e b forem primos entre si, a soma e o produto deles serão sempre números primos entre si.
• Se a e b são dois números naturais quaisquer (≠ 0), os números b e a × b + 1 são sempre primos entre si.
• Os números a; a + 1 e 2a + 1 são sempre primos entre si, dois a dois.
DIVISORES
O conjunto dos divisores de um inteiro a, que denotaremos por D(a), é tal que D(a) = {x ∈ * / x|a}.
Exemplo:
D(0) = *,D(30) = {±1, ±2, ±3, ±5, ±6, ±10, ±15, ±30}.
Se 12 k
12 k a pp p αα α = , um divisor natural de a é da forma
12 k pp p 12 k
ββ β … , em que 0 ≤ βi ≤ αi
para todo 1 ≤ i ≤ k.
Como 30 = 2 ⋅ 3 ⋅ 5, os divisores naturais de 30 são 20 ⋅ 30 ⋅ 50 = 1, 21 ⋅ 30 ⋅ 50= 2, 20 ⋅ 31 ⋅ 50= 3, 20 ⋅ 30 ⋅ 51 = 5, 21 ⋅ 31 ⋅ 50 = 6, 21 ⋅ 30 ⋅ 51 = 10, 20 ⋅ 31 ⋅ 51 = 15 e 21 ⋅ 31 ⋅ 51 = 30.
Outro método para obter os divisores de um inteiro consiste em efetuar a sua decomposição em fatores primos. Em seguida, traça-se uma vertical à direita da decomposição e escreve-se no topo o número 1. Cada um dos fatores primos da decomposição será multiplicado pelo número 1 e também por todos os resultados obtidos antes dele.
Exemplo:
30 2 1
15 3 2
5 5 3 – 6
1 5 – 10 – 15 – 30
Divisores Próprios: são todos os divisores de um número, excetuando-se ele mesmo.
POTÊNCIAS PERFEITAS
Um número n é dito um quadrado perfeito se existe k ∈ tal que n = k2. É fácil demonstrar que um número é um quadrado perfeito se, e somente se, o expoente de cada primo em sua fatoração for um número par.
Um número n é dito um cubo perfeito se existe k ∈ tal que n = k3. É fácil demonstrar que um número é um cubo perfeito se, e somente se, o expoente de cada primo em sua fatoração é um número múltiplo de três.
Geralmente, um número n é dito uma potência m-ésima se existe k ∈ tal que n = km. É fácil demonstrar que um número é uma potência m-ésima se, e somente se, o expoente de cada primo em sua fatoração for um número múltiplo de m.
Exemplo:
441 = 32 ⋅ 72 é um quadrado perfeito, 729 = 36 é um quadrado perfeito, um cubo perfeito e também uma potência 6-ésima.
QUANTIDADE DE DIVISORES
Se 12 k n pp p 12 k
αα α = , o número de divisores naturais de n é dado
por d(n) = (α1
+ 1)(α2
+ 1)…(αk
+ 1).
ProBizu
Para achar o número de divisores inteiros de n, basta multiplicar d(n) por 2. Se estivermos interessados no número de divisores naturais de n que são múltiplos de um determinado inteiro a, basta achar o número de divisores naturais de n a .
Exemplo:
Consideremos o número 22680 = 23 ⋅ 34 ⋅ 5 ⋅ 7.
O número de divisores é (3+1)(4+1)(1+1)(1+1) = 80.
O número de divisores ímpares é (4+1)(1+1)(1+1) = 20. (basta
descontar o fator 2).
O número de divisores múltiplos de 9 é (3+1)(2+1)(1+1)(1+1) = 48.
SOMA DOS DIVISORES NATURAIS
Se 12 k n pp p 12 k
αα α = , a soma dos divisores naturais de n é dada
por ( ) 12 k 11 1
12 k
12 k
p 1p 1 p 1 n p1 p1 p1
α+ α + α + −− − σ= ⋅ −− − .
Exemplo:
Calcular a soma dos divisores de 22680 = 23 ⋅ 34 ⋅ 5 ⋅ 7.
Temos que ( ) 4522 2 13 15 17 1 22680 87120
21 315171
−−−− σ = ⋅⋅⋅= −−−− .
PRODUTO DOS DIVISORES NATURAIS
O produto dos divisores naturais de n é dado por ( ) d n( ) 2 ∏ = n n .
Para demonstrar isso, basta perceber que se d | n, então n | n d e que n d n d ⋅ = .
Exemplo:
O produto dos divisores naturais de 30 é dado por d 30 ( ) 2 4 30 30 810000 = =
FÓRMULA DE LEGENDRE-POLIGNAC
A função maior inteiro (ou função piso) é a função que associa a cada número real x o maior inteiro maior ou igual a x e é denotada por x . xx x = + { } , em que 0 ≤ {x} < 1 é a parte fracionária de x.
Exemplo:
2 2, 2,1 2, 2,1 3 = = − =− Sendo n! o produto dos n primeiros inteiros positivos, temos que, se p é um primo, então o expoente de p na fatoração em primos de p! é dado por 2 3 nn n pp p
+++ ., em que x denota o maior inteiro que é menor ou igual a x. Por exemplo, 3,4 3 = e − =− 2,7 3.
Esta soma parece in nita, mas na verdade não é, pois em algum momento, teremos que as potências de p superarão n.
Exemplo:
Em quantos zeros termina 1000! = 1 ⋅ 2 ⋅ 3 ⋅ 4 ⋅ … ⋅ 1000?
Para cada fator 10 de um número, há um zero no final de sua representação decimal. Uma potência de 10 é formada por um fator 2 e um fator 5. Como há mais fatores 2 do que 5, para encontrar a quantidade de fatores 10 em 1000!, basta contar a quantidade de fatores 5. Isso é feito dividindo-se 1000 sucessivamente por 5 como segue:
1000 5
0 200 5
0 40 5
0 8 5
3 1
Somando-se os quocientes, encontramos a quantidade de fatores 5, ou seja, 200 + 40 + 8 + 1 = 249. Logo, a quantidade de zeros no final da representação de 1000! é 249.
Alternativamente, poderíamos utilizar a fórmula de Legendre- Polignac para encontrar a quantidade de fatores 5 em 1000!. Assim, 234 1000 1000 1000 1000 200 40 8 1 249
Note que se k ≥ 5, temos k
1000 0
5
= .
Exemplo:
O expoente de 3 na fatoração de 20! é dado por
20 20 628
3 9
+ =+= .
FUNÇÃO PHI DE EULER (φ)]
A função φ de Euler é uma função aritmética definida para todo inteiro positivo n tal que φ(n) conta o número de inteiros positivos menores que n e que são primos relativos com n.
Exemplo:
φ(12) = 4, pois 1, 5, 7, 11 são primos entre si com 12. Em geral, temos que se 12 k n pp p 12 k αα α = , então ( ) 12 k 11 1 n n1 1 1 pp p φ= − − −
Exemplo:
24 = 23 ⋅ 3, logo seus fatores primos são p1
= 2 e p2
= 3. Daí
( ) 1 1 12 24 24 1 1 24. . 8
2 3 23
φ = − −= = .
