Números aleatórios

Prévia do material em texto

Parte VIII
Gerac¸a˜o de nu´meros
aleato´rios
28 Introduc¸a˜o
• A simulac¸a˜o de qualquer sistema onde existam com-
ponentes aleato´rias requer a gerac¸a˜o ou obtenc¸a˜o de
nu´meros que sa˜o “aleato´rios” em algum sentido.
– Ex.: para simular o tamanho de uma fila, preci-
samos determinar o tempo entre chegadas de cli-
entes e o tempo de atendimento de cada cliente,
que geralmente sa˜o modelados como varia´veis
aleato´rias pertencente a determinadas distri-
buic¸o˜es.
• Valores para varia´veis aleato´rias definidas por qual-
quer distribuic¸a˜o de probabilidades podem ser gera-
dos utilizando valores IID de uma varia´vel aleato´ria
com distribuic¸a˜o uniforme entre 0 e 1.
– Portanto, chamaremos de “nu´meros aleato´rios”
valores produzidos por uma varia´vel aleato´ria
com distribuic¸a˜o uniforme entre 0 e 1. Tratare-
mos a seguir da gerac¸a˜o deste valores.
• Os primeiros me´todos foram essencialmente manuais:
atirar objetos e dados, manipular cartas, retirar bolas
numeradas de urnas. Ainda hoje sa˜o usados em jogos
e em algumas loterias.
– No in´ıcio do se´culo XX alguns dispositivos fo-
ram criados para acelerar a gerac¸a˜o de nu´meros
aleato´rios: discos girato´rios e impulsos ele´tricos
no va´cuo (em tubos) (usados na de´cada de 50
pela loteria britaˆnica).
– Muitos outros esquemas sa˜o utilizados no dia-a-
dia: selecionar um nu´mero “aleatoriamente” em
uma lista telefoˆnica ou em algum relato´rio com
muitos nu´meros (como o censo), utilizar d´ıgitos
de algum nu´mero irracional (como π).
• Com a popularizac¸a˜o dos computadores maior
atenc¸a˜o foi dada para me´todos compat´ıveis com a
forma como os computadores trabalham. Considere-
mos as seguites possibilidades:
– Armazenar uma tabela de nu´meros aleato´rios.
Como atualmente e´ comum simulac¸o˜es que
utilizam milho˜es de nu´meros aleato´rios, este
nu´meros devem ser mantidos em armazena-
mento secunda´rio (como discos) que possuem
acesso mais lento.
– Acoplar um equipamento ele´trico para gerac¸a˜o
de nu´meros aleato´rios. A principal desvantagem
desta abordagem e´ a impossibilidade de repetir
uma sequeˆncia gerada anteriormente (armaze-
nar, como vimos, pode ser invia´vel).
• Portanto, as pesquisas nas de´cadas de 40 e
50 voltaram-se para a gerac¸a˜o de nu´meros
“aleato´rios” utilizando me´todos “nume´ricos”
ou “aritme´ticos”.
– Estes me´todos sa˜o sequenciais, com cada
novo nu´mero sendo determinado pelos anterio-
res com base em uma fo´rmula matema´tica fixa.
• A primeira tentativa neste sentido foi o me´todo
midsquare de von Neumann e Metropolis nos anos
40: Comec¸e com um nu´mero de 4 d´ıgitos e eleve ele
ao quadrado, resultando em um nu´mero com ate´ 8
d´ıgitos. Complete com zeros a esquerda para que a
representac¸a˜o tenha 8 d´ıgitos. Utilize os 4 d´ıgitos cen-
trais como o pro´ximo nu´mero aleato´rio. Para obter
um nu´mero entre 0 e 1 basta dividir por 104. Assim
sucessivamente para obter os pro´ximos.
– Intuitivamente o me´todo parece bom, ja´
que temos a tendeˆncia a achar que algo e´
“aleato´rio” quando na˜o conseguimos enxergar
padro˜es.
– Entretanto, este me´todo na˜o funciona bem.
Um dos problemas se´rios desta abordagem e´ a
forte tendeˆncia de gerar o valor 0, onde perma-
necera´ neste valor para sempre.
– Isto ilustra o perigo em assumir que sempre
conseguiremos um bom gerador de nu´meros
aleato´rios fazendo alguma coisa estranha
em um nu´mero para obter o pro´ximo.
n=100; x=zeros(1,n); x(1)=1234;
for i=2:n;
x(i)=mod(floor(x(i-1)*x(i-1)/100),10000);
end;
x=x/10000; hist(x)
• Uma cr´ıtica aos me´todos aritme´ticos em ge-
ral e´ o fato dos nu´meros gerados na˜o serem
“aleato´rios” (no sentido de ser imprevis´ıvel). De
fato, se conhecemos um nu´mero da se´rie gerada, sabe-
mos exatamente quais sera˜o todos os pro´ximos. Por
isso os nu´meros gerados por estes me´todos sa˜o muitas
vezes chamados de “pseudo-aleato´rios”.
– Na pra´tica, podemos aceitar geradores
aritme´ticos desde que produzam nu´meros
que se parec¸am com sorteios independentes de
uma distribuic¸a˜o uniforme entre 0 e 1. Ou seja,
que a sequeˆncia gerada passe com sucesso por
uma se´rie de testes estat´ısticos (isto sera´ usado
como definic¸a˜o de “nu´meros aleato´rios”).
• Um “bom” gerador deveria possuir as seguintes
propriedades:
22
1. Acima de tudo, os nu´meros deveriam parecer
distribu´ıdos uniformemente entre 0 e 1, e na˜o
deveriam exibir qualquer correlac¸a˜o entre eles.
Caso contra´rio, o resultado da simulac¸a˜o pode
ser completamente inva´lido.
2. Ser ra´pido e na˜o necessitar de muito armazena-
mento.
3. Permitir repetir a gerac¸a˜o de uma dada
sequeˆncia de nu´meros. Isto facilita a depurac¸a˜o
programa que simula o modelo, e permite a com-
parac¸a˜o de sistemas diferentes quando submeti-
dos aos mesmos eventos.
4. Permitir a gerac¸a˜o de subsequeˆncias disjuntas.
Cada subsequeˆncia e´ utilizada para simuladar
uma determinada fonte de “aleatoriedade”. In-
tersec¸o˜es entre estas subsequeˆncias pode produ-
zir correlac¸o˜es indesejadas.
• Os itens 2, 3 e 4 sa˜o atendidos por praticamente to-
dos os geradores propostos. Alguns artigos no final
da de´cada de 80 apontaram va´rios geradores utili-
zados na pra´tica que falham em atender o item 1
(o mais importante). Atualmente os softwares de
aux´ılio a` simulac¸a˜o esta˜o atentos a isso, e e´ fa´cil
conseguir bibliotecas gratuitas (para as linguagens de
programc¸a˜o mais populares) com geradores que aten-
dem ao item1.
28.1 Geradores congruentes
• Os me´todos baseados em congrueˆncias sa˜o da forma
Xi = f(Xi−1, Xi−2, . . .) (mod m), onde Xi e´ o i-
e´simo nu´mero gerado e f(.) e´ uma func¸a˜o deter-
min´ıstica fixada.
• Os valores gerados esta˜o entre 0 e m − 1. Portanto,
os nu´meros entre 0 e 1 sa˜o obtidos por Ui = Xi/m.
• ANALOGIA COM UMA ROLETA.
• Os geradores de nu´meros aleato´rios mais populares
sa˜o os Geradores Congruente Lineares. Estes sa˜o ge-
radores baseados em congrueˆncia onde f(.) e´ uma
func¸a˜o linear de Xi−1.
29 Geradores Congruente Linea-
res
• Sa˜o geradores definidos pela fo´rmula recursiva Xi =
(aXi−1+b) (mod m), onde m (o mo´dulo), a (o mul-
tiplicador), b (o incremento) e X0 (a semente) sa˜o
inteiros na˜o negativos. Ale´m disso, m > 0, a < m,
b < m e X0 < m.
– Ex.: m = 16, a = 5, b = 3 e X0 = 7, ou seja,
Xi = (5Xi−1 + 3) (mod 16). Portanto, X1 =
(5 ∗ 7 + 3) (mod 16) = 38 mod 16 = 6, X2 =
(5 ∗ 6 + 3) (mod 16) = 33 mod 16 = 1. Conti-
nuando os ca´lculos chegamos a X16 = 7 = X0,
ou seja, a partir deste ponto toda a sequeˆncia se
repete.
n=17; m=16; a=5; b=3; x=zeros(1,n); x(1)=7;
for i=2:n; x(i)=mod(a*x(i-1)+b,m); end;
x, x=x/m
• Uma objec¸a˜o para este me´todo e´ o fato de cada
valor Ui = Xi/m estar restrito ao conjunto
{0, 1/m, 2/m, . . . , (m− 1)/m}. Por exemplo, na˜o te-
mos como gerar um valor para Ui entre 1/m e 2/m,
o que deveria acontecer com probabilidade 1/m.
– Entretanto, com valores altos para m (utiliza-se
m ≥ 109) os valores de Ui fornecem uma boa
aproximac¸a˜o para distribuic¸a˜o uniforme entre 0
e 1.
• A repetic¸a˜o de parte da sequeˆncia (observada no
exemplo) e´ inevita´vel, e ocorre sempre que a
sequeˆncia atinge algum valor gerado anteriormente
(formando assim um ciclo).
– O comprimento do ciclo gerado e´ chamado de
“per´ıodo” do gerador.
– Como 0 ≤ Xi ≤ m − 1, temos que o per´ıodo e´
no ma´ximo m. Quando o per´ıodo e´ igual a m,
dizemos que o gerador e´ de “per´ıodo completo”.
– Quando o gerador e´ de per´ıodo completo, qual-
quer semente produzira´ o ciclo inteiro. Caso
contra´rio, o per´ıodo vai depender da semente
do gerador.
– Ex.1: Xi = (2Xi−1 + 1) (mod 5). Com se-
mente igual a 0, 1, 2 ou 3, o per´ıodo e´ igual a 4.
Com semente igual a 4 o per´ıodo e´ igual a 1.
– Ex.2: Xi = (3Xi−1 + 1) (mod 6). Existe ape-
nas 1 ciclo com per´ıodo 2 (do valor 1 para o 4 e
vice-versa). As sementes 0 e2 levam ao valor 1
(que pertence ao ciclo). As sementes 3 e 5 levam
ao valor 4 (que pertence ao ciclo).
• Como os projetos de simulac¸a˜o geralmente utilizam
muitos nu´meros aleato´rios, e´ necessa´rio que o per´ıodo
do gerador seja longo para evitar as repetic¸o˜es.
– Ale´m disso, os geradores com per´ıodo completo
sa˜o deseja´veis pelo fato de cada nu´mero entre 0
e m − 1 ter chance de ocorrer no ciclo (contri-
buindo para a uniformidade).
– Note pore´m que mesmo geradores com per´ıodo
completo podem gerar sequeˆncias na˜o unifor-
mes. Por exemplo, Xi = (Xi−1 + 1) (mod m)
tem per´ıodo completo, mas gera nu´meros na or-
dem 0, 1, 2, . . . ,m − 1. Ou seja, uma sequeˆncia
com k valores, onde k e´ muito menor que m,
possui apenas valores pro´ximos (e portanto, mal
distribu´ıdos no intervalo de 0 a` m− 1).
23
• O teorema a seguir (demonstrado por Hull e Dobell
em 1962) mostra as condic¸o˜es para que m, a e b pro-
duzam um gerador com per´ıodo completo.
Teorema1 Um gerador congruente linear tem
per´ıodo completo se e somente se as treˆs
condic¸o˜es a seguir sa˜o satisfeitas:
1. m e b sa˜o primos entre si. Ou seja, o u´nico
inteiro positivo que divide m e b e´ 1.
2. Se q e´ um nu´mero primo (divis´ıvel apenas por 1
e por ele pro´prio) que divide m, enta˜o q divide
a− 1.
3. Se 4 divide m, enta˜o 4 divide a− 1.
• Dividir por m para obter o resto e´ uma operac¸a˜o
aritme´tica lenta. Uma alternativa que evita esta di-
visa˜o e´ utilizar m = 2w para algum w (geralmente
o nu´mero de bits de uma word no computador utili-
zado).
– Neste caso, o resto sa˜o os u´ltimos w bits.
– Ex.: 11010 dividido por 22 = 110 mais resto 10.
– Atualmente a maioria dos computadores pos-
suem words com 32 ou 64 bits. Ou seja, descon-
siderando o bit de sinal temos m = 231 > 2.1
bilho˜es.
– Ale´m disso, se w e´ o nu´mero de bits de uma
word, esta abordagem se aproveita do “overflow
de inteiros”. Quando uma operac¸a˜o aritme´tica
provoca overflow, os bits mais significativos
sa˜o descartados (em algumas arquiteturas), so-
brando apenas o resto da divisa˜o por 2w.
– Ex.: Xi = (5Xi−1 +3) (mod 16), em um com-
putador hipote´tico com 4 bits por word. Se
X0 = 5, quanto vale X1? 5 ∗ 5 + 3 = 28 (11100
em bina´rio). Como ocorre overflow, o bit mais
significativo e´ perdido, restando 1100 (12 em de-
cimal). Note que X1 = 28 mod 16 = 12.
– E´ necessa´rio verificar exatamente como o over-
flow de inteiros e´ tratado, o que depende da ar-
quitetura do computador, do formato de repre-
sentac¸a˜o de inteiros e da linguagem utilizada.
Por exemplo, o bit de sinal pode ser modificado
na operac¸a˜o.
• Quando m = 2w, temos pelo Teorema 1 que o per´ıodo
completo e´ obtido se b e´ ı´mpar e a− 1 e´ divis´ıvel por
4.
– Valores para a e b que produzem bons geradores
podem ser obtidos por tentativas. Alguns valo-
res sa˜o fornecidos na literatura. Por exemplo,
para b = 31 Kobayashi propoˆs a = 314.159.269
e b = 453.806.245.
n=10000; m=2^31; a=314159269; b=453806245;
x=zeros(1,n); x(1)=0;
for i=2:n; x(i)=mod(a*x(i-1)+b,m); end;
x=x/m; hist(x)
• Note que geradores onde b = 0 (chamados de multi-
plicativos) na˜o satisfazem a primeira condic¸a˜o do Te-
orema 1, e portanto na˜o possuem per´ıodo completo.
– Pore´m, os geradores multiplicativos sa˜o mais efi-
cientes, mais simples, mais bem compreendidos
e mais utilizados. Analisaremos a seguir este
tipo de gerador.
29.1 Geradores Multiplicativos: b = 0
• Nesta sec¸a˜o analisaremos o gerador Xi = aXi−1
(mod m).
• Quando m = 2w, Knuth provou em 1981 que o
per´ıodo e´ no ma´ximo 2w−2 (ou seja, 1/4 do per´ıodo
completo).
– Ale´m disso, geralmente na˜o temos como deter-
minar m/4 inteiros esta˜o distribu´ıdos (pode ha-
ver grande concentrac¸a˜o em alguma regio˜es, pre-
judicando a uniformidade).
• Uma proposta para o valor de m que se mostrou bem
sucedida e´ utilizar o maior nu´mero primo menor que
2w.
– Ex.: O maior primo menor que 231 e´ 231 − 1.
• Knuth (1981) mostrou que para m primo, o per´ıodo
do gerador e´ m − 1 se a e´ um “elemento primitivo
mo´dulo m”, isto e´, o menor valor inteiro para c tal
que ac − 1 e´ divis´ıvel por m e´ c = m− 1.
– Com m e a escolhidos desta forma, obtemos
cada inteiro 1, 2, . . . ,m− 1 exatamente uma vez
em cada ciclo.
– Os valores para a que produzem bons geradores
sa˜o identificados atrave´s de testes. Para m =
231− 1, dois valores para a teˆm sido largamente
utilizados. Sa˜o eles a = 75 e a = 630.360.016.
• Para m primo, na˜o dispomos do mecanismo de over-
flow para evitar a operac¸a˜o de divisa˜o.
– Um me´todo proposto para evitar a divisa˜o di-
reta e´ chamado “divisa˜o simulada”.
– Sejam m = 2w − q, X ′i = (aXi−1) (mod 2w)
e k = 
aXi−1/2w� (que podem ser obtidos sem
divisa˜o).
aXi−1 = X ′i + 2
wk
aXi−1 − kq = X ′i + 2wk−kq = X ′i + mk
(aXi−1−mk) (mod m) = (X ′i+kq) (mod m)
(aXi−1) (mod m) = (X ′i + kq) (mod m)
24
– Como q < 2w−1, enta˜o 2m = 2w+1 − 2q > 2w
– X ′i + kq < 2m...
Xi =
{
X ′i + kq, se X
′
i + kq < m
X ′i + kq −m, se X ′i + kq ≥ m
– Ex.: m = 231 − 1, a = 75, Xi−1 = 7. Logo
X ′i = 7
6 (mod 231) = 117649, k = 0.
30 Geradores Tausworthe
• Os geradores Tausworthe operam diretamente sobre
os bits.
• Uma sequeˆncia de d´ıgitos bina´rios e´ definida pela re-
correˆncia
bi = (c1bi−1 + c2bi−2 + . . . + cqbi−q) (mod 2),
onde c1, . . . , cq sa˜o constantes bina´rias.
• Neste caso, um ciclo e´ definido como uma sequeˆncia
de valores bina´rios que se repetem continuamente.
Portanto, como os q bits anteriores sa˜o utilizados, o
per´ıodo pode chegar a 2q−1 (uma sequeˆncia de zeros
e´ exclu´ıda, pois gera outra sequeˆncia de zeros).
• Praticamente todos os geradores Tausworthe propos-
tos sa˜o da forma
bi = (bi−r + bi−q) (mod 2),
para inteiros r e q satisfazendo 0 < r < q.
– Note que a soma de varia´veis bina´ria mo´dulo 2 e´
o mesmo que a operac¸a˜o “ou exclusivo”, ou seja,
bi = 0 se bi−r = bi−q, e bi = 1 se bi−r �= bi−q.
– Ex.: r = 3, q = 5, b1 = b2 = . . . = b5 =
1. Assim, para i ≥ 6, bi e´ o ou exclusivo
de bi−3 e bi−5. Os primeiros bi’s sera˜o 11111
00011011101010000100101100-111110.. Note a
repetic¸a˜o apo´s 31 bits.
• Para gerar nu´meros entre 0 e 1, podemos particionar
a sequeˆncia em grupos de w bits, e dividir por 2w
cada nu´mero representado por um grupo de bits.
• Geradores Tausworthe oferecem algumas vantagens
potenciais com relac¸a˜o aos Congruente Lineares.
– Sa˜o independentes do computador utilizado (ta-
manho da word).
– Oferecem per´ıodos de qualquer tamanho.
– Pore´m, testes emp´ıricos da qualidade estat´ıstica
dos nu´mero gerados podem ser inconclusivos.
n=32; r=3; q=5; b=ones(1,n);
for i=q+1:n; b(i)=mod(b(i-r)+b(i-q),2); end; b,
w=4; x=zeros(1,n/w);
for i=1:n/w,
for j=1:w, x(i)=x(i)+b(4*(i-1)+j)*2^(w-j); end;
end; x
31 Combinando geradores
• E´ poss´ıvel combinar dois geradores para produzir um
gerador “melhor”. Algumas formas sa˜o:
• Adicionando nu´meros aleato´rios obtidos por dois ou
mais geradores.
– Se Xi e Yi sa˜o duas sequeˆncia de nu´meros
aleato´rios no intervalo de 0 a m− 1, eles podem
ser combinados para produzir Wi = (Xi + Yi)
(mod m).
– Se estas sequeˆncias teˆm per´ıodos diferentes e sa˜o
obtidos por algoritmos diferentes, isto pode me-
lhorar consideravelmente o per´ıodo e a aleatori-
edade.
• Ou-Exclusivo dos nu´meros aleato´rios obtidos por dois
ou mais geradores. Aqui a adic¸a˜o proposta anterior-
mente e´ substitu´ıda por uma operac¸a˜o ou-exclusivo
bit-a-bit.
• Shuffle.
– Utiliza uma sequeˆncia como ı´ndice para decidir
qual nu´mero de uma segunda sequeˆncia deve ser
retornado.
– Nesta abordagem na˜o e´ fa´cil saltar sub-
sequeˆncias longas (com o objetivo de produzir
subsequeˆncias independentes).
31.1 Selec¸a˜o de sementes
• Uma escolha ruim da semente pode gerar simulac¸o˜es
com resultados falsos. Esta escolhadepende do gera-
dor utilizado. Verifique as restric¸o˜es do gerador.
Na˜o utilizar zero. Geradores multiplicativos e
Tausworthe na˜o permitem semente zero.
Evitar valores pares. Geradores multiplicativos com
m = 2w exigem sementes ı´mpares.
Na˜o subdividir uma sequeˆncia. Quando existe cor-
relac¸a˜o entre os nu´meros gerados, na˜o utilizar
uma mesma sequeˆncia para gerar va´rias varia´veis
aleato´rias. Ex.: x1 tempo entre chegadas, x2 tempo
de atendimento... Na du´vida, divida o ciclo em sub-
sequeˆncias disjuntas.
n=10000; m=2^31; a=5; b=1; x=zeros(1,n);
x(1)=10;
for i=2:n; x(i)=mod(a*x(i-1)+b,m); end;
x=x/m; hist(x); figure; autocorr(x)
Na˜o utilize sequeˆncias sobrepostas. Se a semente
das sequeˆncia utilizadas para gerar duas v.a. se so-
brepo˜em durante a simulac¸a˜o, estas duas v.a. tera˜o
correlac¸a˜o. Fac¸a um programa para determinar as
sementes que subdividem o ciclo em sequeˆncias di-
juntas de mesmo tamanho.
25
Na˜o e´ necessa´rio determinar semente em
replicac¸o˜es sucessivas. A semente deixada
pela u´ltima replicac¸a˜o pode ser utilizada.
Na˜o utilize sementes aleato´rias. Por exemplo, o
relo´gio do sistema. Problemas: (i) impede a re-
plicac¸a˜o da simulac¸a˜o (ex.: depurac¸a˜o), e (ii) na˜o
garante sequeˆncias na˜o sobrepostas. Tambe´m na˜o
use sementes produzidas por outros geradores.
Parte IX
Noc¸o˜es ba´sicas em
teoria dos nu´meros
32 Preliminares: Func¸o˜es Inteiras
e mod
• Se x e´ um nu´mero real, denotamos
– 
x� = o maior inteiro menor ou igual a x.
(“o piso de x”)
– �x
 = o menor inteiro maior ou igual a x.
(“o teto de x”)
• Ex.: 
1/2� = 0, �1/2
 = 1, 
−1/2� = −1 (na˜o zero!).
• Algumas propriedades:
– �x
 = 
x� se e somente se x e´ inteiro.
– �x
 = 
x�+ 1 se e somente se x NA˜O e´ inteiro.
– 
−x� = −�x
– x− 1 < 
x� ≤ x ≤ �x
 < x + 1
33 Divisibilidade
• Dizemos que “m divide n” (ou “n e´ divis´ıvel por m”)
se m > 0 e a raza˜o n/m e´ um inteiro. Denotamos
m \ n ⇔ m > 0 e n = mk para algum inteiro k.
– A relac¸a˜o “n e´ mu´ltiplo de m” e´ ideˆntica, exceto
pelo fato de que m na˜o precisa ser positivo.
– Ex.: O u´nico mu´ltiplo de 0 e´ o pro´prio 0. Todo
inteiro e´ mu´ltiplo de -1, mas nenhum inteiro e´
divis´ıvel por -1 (por definic¸a˜o).
• O “ma´ximo divisor comum” (mdc) de dois inteiros m
e n e´ o maior inteiro que divide ambos:
mdc(m,n) = max{k | k \m e k \ n}.
– Ex.: mdc(12, 18) = 6. Este conceito e´ familiar,
visto que usamos em simplificac¸a˜o de frac¸o˜es:
12/18 = (6 ∗ 2)/(6 ∗ 3) = 2/3.
• O “mı´nimo mu´ltiplo comum” (mmc) de dois inteiros
POSITIVOS m e n e´ o menor inteiro POSITIVO que
e´ mu´ltiplo de ambos:
mmc(m,n) = min{k | k > 0, m \ k e n \ k}.
– Ex.: mmc(12, 18) = 36. Utilizamos este con-
ceito para determinar o mı´nimo denominador
comum de frac¸o˜es:
7
12
+
1
18
=
21
36
+
2
36
=
23
36
.
• O mdc e´ facilmente calculado atrave´s do algoritmo
de Euclides (desenvolvido a 2300 anos!).
– Para calcular mdc(m,n), com 0 ≤ m < n, utili-
zamos a recorreˆncia:
mdc(0, n) = n
mdc(m,n) = mdc(n mod m,m), para m > 0.
– Ex.: mdc(12, 18) = mdc(6, 12) = mdc(0, 6) = 6.
– Prova: qualquer nu´mero que divide m e n
tambe´m divide n mod m = n− 
n/m�m.
• O algoritmo de Euclides tambe´m permite obter intei-
ros m′ e n′ tal que
m′m + n′n = mdc(m,n).
– Se m = 0, enta˜o retorne m′ = 0 e n′ = 1. Caso
contra´rio, retorne m′ = m − 
n/m�r e n′ = r,
onde r = n mod m e rr + mm = mdc(r,m).
– Ex.: obter m′ e n′ tal que m′12 + n′18 =
mdc(12, 18). Utilizando o exemplo anterior, va-
mos comec¸ar com mdc(0, 6) = 0 ∗ 0 + 1 ∗ 6 (ou
seja, m′ = 0 e n′ = 1). Agora vamos obter
m′ e n′ tal que mdc(6, 12) = m′ ∗ 6 + n′ ∗ 12.
Para isso, utilizamos r = 12 mod 6 = 0 e
r ∗ 0 + m ∗ 6 = mdc(0, 6), ou seja, r = 0 (o
m′ anterior) e m = 1 (o n′ anterior). Portanto,
m′ = 1 + 2 ∗ 0 = 1 e n′ = 0. Continuando,
obtemos mdc(12, 18) = (−1)12 + 1 ∗ 18.
– Prova: mdc(m,n) = mdc(r,m) = rr + mm =
r(n− 
n/m�m) + mm = (m− 
n/m�r)m + rn.
34 Nu´meros primos
• Um nu´mero inteiro positivo p e´ chamado “primo” se
ele tem apenas dois divisores: 1 e p.
– Por convenc¸a˜o o nu´mero 1 na˜o e´ primo, portanto
os primeiros primos sa˜o 2,3,5,7, 11,13,17,19,
23,29,31,37, 41..
– Nu´meros com treˆs ou mais divisores sa˜o chama-
dos de “compostos”.
– Todo inteiro maior que 1 ou e´ primo ou com-
posto, nunca ambos.
26
• A importaˆncia dos nu´meros primos vem do fato de
todo inteiro n > 1 poder ser escrito como um produto
de nu´meros primos,
n = p1 . . . pm, onde p1, . . . , pm sa˜o primos.
– Prova: por induc¸a˜o, assuma que esta proprie-
dade vale para todo inteiro maior que 1 e menor
que n. Se n na˜o for primo, enta˜o ele tem um
divisor 1 < n1 < n. Assim, podemos escrever
n = n1n2, com 1 < n2 < n. Mas por hipo´tese,
n1 e n2 podem ser escritos como produto de pri-
mos. Caso base: 4 = 2 ∗ 2.
• O Teorema Fundamental da Aritme´tica estabelece
que existe apenas uma forma de escrever um inteiro
n > 1 como um produto de primos em ordem decres-
cente.
– Ex.: 12 = 22 × 3, 18 = 2× 32.
– Enta˜o, podemos escrever,
n = 2n2×3n3×5n5×7n7 . . . , onde cada np ∈ N.
– Assim, para multiplicar dois nu´meros basta so-
mar os expoentes dos fatores primos,
n = mk ⇔ np = mp + kp, para todo primo p.
– Ex.: 12× 18 = 22+1 × 31+2 = 216.
– Isto implica que,
m \ n ⇔ mp ≤ np, para todo primo p.
– E consequentemente,
k = mmc(m,n) ⇔ kp = max{mp, np}, ∀p.
k = mdc (m,n) ⇔ kp = min{mp, np}, ∀p.
– Ex.: mmc(12, 18) = 2max{2,1}+3max{1,2} = 22×
32 = 36, mdc(12, 18) = 2min{2,1} + 3min{1,2} =
21 × 31 = 6.
– Como consequeˆncia da fatorac¸a˜o u´nica, se um
primo p divide m × n, enta˜o ele divide m ou n
(ou ambos). Note que isso na˜o necessariamente
verdadeiro para nu´meros compostos. Ex.: 4 di-
vide 60 = 6× 10, mas na˜o divide nem 6 nem 10
(os fatores primos 2× 2 foram separados).
35 Nu´meros primos entre si
• Dizemos que dois inteiros m e n sa˜o “primos entre
si” quando eles na˜o teˆm fatores primos em comum,
ou seja, mdc(m,n) = 1.
– Ex.: quando simplificamos uma frac¸a˜o, esta-
mos reduzindo o numerador e o denominador
a nu´meros primos entre si. 12/18 = (6×2)/(6×
3) = 2/3 (na˜o temos como simplificar mais, pois
2 e 3 sa˜o primos entre si). De modo geral temos
que os nu´meros m/mdc(m,n) e n/mdc(m,n)
sa˜o primos entre si.
• Pela definic¸a˜o, temos que dois inteiros m e n sa˜o pri-
mos entre si se e somente se min{mp, np} = 0 para
todo primo p.
– Esta condic¸a˜o pode ser escrita como mp×np = 0
para todo primo p.
– Com isso, podemos provar que k e m sa˜o primos
entre si e k e n sa˜o primos entre si se e somente
se k e m× n sa˜o primos entre si.
– Prova: note que kp ×mp = 0 e kp × np = 0 se e
somente se kp × (mp + np) = 0.
36 Operador “MOD”
• Dados dois inteiros n e m �= 0, denotamos por n mod
m o resto da divisa˜o de n por m.
– Como 
n/m� e´ o quociente desta divisa˜o, temos
que
n = m× 
n/m�+ n mod m.
– Portanto,
n mod m = n−m× 
n/m�.
– Ex.: 5 mod 3 = 5− 3× 
5/3� = 2.
5 mod −3 = 5− (−3)× 
−5/3� = −1.
−5 mod 3 = −5− 3× 
−5/3� = 1.
−5 mod −3 = −5− (−3)× 
(−5)/(−3)� = −2.
• Chamamos o nu´mero apo´s o “mod” de “mo´dulo”.
• Pela definic¸a˜o, temos que
0 ≤ n mod m < m, se m > 0.
0 ≥ n mod m > m, se m < 0.
• O operador “mod” e´ distributivo em relac¸a˜o a` mul-
tiplicac¸a˜o:
d× (n mod m) = (dn) mod (dm).
– Prova: d× (n mod m) = d× (n−m×
n/m�) =
dn− dm× 
(dn)/(dm)� = (dn) mod (dm)
• Em muitos casos o operador de congrueˆncia (“≡”)
simplifica a notac¸a˜o. Ele e´ definido como
a ≡ b (mod m) ⇔ a mod m = b mod m.
– Ou seja, este operador indica que a e b produzem
o mesmo resto quando divididos por m.
– Este operador e´ lido “a e´ congruente a b mo´dulo
m”.
– Ex.: 9 ≡ −16 (mod 5), pois 9 mod 5 = 4 e
−16 mod 5 = 4.
• A operac¸a˜o de congrueˆncia pode tambe´m ser definida
como
a ≡ b (mod m) ⇔ a− b e´ mu´ltiplode m.
27
– Prova: como a = k ×m + a mod m para algum
inteiro k, e b = q × m + b mod m para algum
inteiro q, enta˜o a−b = (k−q)m (pois a mod m =
b mod m).
– Esta relac¸a˜o facilita a determinac¸a˜o de con-
grueˆncias. Ex.: 9 ≡ −16 (mod 5), pois 9 −
(−16) = 25 e´ mu´ltiplo de 5.
• A operac¸a˜o de congrueˆncia e´ uma “relac¸a˜o de equi-
valeˆncia”, ou seja, satisfaz as leis
(i) a ≡ a (reflexiva)
(ii) a ≡ b ⇒ b ≡ a (sime´trica)
(iii) a ≡ b e b ≡ c ⇒ a ≡ c (transitiva)
– Prova: (iii) se a mod m = b mod m e b mod
m = c mod m, enta˜o a mod m = c mod m.
• Podemos somar e subtrair elementos congruentes sem
perder congrueˆncia:
a ≡ b e c ≡ d ⇒ a + c ≡ b + d (mod m)
a ≡ b e c ≡ d ⇒ a− c ≡ b− d (mod m)
– Prova: se a − b e c − d sa˜o mu´ltiplos de m,
enta˜o (a + c) − (b + d) = (a − b) + (c − d) e
(a− c)− (b− d) = (a− b)− (c− d) tambe´m sa˜o
mu´ltiplos de m.
• O mesmo vale para multiplicac¸a˜o:
a ≡ b e c ≡ d ⇒ ac ≡ bd (mod m).
– Prova: ac− bd = (a − b)c + b(c − d) e´ mu´ltiplo
de m, pois a− b e c− d sa˜o mu´ltiplos de m.
– Uma consequeˆncia direta desta propriedade e´
a ≡ b ⇒ an ≡ bn (mod m), para n ∈ N.
– Note que ac ≡ bd (mod m) na˜o implica em
a ≡ b (mod m). Ex.: 3 × 2 ≡ 5 × 2 (mod 4)
mas 3 na˜o e´ congruente a 5 (mod 4).
• Podemos multiplicar/dividir a congrueˆncia e o
mo´dulo por uma constante na˜o nula:
ad ≡ bd (mod md) ⇔ a ≡ b (mod m), para d �= 0.
– Prova: (ad) mod (md) = a mod m e (bd) mod
(md) = b mod m.
• Podemos dividir apenas o mo´dulo:
a ≡ b (mod md) ⇒ a ≡ b (mod m).
– Prova: se a − b e´ mu´ltiplo de md, tambe´m e´
mu´ltiplo de m.
• A lei abaixo permite dividir a congrueˆncia modifi-
cando o mo´dulo o mı´nimo poss´ıvel:
ad ≡ bd (mod m) ⇔ a ≡ b
(
mod
m
mdc(d,m)
)
.
– Prova: pelo algoritmo de Euclides, existem in-
teiros d′ e m′ tal que d′d + m′m = mdc(d,m),
logo d′d ≡ mdc(d,m) (mod m). Utilizando
a ≡ a, temos que ad′d ≡ a × mdc(d,m). O
mesmo vale para bd′d ≡ b × mdc(d,m). Multi-
plicando ambos os lados de ad ≡ bd por d′ ob-
temos por transitividade que a × mdc(d,m) ≡
b×mdc(d,m) (mod m). Agora basta dividir a
congrueˆncia e o mo´dulo por mdc(d,m).
– Um caso particular importante ocorre quando d
e m sa˜o primos entre si:
ad ≡ bd ⇔ a ≡ b (mod m).
– Ex.: se m na˜o e´ mu´ltiplo de 5, temos que 15 ≡
35 (mod m) pode ser simplificado para 3 ≡ 7
(mod m).
• Se a ≡ b com relac¸a˜o a dois mo´dulos, podemos com-
binar os modulos da seguinte forma:
a ≡ b (mod m) e a ≡ b (mod n)
⇔ a ≡ b (mod mmc(m,n)).
– Prova: a−b e´ mu´ltiplo de m e n se e somente se
e´ mu´ltiplo de mmc(m,n) (princ´ıpio da fatorac¸a˜o
u´nica).
– Portanto, quando m e n sa˜o primos entre si,
a ≡ b (mod m) e a ≡ b (mod n)
⇔ a ≡ b (mod mn).
– Se m tem fatorac¸a˜o em primos 2m23m35m5 . . .,
a ≡ b (mod m) ⇔ a ≡ b (mod pmp), ∀ primo p.
37 Aplicac¸a˜o na gerac¸a˜o de
nu´mero aleato´rios
• Seja φ(m) o nu´mero de valores inteiros entre 0 e m−1
que sa˜o primos com relac¸a˜o a m.
• Lema A. Se p e´ primo, enta˜o φ(pe) = pe−1(p − 1),
onde e e´ um inteiro positivo.
– Prova: por induc¸a˜o em e. Hipote´se: vale para
todo expoente menor que e.
Caso base: vale para e = 1, pois todos os p− 1
nu´meros menores que p sa˜o primos em relac¸a˜o
a` p.
Para cada k = 1, . . . , e − 1, devemos remover
do intervalo entre pe−1 e pe todos os nu´meros
da forma d × pk, onde pe−k−1 ≤ d < pe−k e
mdc(d, p) = 1. Por hipote´se, existe φ(pk) valo-
res para d em cada um destes intervalos. Como
todos os primos em relac¸a˜o a` pe−k sa˜o primos em
relac¸a˜o a` pe, para cada nu´mero removido no in-
tervalo entre pe−1 e pe, um novo nu´mero menor
que pe−1 e´ contabilizado como primo em relac¸a˜o
a` pe. Assim, φ(pe) = pe − pe−1 = pe−1(p− 1).
28
• Teorema de Euler. Para todo inteiro positivo m,
e para qualquer a primo em relac¸a˜o a` m, temos que
aφ(m) ≡ 1 (mod m).
– Prova: Sejam d1, . . . , dφ(m) os nu´meros primos
em relac¸a˜o a` m.
Como a e di sa˜o primos em relac¸a˜o a` m, temos
que a × di e´ primo em relac¸a˜o a` m (ou seja,
mdc(adi,m) = 1).
Vamos agora mostrar que adi mod m e´ primo
em relac¸a˜o a` m (ou seja, adi mod m e´ igual a
algum dj). Se adi < m, isto decorre de adi mod
m = adi. Caso contra´rio, pelo algoritmo de Eu-
clides, mdc(adi mod m,m) = mdc(adi,m) = 1.
Os valores adi mod m sa˜o distintos, pois se
adi ≡ adj , para algum par i �= j, ter´ıamos
di ≡ dj pois a pode ser cancelado por ser primo
em relac¸a˜o a` m (contradic¸a˜o!).
Portanto existe uma bijec¸a˜o entre os valores
adi mod m e os valores di. Assim,
(ad1) . . . (adφ(m)) ≡ d1 . . . dφ(m).
Como os di’s podem ser cancelados (pois sa˜o
primos em relac¸a˜o a m), obtemos aφ(m) ≡ 1.
• Vamos considerar geradores de nu´meros “aleato´rios”
congruente lineares multiplicativos, definidos pela re-
correˆncia:
xn = (a× xn−1) mod m.
– Os paraˆmetros deste gerador sa˜o a (multiplica-
dor), m (mo´dulo) e x0 (semente).
– Este gerador e´ o mais popular e o mais bem
compreendido.
– Resolvendo a recorreˆncia obtemos
xn = (anx0) mod m.
– O valor zero na˜o pode ser gerado, pois caso
contra´rio toda a sequeˆncia seguinte seria nula.
Portanto, este gerador ciclos com no ma´ximo
m − 1 elementos distintos (ou seja, o per´ıodo e´
no ma´ximo m− 1).
• Se d e´ um divisor de m e xn, enta˜o todos os elementos
seguintes sera˜o mu´ltiplos de d, pois dk1 mod dk2 =
d(k1 mod k2).
– Para evitar esta propriedade indesejada, xn de-
veria ser primo em relac¸a˜o a` m para todo n.
– Isto limita o per´ıodo em φ(m).
– Se m e´ primo, podemos ter um per´ıodo igual a
m− 1 (caso base do Lema A).
• Lemma B. Considere as se´ries:
Xn = (aXn−1 + c) mod md,
Yn = [(a mod m)(Yn−1 mod m)+(c mod m)] mod m,
com Y0 = X0 mod m. Enta˜o, Yn = Xn mod m para
n ≥ 0.
– Prova: induc¸a˜o em n. Caso base, Y0 = X0 mod
m. Hipo´tese: vale para ı´ndices menores que n.
Aplicando a hipo´tese:
Yn = [(a mod m)(Xn−1 mod m)+(c mod m)] mod m
Xn = (aXn−1 + c) mod md = aXn−1+ c− qmd,
para determinado inteiro q. Portanto,
Xn ≡ aXn−1 + c (mod m).
aXn−1 + c = (qam + a mod m)(qXm +
Xn−1 mod m) + (qcm + c mod m), para de-
terminados inteiros qa, qX e qc. Portanto,
aXn−1 + c ≡ (a mod m)(Xn−1 mod m) +
(c mod m) (mod m).
Com isso concluimos que Yn ≡ Xn (mod m).
29