Aula04-Teoria das Congruencias.pptx

Prévia do material em texto

11/18/13	
  
1	
  
Aritmética	
  Modular	
  
Matemá,ca	
  Discreta	
  2	
  
Rosen	
  (7th	
  ed.)	
  –	
  (Cap.	
  4)	
  
Rosen	
  -­‐	
  “Elementary	
  Number	
  Theory”	
  (Cap.	
  3)	
  	
  
Burton	
  -­‐	
  “Elementary	
  Number	
  Theory”	
  (Cap.	
  4)	
  
André	
  Câmara	
  
Teoria	
  das	
  congruências	
  
•  Outra	
  aproximação	
  a	
  questões	
  de	
  divisibilidade	
  
•  Também	
  conhecida	
  como	
  aritméCca	
  dos	
  restos	
  
•  Desenvolvida	
  pelo	
  gênio	
  alemão	
  Carl	
  Frederic	
  
Gauss	
  
•  "MathemaCcs	
  is	
  the	
  Queen	
  of	
  the	
  Sciences,	
  
and	
  the	
  theory	
  of	
  numbers	
  is	
  the	
  Queen	
  of	
  
MathemaCcs”	
  
Teoria	
  das	
  congruências	
  Propriedades	
  básicas	
  
•  Seja	
  n	
  um	
  inteiro	
  posi,vo.	
  Dois	
  inteiros	
  a	
  e	
  b	
  são	
  
ditos	
  congruentes	
  módulo	
  n	
  simbolizado	
  por:	
  
	
  a	
  ≡	
  b	
  (mod	
  n)	
  
	
  	
  Se	
  n	
  divide	
  a	
  diferença	
  a-­‐b	
  	
  ⇒	
  n|(a-­‐b)	
  	
  
	
  i.e.,	
  a-­‐b	
  =	
  k·∙n,	
  para	
  algum	
  inteiro	
  inteiro	
  k	
  
•  a	
  ≡	
  b	
  (mod	
  n)	
  se	
  somente	
  se	
  a	
  mod	
  m	
  =	
  b	
  mod	
  
m.	
  	
  
•  7	
  ≡	
  2	
  (mod	
  5)	
  
Exemplo	
  
•  Um	
  exemplo	
  simples	
  do	
  uso	
  da	
  aritmé,ca	
  modular	
  é	
  o	
  seu	
  
uso	
  no	
  relógio	
  de	
  12	
  horas	
  
•  mod	
  12	
  
•  9:00+4h	
  =>	
  13	
  ≡	
  1	
  (mod	
  12)	
  
•  12:00+21	
  =>	
  33	
  ≡	
  9	
  (mod	
  12)	
  
Exemplo:	
  
•  Considere	
  n=7	
  
	
  3	
  ≡	
  24	
  (mod	
  7) 	
  3-­‐24	
  =	
  -­‐21	
  	
  	
  	
  	
  	
  ∴	
  7|(-­‐21)	
  
	
  24	
  ≡	
  3	
  (mod	
  7) 	
  24-­‐3	
  =	
  21	
  	
  	
  	
  	
  	
  	
  ∴	
  7|21	
  
	
  -­‐31	
  ≡	
  11	
  (mod	
  7) 	
  -­‐31-­‐11	
  =	
  -­‐42	
  	
  ∴	
  7|42	
  
	
  	
  19	
  ≡	
  -­‐2	
  (mod	
  7)	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
   	
  19-­‐(-­‐2)=21	
  	
  	
  	
  	
  ∴	
  7|21	
  
	
  
•  Se	
  n∤(a-­‐b)	
  dizemos	
  que	
  a	
  e	
  b	
  são	
  incongruentes.	
  
•  Ex.:	
  
	
  25	
  ≢	
  12	
  mod	
  7 	
  25-­‐12	
  =	
  13	
  ∴	
  7∤13	
  
Observações	
  
•  Devemos	
  notar	
  que	
  dois	
  inteiros	
  quaisquer	
  são	
  
congruentes	
  módulo	
  1	
  
•  1	
  divide	
  qualquer	
  inteiro	
  
•  Por	
  esse	
  mo,vo,	
  é	
  prá,ca	
  comum	
  assumir	
  	
  
n	
  >	
  1	
  
•  Dois	
  inteiros	
  são	
  congruentes	
  módulo	
  2	
  se	
  
ambos	
  forem	
  ímpares	
  ou	
  pares	
  
•  42	
  ≡	
  4	
  (mod	
  2)	
  	
  ⇒ 2|38	
  
•  35	
  ≡	
  19	
  (mod	
  2)	
  ⇒	
  2|16	
  
11/18/13	
  
2	
  
Relacionando	
  com	
  Teorema	
  da	
  divisibilidade	
  dos	
  inteiros	
  
a	
  =	
  qn	
  +	
  r,	
  0	
  ≤	
  r	
  ≤	
  n	
  	
  
	
  
Pela	
  definição	
  da	
  teoria	
  das	
  congruências,	
  temos:	
  
a	
  ≡	
  r	
  (mod	
  n)	
  
	
  
Temos	
  então	
  n	
  escolhas	
  dis,ntas	
  de	
  r:	
  0,1,2,...	
  n-­‐1	
  
	
  Menores	
  resíduos	
  não-­‐nega,vos	
  módulo	
  n	
  
	
  
Note	
  que	
  a	
  ≡	
  0	
  (mod	
  n)	
  ,	
  SSE	
  n|a	
  à	
  resto	
  =	
  0	
  
	
  
Teorema	
  
•  Seja	
  n	
  >	
  1	
  fixo	
  e	
  a,b,c,d	
  	
  inteiros	
  arbitrários,	
  então:	
  
a)  a	
  ≡	
  a	
  (mod	
  n)	
  	
  (reflexiva)	
  
b)  Se	
  a	
  ≡	
  b	
  (mod	
  n)	
  então	
  b	
  ≡	
  a	
  (mod	
  n)	
  (simétrica)	
  
c)  Se	
  a	
  ≡	
  b	
  (mod	
  n)	
  e	
  b	
  ≡	
  c	
  (mod	
  n),	
  	
  
então	
  a	
  ≡	
  c	
  (mod	
  n)	
  (transiCva)	
  
d)  Se	
  a	
  ≡	
  b	
  (mod	
  n)	
  e	
  c	
  ≡	
  d	
  (mod	
  n)	
  então	
  	
  
a+c	
  ≡	
  b+d	
  (mod	
  n)	
  e	
  ac	
  ≡	
  bd	
  (mod	
  n)	
  
e)  Se	
  a	
  ≡	
  b	
  (mod	
  n),	
  então	
  a	
  +	
  c	
  ≡	
  b	
  +	
  c	
  (mod	
  n)	
  e	
  ac	
  ≡	
  
bc	
  (mod	
  n).	
  	
  
f)  Se	
  a	
  ≡	
  b	
  (mod	
  n),	
  então	
  ak	
  ≡	
  bk	
  (mod	
  n)	
  para	
  
qualquer	
  inteiro	
  posi,vo	
  k.	
  
Provando	
  (a),	
  (b),	
  (c)	
  
a)  Para	
  um	
  inteiro	
  a,	
  temos	
  a-­‐a	
  =	
  0·∙n	
  	
  então	
  	
  
a	
  ≡	
  a	
  (mod	
  n)	
  
b)  Se	
  a	
  ≡	
  b	
  (mod	
  n),	
  então	
  a-­‐b	
  =	
  kn	
  
b-­‐a	
  =	
  (-­‐k)n	
  e	
  –k	
  também	
  é	
  um	
  inteiro,	
  temos	
  	
  
b	
  ≡	
  a	
  (mod	
  n)	
  
c)  Se	
  a	
  ≡	
  b	
  (mod	
  n)	
  e	
  b	
  ≡	
  c	
  (mod	
  n),	
  então	
  existem	
  h	
  e	
  k	
  
sa,sfazendo:	
  
	
  
a-­‐b	
  =	
  h·∙n	
  e	
  b-­‐c	
  =	
  k·∙n	
  
	
  
Fazendo	
  a	
  –	
  c	
  =	
  (h·∙n	
  +	
  b)	
  –	
  (b	
  -­‐	
  k·∙n)	
  =	
  (h	
  +	
  k)n	
  
Dessa	
  forma:	
  a	
  ≡	
  c	
  (mod	
  n)	
  
	
  
Provando	
  (d)	
  
•  Se	
  a	
  ≡	
  b	
  (mod	
  n)	
  e	
  c	
  ≡	
  d	
  (mod	
  n)	
  então	
  	
  
a+c	
  ≡	
  b+d	
  (mod	
  n)	
  e	
  ac	
  ≡	
  bd	
  (mod	
  n)	
  
•  Se	
  a	
  ≡	
  b	
  (mod	
  n),	
  então	
  (a-­‐b)=k1n	
  e	
  	
  
se	
  c	
  ≡	
  d	
  (mod	
  n),	
  então	
  (c-­‐d)=k2n	
  
•  Somando-­‐se	
  as	
  equações	
  temos:	
  
(a-­‐b)+(c-­‐d)=(a+c)-­‐(b+d)=(k1+k2)n	
  
a+c	
  ≡	
  b+d	
  (mod	
  n)	
  
Provando	
  (d)	
  (cont.)	
  
•  Se	
  a	
  ≡	
  b	
  (mod	
  n)	
  e	
  c	
  ≡	
  d	
  (mod	
  n)	
  então	
  	
  
a+c	
  ≡	
  b+d	
  (mod	
  n)	
  e	
  ac	
  ≡	
  bd	
  (mod	
  n)	
  
•  Se	
  a	
  ≡	
  b	
  (mod	
  n),	
  então	
  (a-­‐b)=k1n	
  e	
  	
  
se	
  c	
  ≡	
  d	
  (mod	
  n),	
  então	
  (c-­‐d)=k2n	
  
	
  
ac	
  =	
  (k1n+b)(k2n+d)=bd+(bk2+dk1+k1k2n)n	
  
	
  
ac	
  ≡	
  bd	
  (mod	
  n)	
  
Inteiro	
  (k3)	
  
Provando	
  (e)	
  
•  Se	
  a	
  ≡	
  b	
  (mod	
  n),	
  então	
  a	
  +	
  c	
  ≡	
  b	
  +	
  c	
  (mod	
  n)	
  e	
  	
  
ac	
  ≡	
  bc	
  (mod	
  n).	
  
•  Já	
  vimos	
  que	
  	
  
•  Se	
  a	
  ≡	
  b	
  (mod	
  n)	
  e	
  c	
  ≡	
  d	
  (mod	
  n)	
  então	
  	
  
a+c	
  ≡	
  b+d	
  (mod	
  n)	
  e	
  ac	
  ≡	
  bd	
  (mod	
  n)	
  
E	
  
•  c	
  ≡	
  c	
  (mod	
  n)	
  
•  Portanto,	
  	
  	
  
•  Se	
  a	
  ≡	
  b	
  (mod	
  n),	
  e	
  c	
  ≡	
  c	
  (mod	
  n),	
  então	
  	
  
a	
  +	
  c	
  ≡	
  b	
  +	
  c	
  (mod	
  n)	
  e	
  ac	
  ≡	
  bc	
  (mod	
  n)	
  
(d)	
  
(a)	
  
11/18/13	
  
3	
  
Provando	
  (f)	
  
•  Se	
  a	
  ≡	
  b	
  (mod	
  n),	
  então	
  ak	
  ≡	
  bk	
  (mod	
  n)	
  para	
  
qualquer	
  inteiro	
  posi,vo	
  k.	
  
•  Prova	
  por	
  indução	
  
•  k=1	
  à	
  a	
  ≡	
  b	
  (mod	
  n)	
  
•  Para	
  um	
  k	
  fixo	
  à	
  ak	
  ≡	
  bk	
  (mod	
  n)	
  
•  Usando	
  (d),	
  temos	
  que	
  	
  
a	
  ≡	
  b	
  (mod	
  n)	
  e	
  ak	
  ≡	
  bk	
  (mod	
  n)	
  	
  à	
  aak	
  ≡	
  bbk	
  (mod	
  n)	
  	
  
	
  	
  ak+1	
  ≡	
  bk+1	
  (mod	
  n)	
  
Que	
  é	
  igual	
  ao	
  passo	
  da	
  indução	
  k+1	
  
Classes	
  de	
  congruência	
  
•  Observe	
  que	
  a	
  relação	
  de	
  congruência	
  é	
  uma	
  
relação	
  de	
  equivalência	
  
•  De	
  modo	
  que	
  o	
  conjunto	
  dos	
  inteiros	
  é	
  dividido	
  
em	
  m	
  diferentes	
  conjuntos,	
  chamados	
  declasses	
  
de	
  congruência	
  módulo	
  m	
  
•  Exemplo:	
  modulo	
  4	
  
Exemplo	
  
•  Um	
  exemplo	
  de	
  como	
  as	
  congruências	
  podem	
  
ser	
  úteis	
  em	
  certos	
  ,pos	
  de	
  computação:	
  
Encontrar	
  o	
  resto	
  da	
  divisão	
  de	
  (1!+2!+3!+...+	
  
100!)	
  por	
  12	
  
	
  
Exemplo	
  	
  
•  Encontrar	
  o	
  resto	
  da	
  divisão	
  de	
  (1!+2!+3!+...+	
  100!)	
  por	
  12 	
  	
  
•  Observe	
  que	
  4!	
  =	
  24	
  ≡	
  0	
  (mod	
  12)	
  
•  24	
  é	
  divisível	
  por	
  12,	
  i.e.	
  o	
  resto	
  é	
  zero	
  
Com	
  isso,	
  podemos	
  dizer	
  que	
  (k>4):	
  
k!	
  =	
  4!·∙5·∙6·∙7·∙...	
  ·∙k	
  ≡	
  0·∙5·∙6·∙7·∙...	
  ·∙k	
  ≡	
  0	
  (mod	
  12)	
  
	
  
	
  
k!	
  ≡	
  0	
  (mod	
  12)	
  para	
  k	
  ≥	
  4	
  
1!+2!+3!+4!+...+100!	
  	
  
≡	
  1!+2!+3!+0+0+...+0	
  ≡9	
  (mod	
  12)	
  
c	
   c	
  
Múl,plos	
  de	
  24,	
  resto	
  0	
  
Exemplo	
  
•  Provar	
  que	
  41|(220-­‐1)	
  
•  Iniciar	
  procurando	
  a	
  relação	
  de	
  41	
  com	
  alguma	
  
potência	
  de	
  2.	
  Exemplo:	
  
•  32≡25≡-­‐9	
  (mod	
  41)	
  
•  Então	
  (25)4≡(-­‐9)4	
  (mod	
  41)	
  (Teorema	
  (f))	
  
•  220	
  ≡	
  81Ÿ81	
  (mod	
  41)	
  
•  Mas,	
  81≡-­‐1	
  (mod	
  41),	
  então	
  812≡(-­‐1)2	
  (mod	
  41)	
  
•  Usando	
  (c)	
  do	
  Teorema,	
  temos:	
  
•  220	
  ≡	
  81Ÿ81	
  (mod	
  41)	
  e	
  812≡1	
  (mod	
  41)	
  à	
  220	
  ≡	
  1	
  (mod	
  41)	
  
•  Usando	
  (e):	
  
•  220	
  -­‐1≡	
  1-­‐1	
  (mod	
  41)	
  à	
  220	
  -­‐1≡	
  0	
  (mod	
  41)	
  à	
  é	
  múl&plo!	
  
Atenção	
  
•  Vimos	
  que	
  se	
  a	
  ≡	
  b	
  (mod	
  n),	
  então	
  	
  
ac	
  ≡	
  bc	
  (mod	
  n)	
  para	
  um	
  inteiro	
  c	
  qualquer	
  
•  No	
  entanto,	
  o	
  inverso	
  não	
  é	
  verdadeiro:	
  
•  Ex.:	
  2·∙4	
  ≡	
  2·∙1	
  (mod	
  6)	
  mas	
  4	
  ≢	
  1	
  (mod	
  6)	
  	
  
•  Algumas	
  vezes	
  o	
  cancelamento	
  é	
  possível,	
  como	
  
veremos	
  a	
  seguir	
  
11/18/13	
  
4	
  
Teorema	
  
•  Se	
  ca	
  ≡	
  bc	
  (mod	
  n)	
  ⇒ a ≡	
  b	
  (mod	
  n/d),	
  onde	
  	
  
d	
  =	
  GCD	
  (c,n)	
  
•  Lei	
  de	
  cancelamento	
  
•  Prova:	
  
•  ca	
  ≡	
  bc	
  (mod	
  n)	
  	
  
•  (ca-­‐cb)=kn	
  
•  GCD(c,n)=d	
  à	
  c=dr	
  e	
  n=ds,	
  r	
  e	
  s	
  inteiros	
  e	
  
rela,vamente	
  primos	
  
•  dra-­‐drb=kds	
  à	
  r(a-­‐b)=ks	
  então	
  s|r(a-­‐b)	
  
Cont.	
  
• Lembrando:	
  
•  Lemma	
  de	
  Euclides:	
  Se	
  a	
  |	
  bc,	
  com	
  gcd(a,b)=1,	
  
então	
  a	
  |	
  c.	
  
•  r	
  e	
  s	
  são	
  rela,vamente	
  primos,	
  então	
  
GCD(r,s)=1	
  
•  Se	
  s|r(a-­‐b)	
  e	
  GCD(r,s)=1	
  =>	
  s|(a-­‐b)	
  (lemma	
  de	
  Euclides)	
  
•  Então	
  ⇒	
  a	
  ≡	
  b	
  (mod	
  s)	
  ou	
  seja:	
  
	
  ⇒	
  a	
  ≡	
  b	
  (mod	
  n/d)	
  
Lei	
  de	
  cancelamento	
  
•  Corolário	
  1:	
  
•  Se	
  ca	
  ≡	
  cb	
  (mod	
  n)	
  e	
  GCD	
  (c,n)	
  =	
  1,	
  então	
  
a	
  ≡	
  b	
  (mod	
  n)	
  
•  Corolário	
  2:	
  
•  Se	
  ca	
  ≡	
  cb	
  (mod	
  p)	
  onde	
  p	
  é	
  primo	
  e	
  p∤c,	
  então	
  	
  
a	
  ≡	
  b	
  (mod	
  p)	
  
Exemplo	
  1	
  
•  Considere	
  a	
  congruência	
  
33	
  ≡	
  15	
  (mod	
  9)	
  
Ou,	
  se	
  preferir	
  
3·∙11	
  ≡	
  3·∙5	
  (mod	
  9)	
  
•  Visto	
  que	
  GCD(3,9)	
  =	
  3,	
  então	
  podemos	
  dizer	
  
11	
  ≡	
  5	
  (mod	
  9/3)	
  ⇒ 11	
  ≡	
  5	
  (mod	
  3)	
  	
  
Exemplo	
  2	
  
•  Considere	
  a	
  congruência	
  
-­‐35	
  ≡	
  45	
  (mod	
  8)	
  
O	
  mesmo	
  que:	
  
5·∙(-­‐7)	
  ≡	
  5	
  ·∙9	
  (mod	
  8)	
  
	
  
•  Note	
  que	
  os	
  inteiros	
  5	
  e	
  8	
  são	
  rela,vamente	
  
primos,	
  i.e.,	
  GCD(5,8)	
  =	
  1	
  
•  Portanto,	
  pelo	
  corolário	
  1:	
  
-­‐7	
  ≡	
  9	
  (mod	
  8)	
  
Exercício	
  
•  Prove:	
  
a.  Se	
  a	
  ≡	
  b	
  (mod	
  n)	
  e	
  m|n,	
  então	
  a	
  ≡	
  b	
  (mod	
  m)	
  
b.  Se	
  a	
  ≡	
  b	
  (mod	
  n)	
  e	
  c>0,	
  então	
  ca	
  ≡	
  cb	
  (mod	
  
cn)	
  
c.  Se	
  a	
  ≡	
  b	
  (mod	
  n)	
  e	
  os	
  inteiros	
  a,	
  b	
  e	
  n	
  são	
  
todos	
  divisíveis	
  por	
  d>0,	
  então	
  a/d	
  ≡	
  b/d	
  
(mod	
  n/d)	
  
11/18/13	
  
5	
  
Testes	
  especiais	
  de	
  divisibilidade	
  
•  Dado	
  um	
  inteiro	
  b	
  >	
  1,	
  qualquer	
  inteiro	
  posi,vo	
  N	
  
pode	
  ser	
  escrito	
  unicamente	
  em	
  termos	
  de	
  potências	
  
de	
  b,	
  ou	
  seja:	
  
	
  
	
  
Onde,	
  0	
  ≤	
  ak	
  ≤	
  b-­‐1	
  
	
  
	
  	
  	
  	
  	
  
0
1
1
2
2
1
1 ... ababababaN
m
m
m
m +++++=
−
−
Testes	
  especiais	
  de	
  divisibilidade	
  
Pelo	
  algoritmo	
  da	
  divisão:	
  
	
  
N	
  =	
  q1b	
  +	
  a0,	
  0	
  ≤	
  a0	
  ≤	
  b	
  	
  (1)	
  
	
  
Se	
  q1	
  ≥	
  b,	
  então	
  podemos	
  dividí-­‐lo	
  mais	
  de	
  uma	
  vez:	
  
	
  
q1=	
  q2b	
  +	
  a1,	
  0	
  ≤	
  a1	
  ≤	
  b	
  	
  (2)	
  
	
  
Subs,tuindo	
  (2)	
  em	
  (1):	
  
N	
  =	
  (q2b	
  +	
  a1)b	
  +	
  a0	
  
	
  	
  =	
  q2b2	
  +	
  a1b	
  +	
  a0	
  
	
  	
  =	
  q3b3	
  +	
  q2b2	
  +	
  a1b	
  +	
  a0	
  
	
  	
  	
  	
  =	
  ...	
  
	
  	
  	
  	
  	
   0
1
1
2
2
1
1 ... ababababaN
m
m
m
m +++++=
−
−
Enquanto	
  q2≥b	
  
podemos	
  con,nuar	
  
Notação	
  lugar-­‐valor	
  de	
  N	
  	
  na	
  base	
  b	
  
•  Note	
  que	
  N	
  	
  
Pode	
  ser	
  representado	
  simplesmente	
  pelo	
  vetor	
  
de	
  coeficientes:	
  
	
  
	
  
	
  Obs:	
  Não	
  é	
  um	
  produto,	
  mas	
  uma	
  sequência	
  de	
  coeficientes	
  
	
  
Valores	
  de	
  base	
  b	
  pequenos	
  	
  trazem	
  representações	
  mais	
  longas	
  dos	
  
números,	
  com	
  a	
  vantagem	
  de	
  trazer	
  menos	
  opções	
  para	
  os	
  
coeficientes	
  
0
1
1
2
2
1
1 ... ababababaN
m
m
m
m +++++=
−
−
bmm aaaaaN )...( 0121−=
Exemplo	
  
•  Caso	
  mais	
  simples:	
  base	
  b	
  =	
  2	
  
•  Sistema	
  de	
  numeração	
  binário	
  
•  Apenas	
  0	
  e	
  1	
  podem	
  aparecer	
  como	
  coeficientes	
  
•  Todo	
  inteiro	
  posi,vo	
  pode	
  assim	
  ser	
  expresso	
  
como	
  uma	
  soma	
  de	
  potências	
  de	
  2	
  
•  	
  Ex.:	
  105	
  =	
  1·∙26+1·∙25+0·∙24+1·∙23+0·∙22+0·∙21+1	
  
=	
  26+25+23+1	
  
	
  
•  Na	
  forma	
  abreviada:	
  105	
  =	
  (1101001)2	
  
Teorema	
  	
  
•  Seja	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  uma	
  função	
  polinomial	
  de	
  x	
  com	
  
coeficientes	
  ck.	
  Se	
  a	
  ≡	
  b	
  (mod	
  n)	
  então	
  	
  
P(a)	
  ≡	
  P(b)	
  (mod	
  n)	
  
•  Dizemos	
  que	
  a	
  é	
  uma	
  solução	
  da	
  congruência	
  	
  
P(x)	
  ≡	
  0	
  (mod	
  n)	
  se	
  P(a)	
  ≡	
  0	
  (mod	
  n)	
  	
  
•  Corolário:	
  
•  Se	
  a	
  é	
  uma	
  solução	
  de	
  P(x)	
  ≡	
  0	
  (mod	
  n)	
  e	
  	
  
a	
  ≡	
  b	
  (mod	
  n)	
  então	
  b	
  também	
  é	
  solução	
  
∑
=
=
m
kk
k xcxP
0
)(
Exemplo	
  
•  Para	
  calcular	
  5110	
  (mod	
  131)	
  
•  Expoente	
  110	
  pode	
  ser	
  escrito	
  em	
  binário	
  como	
  
•  110=64+32+8+4+2=(110110)2	
  
•  5110=564+32+8+4+2=564	
  *	
  532	
  *	
  58	
  *	
  54	
  *	
  52	
  
•  Calculamos	
  as	
  congruencias	
  correspondentes	
  aos	
  1’s	
  na	
  
representação	
  binária	
  
•  564	
  *	
  532	
  *	
  58	
  *	
  54	
  *	
  52≡105*74*114*101*25≡60	
  (mod	
  131)	
  
11/18/13	
  
6	
  
Exemplo	
  de	
  utilização	
  
•  A	
  aritmé,ca	
  modular	
  é	
  comumente	
  u,lizada	
  no	
  cálculo	
  de	
  
dígitos	
  verificadores	
  (ex.:	
  CPF,	
  contas	
  bancárias,	
  cheques,	
  
passaportes,	
  etc)	
  
•  O	
  que	
  se	
  faz	
  habitualmente	
  é	
  calcular	
  a	
  soma	
  do	
  produto	
  
entre	
  os	
  dígitos	
  do	
  número	
  a	
  ser	
  verificado	
  por	
  
determinados	
  “pesos”	
  módulo	
  10	
  
•  Ex.:	
  
•  a9	
  ≡	
  7a1+3a2+9a3+7a4+3a5+9a6+7a7+3a8	
  (mod	
  10)	
  
•  Para	
  o	
  número	
  81504216	
  teremos:	
  
•  a9	
  ≡	
  7·∙8+3·∙1+9·∙5+7·∙0+3·∙4+9·∙2+7·∙1+3·∙6	
  (mod	
  10)	
  
159	
  ≡	
  9	
  (mod	
  10)	
  
Teste	
  de	
  primalidade	
  
•  U,lizar	
  teste	
  de	
  primalidade	
  de	
  Fermat	
  
•  Dados:	
  
•  n:	
  o	
  número	
  a	
  ser	
  testado	
  
•  k:	
  o	
  número	
  de	
  vezes	
  que	
  deve	
  ser	
  testado	
  (grau	
  de	
  
certeza)	
  
•  O	
  algoritmo:	
  
repita k vezes: 
Escolha um número a aleatoriamente 
no intervalo [1, n−1] 
Se an−1 mod n ≠ 1 então retorne composto 
Senão retorne provavelmente primo 
32	
  
Teste	
  de	
  primalidade	
  Exemplo	
  
•  O	
  algoritmo:	
  
repita k vezes: 
Escolha um número a aleatoriamente 
no intervalo [1, n−1] 
Se an−1 mod n ≠ 1 então retorne composto 
Senão retorne provavelmente primo 
•  Seja	
  n	
  =	
  105	
  
•  Iteração	
  1:	
  a	
  =	
  92:	
  92104	
  mod	
  105	
  =	
  1	
  
•  Iteração	
  2:	
  a	
  =	
  84:	
  84104	
  mod	
  105	
  =	
  21	
  
•  Portanto,	
  105	
  é	
  composto	
   33	
  
Teste	
  de	
  primalidade	
  Exemplo	
  
•  O	
  algoritmo:	
  
repita k vezes: 
Escolha um número a aleatoriamente 
no intervalo [1, n−1] 
Se an−1 mod n ≠ 1 então retorne composto 
Senão retorne provavelmente primo 
•  Seja	
  n	
  =	
  101	
  
•  Iteração	
  1:	
  a	
  =	
  55:	
  55100	
  mod	
  101	
  =	
  1	
  
•  Iteração	
  2:	
  a	
  =	
  60:	
  60100	
  mod	
  101	
  =	
  1	
  
•  Iteração	
  3:	
  a	
  =	
  14:	
  14100	
  mod	
  101	
  =	
  1	
  
•  Iteração	
  4:	
  a	
  =	
  73:	
  73100	
  mod	
  101	
  =	
  1	
  
•  Neste	
  ponto,	
  101	
  tem	
  (½)4	
  =	
  1/16	
  de	
  chances	
  ainda	
  	
  de	
  
ser	
  composto	
  
Mais	
  sobre	
  o	
  teste	
  de	
  primalidade	
  de	
  Fermat	
  
•  A	
  cada	
  iteração	
  a	
  probabilidade	
  de	
  que	
  o	
  número	
  seja	
  
composto	
  cai	
  pela	
  metade	
  
•  Probabilidade	
  =	
  (½)k	
  
•  Se	
  k	
  =	
  100,	
  a	
  probabilidade	
  de	
  ser	
  um	
  composto	
  é	
  de	
  	
  (½)100	
  =	
  1	
  em	
  1.2	
   
×	
  1030	
  
•  Portanto,	
  k	
  =	
  100	
  é	
  uma	
  boa	
  escolha	
  
•  Entretanto,	
  ainda	
  não	
  é	
  uma	
  certeza!	
  
•  Existem	
  números	
  conhecidamente	
  compostos	
  mas	
  que	
  são	
  apontados	
  
como	
  primos	
  neste	
  teste	
  
•  Fonte:	
  hxp://en.wikipedia.org/wiki/Fermat_primality_test	
  
Campanha	
  de	
  recrutamento	
  do	
  google	
  
36	
  
11/18/13	
  
7	
  
37