Artigos

1.4: Fatoração Prime - Matemática


Na afirmação 3 · 4 = 12, o número 12 é chamado de produtos, enquanto 3 e 4 são chamados fatores.

Exemplo 1

Encontre todos os fatores de número inteiro de 18.

Solução

Precisamos encontrar todos os pares de números inteiros cujo produto seja igual a 18. Os pares a seguir vêm à mente.

1 · 18 = 18 e 2 · 9 = 18 e 3 · 6 = 18.

Portanto, os fatores de 18 são (na ordem) 1, 2, 3, 6, 9 e 18.

Exercício

Encontre todos os fatores de número inteiro de 21.

Responder

1, 3, 7 e 21

Divisibilidade

No Exemplo 1, vimos 3 · 6 = 18, fazendo 3 e 6 fatores de 18. Como a divisão é o inverso da multiplicação, ou seja, a divisão por um número desfaz a multiplicação desse número, isso fornece imediatamente

18 ÷ 6 = 3 e 18 ÷ 3 = 6.

Ou seja, 18 é divisível por 3 e 18 é divisível por 6. Quando dizemos que 18 é divisível por 3, queremos dizer que quando 18 é dividido por 3, há um resto zero.

Divisível

Deixar uma e b ser números inteiros. Então uma é divisível por b se e somente se o resto for zero quando uma é dividido por b. Neste caso, dizemos que “b é um divisor de uma.”

Exemplo 2

Encontre todos os divisores de número inteiro de 18.

Solução

No Exemplo 1, vimos que 3 · 6 = 18. Portanto, 18 é divisível por 3 e 6 (18 ÷ 3 = 6 e 18 ÷ 6 = 3). Portanto, quando 18 é dividido por 3 ou 6, o resto é zero. Portanto, 3 e 6 são divisores de 18. Observando os outros produtos no Exemplo 1, a lista completa de divisores de 18 é 1, 2, 3, 6, 9 e 18.

Exercício

Encontre todos os divisores de número inteiro de 21.

Responder

1, 3, 7 e 21.

Exemplo 1 e Exemplo 2 mostram que ao trabalhar com números inteiros, as palavras fator e divisor são intercambiáveis.

Fatores e divisores

Se c = uma · b, então uma e b são chamados fatores de c. Ambos uma e b também são chamados divisores de c.

Testes de Divisibilidade

Existem vários testes de divisibilidade muito úteis.

Divisível por 2. Se um número inteiro terminar em 0, 2, 4, 6 ou 8, então o número é chamado de número par e é divisível por 2. Exemplos de números pares são 238 e 1.246 (238 ÷ 2 = 119 e 1, 246 ÷ 2 = 623). Um número que não é par é chamado de número ímpar. Exemplos de números ímpares são 113 e 2.339.

Divisível por 3. Se a soma dos dígitos de um número inteiro for divisível por 3, então o próprio número é divisível por 3. Um exemplo é 141. A soma dos dígitos é 1 + 4 + 1 = 6, que é divisível por 3. Portanto , 141 também é divisível por 3 (141 ÷ 3 = 47).

Divisível por 4. Se o número representado pelos dois últimos dígitos de um número inteiro for divisível por 4, o próprio número será divisível por 4. Um exemplo é 11.524. Os dois últimos dígitos representam 24, que é divisível por 4 (24 ÷ 4 = 6). Portanto, 11.524 é divisível por 4 (11, 524 ÷ 4 = 2, 881).

Divisível por 5. Se um número inteiro terminar em zero ou 5, então o número é divisível por 5. Os exemplos são 715 e 120 (715 ÷ 5 = 143 e 120 ÷ 5 = 24).

Divisível por 6. Se um número inteiro é divisível por 2 e por 3, então ele é divisível por 6. Um exemplo é 738. Primeiro, 738 é par e divisível por 2. Segundo, 7 + 3 + 8 = 18, que é divisível por 3. Portanto, 738 é divisível por 3. Como 738 é divisível por 2 e 3, ele é divisível por 6 (738 ÷ 6 = 123).

Divisível por 8. Se o número representado pelos últimos três dígitos de um número inteiro for divisível por 8, o próprio número será divisível por 8. Um exemplo é 73.024. Os últimos três dígitos representam o número 24, que é divisível por 8 (24 ÷ 8 = 3). Assim, 73.024 também é divisível por 8 (73, 024 ÷ 8 = 9, 128).

Divisível por 9. Se a soma dos dígitos de um número inteiro for divisível por 9, então o próprio número é divisível por 9. Um exemplo é 117. A soma dos dígitos é 1 + 1 + 7 = 9, que é divisível por 9. Portanto , 117 é divisível por 9 (117 ÷ 9 = 13).

Números primos

Começamos com a definição de um número primo.

Número primo

Um número inteiro (diferente de 1) é um número primo se seus únicos fatores (divisores) forem 1 e ele mesmo. Equivalentemente, um número é primo se, e somente se, tiver exatamente dois fatores (divisores).

Exemplo 3

Qual dos números inteiros 12, 13, 21 e 37 são números primos?

Solução

  • Os fatores (divisores) de 12 são 1, 2, 3, 4, 6 e 12. Portanto, 12 não é um número primo.
  • Os fatores (divisores) de 13 são 1 e 13. Como seus únicos divisores são 1 e ele mesmo, 13 é um número primo.
  • Os fatores (divisores) de 21 são 1, 3, 7 e 21. Portanto, 21 não é um número primo.
  • Os fatores (divisores) de 37 são 1 e 37. Como seus únicos divisores são 1 e ele mesmo, 37 é um número primo.

Exercício

Qual dos números inteiros 15, 23, 51 e 59 são números primos?

Responder

23 e 59

Exemplo 4

Liste todos os números primos menores que 20.

Solução

Os números primos menores que 20 são 2, 3, 5, 7, 11, 13, 17 e 19.

Tente você!

Liste todos os números primos menores que 100.

Números compostos

Se um número inteiro não for um número primo, ele é chamado de número composto.

Exemplo 5

O número inteiro 1.179 é primo ou composto?

Solução

Observe que 1 + 1 + 7 + 9 = 18, que é divisível por 3 e 9. Portanto, 3 e 9 são ambos divisores de 1.179. Portanto, 1.179 é um número composto.

Exercício

O número inteiro 2.571 é primo ou composto?

Responder

Composto

Árvores de fator

Aprenderemos agora como expressar um número composto como um produto único de números primos. O dispositivo mais popular para atingir esse objetivo é o árvore do fator.

Exemplo 6

Expresse 24 como um produto de fatores primos.

Solução

Usamos uma árvore de fatores para decompor 24 em um produto de primos.

Em cada nível da árvore, divida o número atual em um produto de dois fatores. O processo está completo quando todas as “folhas circuladas” na parte inferior da árvore são números primos. Organizando os fatores nas "folhas circuladas" em ordem,

24 = 2 · 2 · 2 · 3.

A resposta final não depende das escolhas do produto feitas em cada nível da árvore. Aqui está outra abordagem.

A resposta final é encontrada incluindo todos os fatores das “folhas circuladas” no final de cada galho da árvore, o que produz o mesmo resultado, a saber, 24 = 2 · 2 · 2 · 3.

Abordagem Alternativa

Alguns preferem dividir repetidamente por 2 até que o resultado não seja mais divisível por 2. Em seguida, tente dividir repetidamente pelo próximo primo até que o resultado não seja mais divisível por esse primo. O processo termina quando o último quociente resultante é igual ao número 1.

A primeira coluna revela a fatoração primária; ou seja, 24 = 2 · 2 · 2 · 3.

Exercício

Expresse 36 como um produto de fatores primos.

Responder

2 · 2 · 3 · 3.

O fato de que a abordagem alternativa no Exemplo 6 produziu o mesmo resultado é significativo.

Teorema de Fatoração Única

Cada número inteiro pode ser unicamente fatorado como um produto de primos.

Esse resultado garante que, se os fatores primos forem ordenados do menor ao maior, todos obterão o mesmo resultado ao dividir um número em um produto de fatores primos.

Expoentes

Começamos com a definição de uma expressão exponencial.

Expoentes

A expressão umam é definido para significar

(a ^ {m} = underbrace {a cdot a cdot ldots cdot a} _ {m text {vezes}} )

O número uma é chamada de base da expressão exponencial e o número m é chamado de expoente. O expoente m nos diz para repetir a base uma como um fator m vezes.

Exemplo 7

Avalie 25, 23, e 52.

Solução

  • No caso de 25, temos

25 = 2 · 2 · 2 · 2 · 2

= 32.

  • No caso de 33, temos

33 = 3 · 3 · 3

= 27.

  • No caso de 52, temos

52 = 5 · 5

= 25.

Exercício

Avalie: 35.

Responder

243.

Exemplo 8

Expresse a solução do Exemplo 6 em forma compacta usando expoentes.

Solução

No Exemplo 6, determinamos a fatoração principal de 24.

24 = 2 · 2 · 2 · 3

Como 2 · 2 · 2 = 23, podemos escrever isso de forma mais compacta.

24 = 23 · 3

Exercício

Fator principal 54.

Responder

2 · 3 · 3 · 3

Exemplo 9

Avalie a expressão 23 · 32 · 52.

Solução

Primeiro eleve cada fator até o expoente fornecido e, em seguida, faça a multiplicação em ordem (da esquerda para a direita).

23 · 32 · 52 = 8 · 9 · 25

= 72 · 25

= 1800

Exercício

Avalie: 33 · 52.

Responder

675

Aplicativo

Um quadrado é um retângulo com quatro lados iguais.

Área de um quadrado

Deixar s representam o comprimento de cada lado de um quadrado.

Como um quadrado também é um retângulo, podemos encontrar a área do quadrado multiplicando seu comprimento e largura. No entanto, neste caso, o comprimento e a largura são iguais a s, então UMA = (s)(s) = s2. Portanto, a fórmula para a área de um quadrado é

UMA = s2.

Exemplo 10

A borda de um quadrado tem 13 centímetros. Encontre a área de um quadrado.

Solução

Substituto s = 13 cm na fórmula da área.

UMA = s2

= (13 cm)2

= (13 cm) (13 cm)

= 169 cm2

Portanto, a área do quadrado é de 169 cm2; ou seja, 169 centímetros quadrados.

Exercício

A borda de uma praça tem 15 metros. Encontre a área de um quadrado.

Responder

225 metros quadrados

Exercícios

Nos Exercícios 1-12, encontre todos os divisores do número fornecido.

1. 30

2. 19

3. 83

4. 51

5. 91

6. 49

7. 75

8. 67

9. 64

10. 87

11. 14

12. 89


Nos Exercícios 13-20, qual dos seguintes números não é divisível por 2?

13. 117, 120, 342, 230

14. 310, 157, 462, 160

15. 30, 22, 16, 13

16. 382, 570, 193, 196

17. 105, 206, 108, 306

18. 60, 26, 23, 42

19. 84, 34, 31, 58

20. 66, 122, 180, 63


Nos Exercícios 21-28, qual dos números a seguir não é divisível por 3?

21. 561, 364, 846, 564

22. 711, 850, 633, 717

23. 186, 804, 315, 550

24. 783, 909, 504, 895

25. 789, 820, 414, 663

26. 325, 501, 945, 381

27. 600, 150, 330, 493

28. 396, 181, 351, 606


Nos exercícios 29-36, qual dos seguintes números não é divisível por 4?

29. 3797, 7648, 9944, 4048

30. 1012, 9928, 7177, 1592

31. 9336, 9701, 4184, 2460

32. 2716, 1685, 2260, 9788

33. 9816, 7517, 8332, 7408

34. 1788, 8157, 7368, 4900

35. 1916, 1244, 7312, 7033

36. 7740, 5844, 2545, 9368


Nos exercícios 37-44, qual dos números a seguir não é divisível por 5?

37. 8920, 4120, 5285, 9896

38. 3525, 7040, 2185, 2442

39. 8758, 3005, 8915, 3695

40. 3340, 1540, 2485, 2543

41. 2363, 5235, 4145, 4240

42. 9030, 8000, 5445, 1238

43. 1269, 5550, 4065, 5165

44. 7871, 9595, 3745, 4480


Nos exercícios 45-52, qual dos seguintes números não é divisível por 6?

45. 328, 372, 990, 528

46. 720, 288, 148, 966

47. 744, 174, 924, 538

48. 858, 964, 930, 330

49. 586, 234, 636, 474

50. 618, 372, 262, 558

51. 702, 168, 678, 658

52. 780, 336, 742, 312


Nos Exercícios 53-60, qual dos seguintes números não é divisível por 8?

53. 1792, 8216, 2640, 5418

54. 2168, 2826, 1104, 2816

55. 8506, 3208, 9016, 2208

56. 2626, 5016, 1392, 1736

57. 4712, 3192, 2594, 7640

58. 9050, 9808, 8408, 7280

59. 9808, 1232, 7850, 7912

60. 3312, 1736, 9338, 3912


Nos Exercícios 61-68, qual dos seguintes números não é divisível por 9?

61. 477, 297, 216, 991

62. 153, 981, 909, 919

63. 153, 234, 937, 675

64. 343, 756, 927, 891

65. 216, 783, 594, 928

66. 504, 279, 307, 432

67. 423, 801, 676, 936

68. 396, 684, 567, 388


Nos Exercícios 69-80, identifique o número fornecido como primo, composto ou nenhum.

69. 19

70. 95

71. 41

72. 88

73. 27

74. 61

75. 91

76. 72

77. 21

78. 65

79. 23

80. 36


Nos Exercícios 81-98, encontre a fatoração primária do número natural.

81. 224

82. 320

83. 108

84. 96

85. 243

86. 324

87. 160

88. 252

89. 32

90. 128

91. 360

92. 72

93. 144

94. 64

95. 48

96. 200

97. 216

98. 392


Nos Exercícios 99-110, calcule o valor exato da expressão exponencial fornecida.

99. 52 · 41

100. 23 · 41

101. 01

102. 13

103. 33 · 02

104. 33 · 22

105. 41

106. 52

107. 43

108. 42

109. 33 · 12

110. 52 · 23


Nos Exercícios 111-114, encontre a área do quadrado com o lado dado.

111,28 polegadas

112,31 polegadas

113,2 polegadas

114,13 polegadas


Crie árvores de fatores para cada número nos Exercícios 115-122. Escreva a fatoração principal para cada número na forma compacta, usando expoentes.

115. 12

116. 18

117. 105

118. 70

119. 56

120. 56

121. 72

122. 270


123. Peneira de Eratóstenes. Este exercício apresenta o Peneira de Eratóstenes, um algoritmo antigo para encontrar os primos menores que um certo número n, criado pela primeira vez pelo matemático grego Eratóstenes. Considere a grade de inteiros de 2 a 100.

Para encontrar os primos menores que 100, proceda da seguinte maneira.

i) Eliminar todos os múltiplos de 2 (4, 6, 8, etc.)

ii) O próximo número da lista que não foi eliminado é um número primo.

iii) Eliminar da lista todos os múltiplos do número que você identificou na etapa (ii).

iv) Repita os passos (ii) e (iii) até que você não possa mais acertar mais múltiplos.

v) Todos os números não batidos na lista são primos.

Respostas

1. 1, 2, 3, 5, 6, 10, 15, 30

3. 1, 83

5. 1, 7, 13, 91

7. 1, 3, 5, 15, 25, 75

9. 1, 2, 4, 8, 16, 32, 64

11. 1, 2, 7, 14

13. 117

15. 13

17. 105

19. 31

21. 364

23. 550

25. 820

27. 493

29. 3797

31. 9701

33. 7517

35. 7033

37. 9896

39. 8758

41. 2363

43. 1269

45. 328

47. 538

49. 586

51. 658

53. 5418

55. 8506

57. 2594

59. 7850

61. 991

63. 937

65. 928

67. 676

69. prime

71. prime

73. composto

75. composto

77. composto

79. prime

81. 2 · 2 · 2 · 2 · 2 · 7

83. 2 · 2 · 3 · 3 · 3

85. 3 · 3 · 3 · 3 · 3

87. 2 · 2 · 2 · 2 · 2 · 5

89. 2 · 2 · 2 · 2 · 2

91. 2 · 2 · 2 · 3 · 3 · 5

93. 2 · 2 · 2 · 2 · 3 · 3

95. 2 · 2 · 2 · 2 · 3

97. 2 · 2 · 2 · 3 · 3 · 3

99. 100

101. 0

103. 0

105. 4

107. 64

109. 27

111,784 pol.2

113. 484 pol.2

115. 12 = 22 · 3

117. 105 = 3 · 5 · 7

119. 56 = 23 · 7

121. 72 = 23 · 32

123. Os números não batidos são primos: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79 , 83, 89, 97


Fatoração Prime

Aprender como encontrar a fatoração primária de um número é importante quando começamos a aprender sobre frações. Isso é especialmente importante quando começamos a reduzir as frações. Aqui estão algumas palavras de vocabulário que o ajudarão com esta lição:

  • Fatore & # 61 um número que divide uniformemente em outro número (Exemplo: 3 é um fator de 12 porque 12 & divide 3 é um número inteiro).
  • qualquer número onde os únicos fatores são 1 e ele mesmo (Exemplo: 11 é um número primo. Não há outro número além de 1 e 11 que você pode dividir por que lhe dará um número inteiro).

O primeiro vídeo explicará mais sobre os primos e como determinar se um número é primo.

Uma vez que sabemos o que são os números primos, aprendemos que cada número é composto de números primos menores. A divisão de um número nos primos que o formam é chamada de fatoração primo. Cada número tem uma fatoração primária. Para os números primos, seus únicos fatores são eles próprios e 1. Este vídeo mostrará como encontrar a fatoração primo de um número e trabalhar com alguns exemplos.

É muito útil memorizar alguns dos números primos, o que tornará mais fácil encontrar a fatoração de primos em problemas futuros. Use este gráfico para memorizar os primos até 20. Familiarize-se com os números primos até 100.

Recursos adicionais

Encontre a fatoração principal dos seguintes números:

Soluções

3 & # 215 7 & # 61 21 e 3 e 7 são fatores primários. A fatoração principal do número 21 é 3 e 7

A definição de um número primo é qualquer número em que os únicos fatores sejam 1 e ele mesmo.

Os únicos fatores de 13 são 1 e ele mesmo, 13. A fatoração principal de 13 é apenas 13.

Primeiro, encontre os fatores de 12. Aqui, mostramos algumas maneiras de fatorar 12. Ele pode ser fatorado como 4 & # 215 3 ou 6 & # 215 2

Os números 3 e 2 são primos, mas 4 e 6 não são.

Em seguida, encontre os fatores de 4 ou 6. Observe como a fatoração principal de 12 é 2 & # 215 2 & # 215 3 se os fatores iniciais foram 4 & # 215 3 de 6 & # 215 2. A fatoração principal é a mesma .

54 é um número par, portanto sabemos que é divisível por 2.

O número 2 é primo, mas 27 não, portanto, devemos encontrar os fatores de 27.

O número 3 é um número primo, mas 9 não é primo, então devemos encontrar os fatores de 9.

O número 3 é um número primo, então há na verdade mais dois 3 em nossa fatoração principal.

Agora voltamos e encontramos todos os números primos na fatoração de 54.


Calculadora de fatoração principal

Forneça um número inteiro para encontrar seus fatores primos, bem como uma árvore de fatores.

O que é um número primo?

Os números primos são números naturais (números inteiros positivos que às vezes incluem 0 em certas definições) que são maiores que 1, que não podem ser formados pela multiplicação de dois números menores. Um exemplo de um número primo é 7, uma vez que ele só pode ser formado pela multiplicação dos números 1 e 7. Outros exemplos incluem 2, 3, 5, 11, etc.

Os números que podem ser formados com dois outros números naturais, maiores que 1, são chamados de números compostos. Exemplos disso incluem números como 4, 6, 9, etc.

Os números primos são amplamente usados ​​na teoria dos números devido ao teorema fundamental da aritmética. Este teorema afirma que os números naturais maiores que 1 são primos ou podem ser fatorados como um produto de números primos. Como exemplo, o número 60 pode ser fatorado em um produto de números primos da seguinte maneira:

Como pode ser visto no exemplo acima, não há números compostos na fatoração.

O que é fatoração primária?

A fatoração primária é a decomposição de um número composto em um produto de números primos. Existem muitos algoritmos de fatoração, alguns mais complicados do que outros.

Um método para encontrar os fatores primos de um número composto é a divisão experimental. A divisão de teste é um dos algoritmos mais básicos, embora seja altamente tedioso. Envolve testar cada inteiro dividindo o número composto em questão pelo inteiro e determinando se, e quantas vezes, o inteiro pode dividir o número igualmente. Como um exemplo simples, abaixo está a fatoração principal de 820 usando a divisão experimental:

Como 205 não é mais divisível por 2, teste os próximos números inteiros. 205 não pode ser dividido igualmente por 3. 4 não é um número primo. No entanto, pode ser dividido por 5:

Como 41 é um número primo, isso conclui a divisão de teste. Desse modo:

Os produtos também podem ser escritos como:

Este é essencialmente o método da "força bruta" para determinar os fatores primos de um número e, embora 820 seja um exemplo simples, pode se tornar muito mais tedioso muito rapidamente.

Outra maneira comum de conduzir a fatoração primária é conhecida como decomposição primária e pode envolver o uso de uma árvore de fatores. A criação de uma árvore de fatores envolve a divisão do número composto em fatores do número composto, até que todos os números sejam primos. No exemplo abaixo, os fatores primos são encontrados dividindo-se 820 por um fator primo, 2, e continuando a dividir o resultado até que todos os fatores sejam primos. O exemplo abaixo demonstra duas maneiras que uma árvore de fator pode ser criada usando o número 820:

Assim, pode-se ver que a fatoração primária de 820, em ambos os casos, novamente é:

Embora esses métodos funcionem para números menores (e há muitos outros algoritmos), não há algoritmo conhecido para números muito maiores e pode levar um longo período de tempo até mesmo para as máquinas computarem as fatorações primos de números maiores em 2009, cientistas concluiu um projeto usando centenas de máquinas para fatorar o número de 232 dígitos, RSA-768, e levou dois anos.


Fatoração

Da divisão para multiplicação para fatoração.

Divisão e multiplicação são operações relacionadas.

A divisão 6 ÷ 3 = 2 pode ser escrita como uma multiplicação: 6 = 2 × 3

Fatorar um número inteiro é escrevê-lo como um produto de dois ou mais números inteiros.

1) 6 = 1 × 6 6 = 2 × 3 1, 2, 3 e 6 são chamados de fatores de 6.

2) 12 = 12 × 1 = 3 × 4 = 6 × 2 1, 2, 3, 4, 6 e 12 são chamados de fatores de 12.

3) 20 = 1 × 20 = 2 × 10 = 2 × 2 × 5 = 4 × 5 1, 2, 3, 4, 5, 10 e 20 são chamados de fatores de 20.


1.4: Fatoração Prime - Matemática

1.1.1. Definição. Um inteiro a é chamado de múltiplo de um inteiro b se a = bq para algum inteiro q. Nesse caso, também dizemos que b é um divisor de a, e usamos a notação b | uma.

No caso acima, também podemos dizer que b é um fator de a, ou que a é divisível por b. Se b não for um divisor de a, o que significa que a bq para todo q Z, então escrevemos b a. O conjunto de todos os múltiplos de um inteiro a será denotado por

1.1.2. Axioma. [Princípio de boa ordenação] Cada conjunto não vazio de números naturais contém um elemento menor.

1.1.3 Teorema. [Algoritmo de divisão] Para quaisquer inteiros aeb, com b & gt0, existem inteiros únicos q (o quociente) e r (o resto) tais que a = bq + r, com 0 r & ltb.

1.1.4. Teorema. Seja I um conjunto não vazio de inteiros que é fechado sob adição e subtração. Então I consiste apenas em zero ou então contém um menor elemento positivo, caso em que I consiste em todos os múltiplos de seu menor elemento positivo.

1.1.5. Definição. Um inteiro positivo d é chamado de maior divisor comum dos inteiros diferentes de zero a e b se (i) d é um divisor de a e b, e

(ii) qualquer divisor de aeb também é um divisor de d. Usaremos a notação gcd (a, b), ou simplesmente (a, b), para o máximo divisor comum de a e b.

1.1.6. Teorema. Quaisquer dois inteiros diferentes de zero a e b têm um maior divisor comum, que pode ser expresso como a menor combinação linear positiva de a e b.
Além disso, um inteiro é uma combinação linear de aeb se e somente se for um múltiplo de seu maior divisor comum.

O maior divisor comum de dois números pode ser calculado usando um procedimento conhecido como algoritmo euclidiano. Primeiro, observe que se a 0 e b | a, então mdc (a, b) = | b |. A próxima observação fornece a base para o algoritmo euclidiano. Se a = bq + r, então (a, b) = (b, r). Assim, dados inteiros a & gtb & gt0, o algoritmo euclidiano usa o algoritmo de divisão repetidamente para obter

Desde r1 & gt r2 & gt. . . , os restantes ficam cada vez menores e, após um número finito de passos, obtemos um resto rn + 1 = 0. Assim mdc (a, b) = mdc (b, r1) =. . . = rn.

1.2.1. Definição. Os inteiros diferentes de zero aeb são considerados relativamente primos se (a, b) = 1.

1.2.2 Proposição. Sejam a, b inteiros diferentes de zero. Então (a, b) = 1 se e somente se existirem inteiros m, n tais que

1.2.3 Proposição. Sejam a, b, c inteiros. (a) Se b | ac, então b | (abc.

(b) Se b | ac e (a, b) = 1, então b | c.

(c) Se b | a, c | a e (b, c) = 1, então bc | uma.

(d) (a, bc) = 1 se e somente se (a, b) = 1 e (a, c) = 1. 1.2.4. Definição. Um inteiro p & gt1 é chamado de número primo se seus únicos divisores forem & plusmn 1 e & plusmn p. Um inteiro a & gt 1 é chamado de composto se não for primo.

1.2.5. Lema. [Euclides] Um inteiro p & gt1 é primo se, e somente se, satisfaz a seguinte propriedade: If p | ab para inteiros aeb, então p | a ou p | b.

1.2.6. Teorema. [Teorema fundamental da aritmética] Qualquer número inteiro a & gt1 pode ser fatorado exclusivamente como um produto de números primos, na forma

1.2.7. Teorema. [Euclides] Existem infinitos números primos.

1.2.8. Definição. Um inteiro positivo m é chamado de mínimo múltiplo comum dos inteiros diferentes de zero a e b se (i) m é um múltiplo de a e b, e

(ii) qualquer múltiplo de aeb também é um múltiplo de m. Usaremos a notação lcm [a, b] para o mínimo múltiplo comum de a e b.

1.2.9. Proposição. Sejam aeb inteiros positivos com fatorações principais

onde umeu 0 e beu 0 para todo i (permitindo o uso dos mesmos fatores primos.)
Para cada eu deixei deu = min eu, beu > e deixe-meeu = max eu, beu >. Então temos as seguintes fatorações: (a) mdc (a, b) = p1 d1 p2 d2 & middot & middot & middot pn dn

Congruências

1.3.2. Proposição. Sejam a, b e n & gt0 inteiros. Então a b (mod n) se e somente se n | (a-b).

Ao trabalhar com módulo de congruência n, o inteiro n é chamado de módulo. Pela proposição anterior, a b (mod n) se e somente se a-b = nq para algum inteiro q. Podemos escrever isso na forma a = b + nq, para algum inteiro q. Esta observação fornece um método muito útil para substituir uma congruência por uma equação (sobre Z). Por outro lado, a Proposição 1.3.3 mostra que qualquer equação pode ser convertida para um módulo de congruência n simplesmente mudando o sinal = para. Ao fazer isso, qualquer termo congruente a 0 pode ser simplesmente omitido. Assim, a equação a = b + nq seria convertida de volta para a b (mod n).

1.3.3 Proposição. Seja n & gt0 um número inteiro. Então, as seguintes condições são válidas para todos os inteiros a, b, c, d: (a) Se a c (mod n) e b d (mod n), então

em seguida, a b c d (mod n) e ab cd (mod n).

(b) Se a + c a + d (mod n), então c d (mod n).

Se ac ad (mod n) e (a, n) = 1, então c d (mod n). 1.3.4. Proposição. Sejam a e n & gt1 inteiros. Existe um inteiro b tal que ab 1 (mod n) se e somente se (a, n) = 1.

1.3.5. Teorema. A congruência ax b (mod n) tem solução se e somente se b é divisível por d, onde d = (a, n).
Se d | b, então há d soluções distintas módulo n, e essas soluções são módulo congruente n / d.

1.3.6. Teorema. [Teorema do restante chinês] Sejam n e m inteiros positivos, com (n, m) = 1. Então o sistema de congruências

tem uma solução. Além disso, quaisquer duas soluções são congruentes módulo mn.

1.4.1. Definição. Sejam a e n & gt0 inteiros. O conjunto de todos os inteiros que têm o mesmo resto de a quando dividido por n é chamado de classe de congruência de um módulo n, e é denotado por [a]n, Onde

A coleção de todas as classes de congruência módulo n é chamada de conjunto de inteiros módulo n, denotado por Z n.

1.4.2 Proposição. Seja n um inteiro positivo e a, b quaisquer inteiros. Então, a adição e multiplicação das classes de congruência fornecidas abaixo são bem definidas:

1.4.3. Definição. Se um]n pertence a Z n, e [a]n[b]n = [0]n para alguma classe de congruência diferente de zero [b]n, então uma]n é chamado de divisor de zero, módulo n.

1.4.4. Definição. Se um]n pertence a Z n, e [a]n[b]n = [1]n, para alguma classe de congruência [b]n, então [b]n é chamado de inverso multiplicativo de [a]n e é denotado por [a]n -1 .
Nesse caso, dizemos que [a]n e B]n são elementos invertíveis de Z n, ou unidades de Z n.

1.4.5. Proposição. Seja n um número inteiro positivo. (a) A classe de congruência [a]n tem um inverso multiplicativo em Z n se e somente se (a, n) = 1.

(b) Um elemento diferente de zero de Z n ou tem um inverso multiplicativo ou é um divisor de zero. 1.4.6. Corolário. As seguintes condições no módulo n & gt 0 são equivalentes: (1) O número n é primo.

(2) Z n não tem divisores de zero, exceto [0]n.

(3) Cada elemento diferente de zero de Z n tem um inverso multiplicativo. 1.4.7. Definição. Seja n um número inteiro positivo. O número de inteiros positivos menores ou iguais an que são relativamente primos an será denotado por (n). Essa função é chamada de função phi de Euler, ou função totiente.

1.4.9. Definição. O conjunto de unidades de Z n, as classes de congruência [a]n, de modo que (a, n) = 1, será denotado por
Z n e vezes.

O teorema a seguir mostra que elevar qualquer classe de congruência em Z n & vezes à potência (n) produz a classe de congruência de 1. É possível dar uma prova teórica puramente numérica neste ponto, mas no Exemplo 3.2.12 há uma prova mais elegante usando a teoria dos grupos elementares.

1.4.11. Teorema. [Euler] Se (a, n) = 1, então a (n) 1 (mod n).

1.4.12 Corolário. [Fermat] Se p é primo, então a p a (mod p), para qualquer inteiro a.


Árvores de fator principal (intervalo de 4 a 48) (A)

Professores pode usar planilhas de matemática como teste, tarefas práticas ou ferramentas de ensino (por exemplo, em trabalho de grupo, para andaimes ou em um centro de aprendizagem). Pais pode trabalhar com seus filhos para lhes dar prática extra, para ajudá-los a aprender uma nova habilidade matemática ou para manter suas habilidades frescas durante os feriados escolares. Student s pode usar planilhas de matemática para dominar uma habilidade matemática por meio da prática, em um grupo de estudo ou para tutoria entre pares.

Use os botões abaixo para imprimir, abrir ou baixar a versão PDF do Árvores de fator principal (intervalo de 4 a 48) (A) planilha matemática. O tamanho do arquivo PDF é 34804 bytes. Imagens de visualização da primeira e da segunda (se houver) páginas são mostradas. Se houver mais versões desta planilha, as outras versões estarão disponíveis abaixo das imagens de visualização. Para mais informações desse tipo, use a barra de pesquisa para procurar algumas ou todas estas palavras-chave: numeração, número, sentido, matemática, matemática, fatores, primos, diagramas de árvore .

O Impressão botão irá iniciar a caixa de diálogo de impressão do seu navegador. O Abrir O botão abrirá o arquivo PDF completo em uma nova guia do navegador. O Professor O botão iniciará o download do arquivo PDF completo, incluindo as perguntas e respostas (se houver). Se um Aluna estiver presente, ele iniciará o download apenas da (s) página (s) de pergunta. Opções adicionais podem estar disponíveis clicando com o botão direito em um botão (ou mantendo um toque na tela de toque). Não vejo botões!

As árvores de fator principal (intervalo de 4 a 48) (A) Planilha matemática Page 1 As Árvores de Fator Principal (Faixa de 4 a 48) (A) Planilha Matemática Página 2

Lição: Fatoração Prime

· Puxe duas baquetas - os alunos completam as respostas no quadro branco - os alunos verificam o trabalho e o trabalho dos alunos (2 minutos) O professor ainda anda por aí para verificar a compreensão enquanto os alunos estão trabalhando a bordo.

· Verificar tudo - colocar todas as respostas no quadro branco

· Os alunos verificam todos os problemas do dever de casa (3 minutos - 1 minuto antes, 1 minuto atrás)

· O professor anda enquanto os alunos verificam o trabalho para intervir.

· O professor identifica um ou dois erros mais comuns na lição de casa e analisa toda a aula sobre transparência. (1 a 2 minutos) Antes da revisão - peça aos alunos que pensem sobre os passos que estou realizando enquanto resolvo o (s) problema (s) - eles compartilharão a aula inteira depois.

Passagem de papel em transição:

· Professor lê e mostra o problema

· O aluno puxa um pedaço de pau para chamar o aluno a responder

· Última sequência de problemas - todos os alunos completam e respondem levantando a mão - mão mais rápida chamada

§ Abertura: Hoje vamos aprender uma teoria da matemática super importante. Essa teoria diz que todo número pode ser fatorado em um produto de números primos de exatamente uma maneira. Antes de começarmos a aprender esta teoria super importante - vamos decompô-la com base em nosso conhecimento de vocabulário. O que significa a palavra primo? O que significa a palavra fator? O que significa a palavra produto?

§ Lançar: distribua calculadoras para todos os alunos.

o Mostre o seguinte no overhead: 15 x 28/20 x 7 x 3/3 x 35 x 4

o Peça aos alunos para usarem a calculadora para encontrar os produtos. Pergunte aos alunos o que eles notam. Todos eles equivalem a 420.

o Diga aos alunos que há muitas maneiras de escrever 420 como um produto (lembrar aos alunos os meios do produto como a resposta a um problema de multiplicação) Alguém pode encontrar outra maneira?

o Pergunte aos alunos como eles encontraram cada produto - se os alunos estão tendo problemas para explicar seu raciocínio ou estão presos em encontrar maneiras diferentes de encontrar outro produto, então elicite:

o A estratégia de combinação - Pegue partes dos problemas que já temos e combine-os para formar um novo número (em vez de 20 x 7 x 3 - múltiplos 7 x 3 e faça o problema 20 x 21.

o A estratégia de separação - pegar um número e dividi-lo em dois de seus fatores (15 x 28 - à 5 x 3 x 28 se você dividir 15)

o Exibir o quebra-cabeça do produto para os alunos - permitir que eles usem suas calculadoras

o Explique que o quebra-cabeça é como uma busca por palavras - exceto que vamos agrupar uma sequência de números cujo produto é igual a 1350. As sequências podem ir horizontalmente, verticalmente ou em torno dos cantos.

o Encontre um para eles como exemplo (linha superior - círculo 5 x 6 x 5 x 9) Peça ao aluno para usar calculadoras para ver se isso funciona.

o Encontre verticalmente - 5 x 3 x 10 x 9 - peça ao aluno para verificar se isso funciona

o Permita que os alunos procurem mais algumas strings que encontrarem.

o Compartilhe para toda a classe algumas das strings encontradas.

o Pegue uma corda do quebra-cabeça do produto e diga aos alunos que queremos quebrar a corda ainda mais longe até que tenhamos a corda mais longa possível. Saberemos que temos a seqüência mais longa possível quando a quebrarmos em seus fatores primos.

o Modelar dividindo o mesmo número de uma maneira diferente

o Mostrar circulando qualquer número primo um sinal para parar aquele galho da árvore.

o Faça anotações sobre a fatoração principal e como percorrer o processo

o Os alunos praticarão a criação de árvores de fatores para diferentes conjuntos de números.

o Discuta como podemos escrever produtos ou números primos com expoentes também - demonstre aos alunos - mostre os alunos trabalhando desde a sequência com expoentes até a sequência mais longa. Modelar para alunos e completar alguns exemplos.

§ Ponto-chave: cada número tem apenas uma longa sequência de fatores. A fatoração principal de qualquer número é única para aquele número.


FACTORIZAÇÃO COMPLETA

OBJETIVOS

  1. Primeiro, procure os fatores comuns.
  2. Fatore o trinômio restante aplicando os métodos deste capítulo.

Já estudamos todos os métodos usuais de fatoração encontrados na álgebra elementar. No entanto, você deve estar ciente de que um único problema pode exigir mais de um desses métodos. Lembre-se de que existem duas verificações para a fatoração correta.

Uma vez que um fator comum tenha sido encontrado, você deve verificar se o trinômio resultante é fatorável.

Se um trinômio tiver quaisquer fatores comuns, geralmente será mais fácil se eles forem fatorados primeiro.

Um bom procedimento a seguir na fatoração é sempre remover o maior fator comum primeiro e então fatorar o que resta, se possível.


Transformações de Laplace

Michael Carr,. Eabhnat Ní Fhloinn, em Cálculo para Estudantes de Engenharia, 2020

14.1.3 Frações parciais

Lidamos com muitas das expressões padrão na subseção anterior. No entanto, ainda precisamos considerar o que acontece quando obtemos uma expressão como

Não temos nenhuma transformação padrão para esta expressão. Mas pode ser mostrado que

Sabemos como lidar com o lado direito da Eq. (14,37), então agora podemos avaliar

onde 1 s + 7 e 1 s + 4 são chamadas de frações parciais da expressão 2 s + 11 s 2 + 11 s + 28. Vamos agora considerar como fazemos para encontrar as frações parciais de uma expressão.

Regras para encontrar frações parciais

A primeira etapa ao tentar decompor uma expressão em frações parciais é fatorar o denominador em seus fatores primos. Por exemplo, 1 s 2 + 9 s + 14 fatoriza para 1 (s + 7) (s + 2). Neste ponto, precisamos considerar a forma que os fatores assumem.

Um fator linear, por exemplo, 1 (s + a), dá uma fração parcial da forma A s + a, onde UMA é uma constante a ser determinada.

Exemplo 14.9

Um fator repetido da forma (s + a) 2 dá as frações parciais A s + a + B (s + a) 2.

Exemplo 14.10

Se o fator repetido assumir a forma 1 (s + a) 3, isso resultará em frações parciais de E s + a + F (s + a) 2 + G (s + a) 3.

Exemplo 14.11

Um fator quadrático 1 (s 2 + a s + b) dá uma fração parcial E s + F s 2 + a s + b.

Exemplo 14.12

Exemplo 14.13

Usando as regras 1 - 4 acima, podemos reescrever as seguintes expressões em formato de fração parcial:

Escreva as seguintes expressões como frações parciais: 1.

Depois de calcularmos as frações parciais, precisamos encontrar os valores das constantes. Por exemplo, suponha que temos

Para determinar as transformações inversas de Laplace

Exemplo 14.14

Existem várias etapas para determinar

Fatore o denominador 3 s - 5 s 2 - 8 s - 33 = 3 s - 5 (s - 11) (s + 3).

As frações parciais são da forma A s + 3 + B s - 11, dando-nos a identidade 3 s - 5 s 2 - 8 s - 33 = A s + 3 + B s - 11.


1.4: Fatoração Prime - Matemática

Esta página discute um pouco da matemática e dos algoritmos de computador usados ​​em uma busca eficiente por primos de Mersenne. Como sou mais um programador de computador do que um matemático, não irei entrar em muitos detalhes matemáticos, mas tentarei fornecer dicas.

Formando uma lista de expoentes

Mersenne numbers are of the simple form 2 P -1, where P is the exponent to be tested. It is easy to prove that if 2 P -1 is prime, then P must be a prime. Thus, the first step in the search is to create a list of prime exponents to test.

Trial Factoring

The next step is to eliminate exponents by finding a small factor. There are very efficient algorithms for determining if a number divides 2 P -1. For example, let's see if 47 divides 2 23 -1. Convert the exponent 23 to binary, you get 10111. Starting with 1, repeatedly square, remove the top bit of the exponent and if 1 multiply squared value by 2, then compute the remainder upon division by 47.

Thus, 2 23 = 1 mod 47. Subtract 1 from both sides. 2 23 -1 = 0 mod 47. Since we've shown that 47 is a factor, 2 23 -1 is not prime.

One very nice property of Mersenne numbers is that any factor q of 2 p -1 must be of the form 2kp+1. Furthermore, q must be 1 or 7 mod 8. A proof is available. Finally, an efficient program can take advantage of the fact that any potential factor q must be prime.

The GIMPS factoring code creates a modified sieve of Eratosthenes with each bit representing a potential 2kp+1 factor. The sieve then eliminates any potential factors that are divisible by prime numbers below 40,000 or so. Also, bits representing potential factors of 3 or 5 mod 8 are cleared. This process eliminates roughly 95% of potential factors. The remaining potential factors are tested using the powering algorithm above.

Now the only question remaining is how much trial factoring should be done? The answer depends on three variables: the cost of factoring, the chance of finding a factor, and the cost of a primality test. The formula used is:

Exponents up to Trial factor to
02 65
23,390,0002 66
29,690,0002 67
37,800,0002 68
47,450,0002 69
58,520,0002 70
75,670,0002 71
96,830,0002 72
115,300,0002 73
147,500,0002 74
186,400,0002 75
227,300,0002 76
264,600,0002 77
337,400,0002 78
420,400,0002 79
516,000,0002 80

P-1 Factoring

There is another factoring method that GIMPS uses to find factors and thereby avoid costly primality tests. This method is called Pollard's (P-1) method. If q is a factor of a number, then the P-1 method will find the factor q if q-1 is highly composite &ndash that is, it has nothing but small factors.

This method when adapted to Mersenne numbers is even more effective. Remember, that the factor q is of the form 2kp+1. It is easy to modify the P-1 method such that it will find the factor q whenever k is highly composite.

The P-1 method is quite simple. In stage 1 we pick a bound B1. P-1 factoring will find the factor q as long as all factors of k are less than B1 (k is called B1-smooth). We compute E &ndash the product of all primes less than B1. Then we compute x = 3 E*2*P . Finally, we check the GCD (x-1, 2 P -1) to see if a factor was found.

There is an enhancement to Pollard's algorithm called stage 2 that uses a second bound, B2. Stage 2 will find the factor q if k has just one factor between B1 and B2 and all remaining factors are below B1. This stage uses lots of memory.

GIMPS has used this method to find some impressive factors. Por exemplo:

So how does GIMPS intelligently choose B1 and B2? We use a variation of the formula used in trial factoring. We must maximize:

The chance of finding a factor and the factoring cost both vary with different B1 and B2 values. Dickman's function (see Knuth's Art of Computer Programming Vol. 2) is used to determine the probability of finding a factor, that is k is B1-smooth or B1-smooth with just one factor between B1 and B2. The program tries many values of B1 and (if there is sufficient available memory) several values of B2, selecting the B1 and B2 values that maximize the formula above.

Lucas-Lehmer Primality Testing

The methods described above are first used to attempt to find a factor for the Mersenne number and therefore eliminate the prime exponent P from the testing list before performing the relatively costly Lucas-Lehmer primality test.

The Lucas-Lehmer primality test is remarkably simple. It states that for P > 2, 2 P -1 is prime if and only if Sp-2 is zero in this sequence: S0 = 4, SN = (SN-1 2 - 2) mod (2 P -1).
For example, to prove 2 7 - 1 is prime:

To implement the Lucas-Lehmer test efficiently, one must find the fastest way to square huge numbers modulo 2 P -1. Since the late 1960's the fastest algorithm for squaring large numbers is to split the large number into pieces forming a large array, then perform a Fast Fourier Transform (FFT), a squaring, and an Inverse Fast Fourier Transform (IFFT). See the "How Fast Can We Multiply?" section in Knuth's Art of Computer Programming Vol. 2. In a January, 1994 Mathematics of Computation article by Richard Crandall and Barry Fagin titled " Discrete Weighted Transforms and Large-Integer Arithmetic ", the concept of using an irrational base FFT was introduced. This improvement more than doubled the speed of the squaring by allowing us to use a smaller FFT and it performs the mod 2 P -1 step for free. Although GIMPS uses a floating point FFT for reasons specific to the Intel Pentium architecture, Peter Montgomery showed that an all-integer weighted transform can also be used.

As mentioned in the last paragraph, GIMPS uses floating point FFTs written in highly pipelined, cache friendly assembly language. Since floating point computations are inexact, after every iteration the floating point values are rounded back to integers. The discrepancy between the proper integer result and the actual floating point result is called the convolution or roundoff error. If the convolution error ever exceeds 0.5 then the rounding step will produce incorrect results &ndash meaning a larger FFT should have been used. One of GIMPS' error checks is to make sure the maximum convolution error does not exceed 0.4.

What are the chances that the Lucas-Lehmer test will find a new Mersenne prime number? A simple approach is to repeatedly apply the observation that the chance of finding a factor between 2 X and 2 X+1 is about 1/x. For example, you are testing 2 10,000,139 -1 for which trial factoring has proved there are no factors less than 2 64 . The chance that it is prime is the chance of no 65-bit factor * chance of no 66-bit factor * . * chance of no 5,000,070-bit factor. That is:

This simplifies to 64 / 5000070 or 1 in 78126. This simple approach isn't quite right. It would give a formula of how_far_factored divided by (exponent divided by 2). However, more rigorous work has shown the formula to be (how_far_factored-1) / (exponent times Euler's constant (0.577. )). In this case, 1 in 91623. Even these more rigourous formulas are unproven.

Double-Checking

To verify that a first-time Lucas-Lehmer primality test was performed without error, GIMPS runs the primality test a second time. During each Lucas-Lehmer primality test, the low order 64 bits of the final SP-2 value, called a residue, are sent to PrimeNet and recorded. If these match, then GIMPS declares the exponent properly double-checked. If they do not match, then the primality test is run again until a match finally occurs. The double-check, which takes just as long as a first-time test, is usually done about 2 years after the first-time test. GIMPS assigns double-checks to slower PCs because the exponents are smaller than first-time tests, resulting in work units that can complete in a reasonable time on a slower PC.

GIMPS double-checking goes a bit further to guard against programming errors. Prior to starting the Lucas-Lehmer test, the S0 value is left-shifted by a random amount. Each squaring just doubles how much we have shifted the S value. Note that the mod 2 P -1 step merely rotates the p-th bits and above to the least significant bits, so there is no loss of information. Why do we go to this trouble? If there were a bug in the FFT code, then the shifting of the S values ensures that the FFTs in the first primality test are dealing with completely different data than the FFTs in the second primality test. It would be near impossible for a programming bug to produce the same final 64 bit residues.

Historically, the error rate for a Lucas-Lehmer test where no serious errors were reported during the run is around 1.5%. For Lucas-Lehmer tests where an error was reported the error rate is in the neighborhood of 50%.

Is there a better method than Lucas-Lehmer?

Starting in 2018, GIMPS started using a Fermat probable prime test rather than a Lucas-Lehmer test to search for new Mersenne primes. Robert Gerbicz devised a way to almost completely eliminate the chance of a hardware error corrupting the primality test. Even though results are 99.999+% reliable double-checking is still necessary to guard against program error or forged results. Gerbicz error checking does mean that GIMPS is extremely unlikely to miss a new Mersenne prime on the first test -- a big improvement a 1 or 2% chance of missing a new Mersenne prime on the first test.

Another breakthrough lets GIMPS completely avoid the double-checking process! Krzysztof Pietrzak showed how to create a PRP proof that cannot be faked and can be verified over 100 times faster than a standard double-check. In 2020 proofs were added to the GIMPS software and PRP with proofs became the preferred way to search for new Mersenne primes.


Assista o vídeo: Casos de Fatoração (Novembro 2021).