Aula05-Congruencias Lineares.pptx

Prévia do material em texto

11/18/13	
  
1	
  
Congruências	
  Lineares	
  
Matemá,ca	
  Discreta	
  2	
  
Rosen	
  –	
  “Discrete	
  Mathema2cs”	
  (Cap.	
  4)	
  	
  
Rosen	
  –	
  “Elementary	
  Number	
  Theory”	
  (Cap.	
  3)	
  	
  
Burton	
  (Cap.	
  4)	
  
André	
  Câmara	
  
Congruências	
  lineares	
  
•  Uma	
  congruência	
  linear	
  é	
  uma	
  equação	
  do	
  ,po	
  
ax	
  ≡	
  b	
  (mod	
  n).	
  	
  
•  Devemos	
  encontrar	
  todos	
  os	
  inteiros	
  x	
  que	
  
sa,sfazem	
  a	
  relação	
  de	
  congruência	
  
•  Um	
  método	
  é	
  buscar	
  por	
  um	
  inteiro	
  tal	
  que:	
  
•  Se	
  tal	
  inteiro	
  exis,r.	
  Este	
  inteiro	
  é	
  chamado	
  
inverso	
  de	
  a	
  modulo	
  m	
  
Inverso	
  modulo	
  m	
  
•  Teorema:	
  
•  Se	
  a	
  e	
  m	
  são	
  inteiros	
  rela,vamente	
  primos,	
  e	
  
m>1,	
  então	
  existe	
  um	
  inverso	
  de	
  a	
  módulo	
  m.	
  
•  Ou	
  seja,	
  existe	
  um	
  único	
  inteiro	
  posi,vo	
  	
  	
  	
  	
  menor	
  
que	
  m	
  que	
  é	
  um	
  inverso	
  de	
  a	
  modulo	
  m	
  e	
  todo	
  
outro	
  inverso	
  de	
  a	
  modulo	
  m	
  é	
  congruente	
  a	
  	
  	
  	
  	
  
modulo	
  m.	
  
•  Prova:	
  
•  Se	
  o	
  GCD(a,m)=1,	
  existem	
  inteiros	
  s	
  e	
  t	
  tais	
  que:	
  
sa	
  +	
  tm	
  =	
  1	
  
Isso	
  implica	
  que:	
  sa-­‐1=m(-­‐t)	
  à	
  sa	
  ≡	
  1	
  (mod	
  m)	
  
O	
  que	
  faz	
  de	
  s	
  um	
  inverso	
  de	
  a	
  modulo	
  m.	
  
Inverso	
  modulo	
  m	
  
•  Fácil	
  de	
  encontrar	
  por	
  inspeção,	
  quando	
  m	
  é	
  
pequeno.	
  
•  Buscar	
  um	
  múl,plo	
  de	
  a	
  que	
  exceda	
  um	
  
múl,plo	
  de	
  m	
  em	
  1	
  
•  Ex.:	
  Encontrar	
  o	
  inverso	
  de	
  3	
  módulo	
  7	
  
•  5	
  ·∙	
  3	
  ≡	
  1	
  (mod	
  7)	
  ,	
  portanto	
  5	
  é	
  um	
  inverso	
  de	
  3	
  módulo	
  7	
  
•  Podemos	
  usar	
  o	
  algoritmo	
  euclidiano	
  (GCD)	
  
para	
  encontrar	
  tais	
  inversos	
  
	
  
Congruências	
  lineares	
  
•  Uma	
  congruência	
  linear	
  é	
  uma	
  equação	
  do	
  ,po	
  
ax	
  ≡	
  b	
  (mod	
  n).	
  	
  
•  A	
  solução	
  é	
  dada	
  por	
  um	
  inteiro	
  x0	
  para	
  o	
  qual	
  
ax0	
  ≡	
  b	
  (mod	
  n),	
  i.e.:	
  
n|(ax0	
  –	
  b)	
  ⇒ ax0	
  –	
  b	
  =	
  ny0	
  
⇒	
  ax0	
  -­‐	
  ny0	
  =	
  b	
  (equação	
  diofân,ca)	
  
	
  
Ex.:	
  3x	
  ≡	
  9	
  mod	
  12	
  
	
   	
  x0	
  =	
  3	
  
	
   	
  x1	
  =	
  -­‐9	
  
Congruências	
  lineares	
  
Ex.:	
  3x	
  ≡	
  9	
  mod	
  12	
  
	
   	
  x0	
  =	
  3	
  
	
   	
  x1	
  =	
  -­‐9	
  
	
  
•  Entretanto,	
  observe	
  x0≡x1	
  (mod	
  12)	
  	
  
•  i.e.:	
  3	
  ≡	
  -­‐9	
  (mod	
  12)	
  
•  Todos	
  elementos	
  desta	
  classe	
  de	
  congruência	
  também	
  são	
  
soluções	
  
...	
  ≡	
  -­‐21	
  ≡	
  -­‐9	
  ≡	
  3	
  ≡	
  15	
  ≡	
  ...	
  (mod	
  12)	
  
	
  
Dessa	
  forma,	
  o	
  interesse	
  é	
  descobrir	
  quais	
  as	
  soluções	
  
incongruentes	
  (ou	
  seja,	
  quantas	
  das	
  12	
  classes	
  de	
  congruências	
  
fornecem	
  soluções?)	
  
11/18/13	
  
2	
  
Equação	
  Diofântica	
  
•  Chamamos	
  equação	
  diofân,ca	
  qualquer	
  equação	
  
com	
  2	
  ou	
  mais	
  variáveis	
  que	
  deve	
  ser	
  resolvida	
  com	
  
inteiros:	
  
ax+by	
  =	
  c,	
  a,b	
  e	
  c	
  inteiros	
  
•  Podem	
  exis,r	
  um	
  grande	
  número	
  de	
  soluções	
  
•  Ex.:	
  3x+6y	
  =	
  18	
  
3·∙4+6·∙1	
  =	
  18	
  
3·∙(-­‐6)+6·∙6	
  =	
  18	
  
3·∙10+6·∙(-­‐2)	
  =	
  18	
  
Eq.	
  Diofân,ca	
  linear	
  
Equação	
  Diofântica	
  
•  Pode	
  não	
  haver	
  solução	
  nos	
  inteiros	
  
•  Ex:	
  2x+10y	
  =	
  17	
  ⇒ x,y	
  ∈	
  R 
•  Observe	
  que:	
  
•  3x+6y	
  =	
  18	
  ⇒	
  ∃	
  
•  GCD(3,6)	
  =	
  3	
  ⇒	
  3|18	
  	
  
•  2x+10y	
  =	
  17	
  ⇒	
  ∄	
  
•  GCD(2,10)	
  =	
  2	
  ⇒	
  2∤17	
  
•  Podemos	
  concluir	
  que	
  a	
  equação	
  diofân,ca	
  linear	
  	
  
ax+by=c	
  admite	
  solução	
  SSE	
  d|c	
  ∴	
  d	
  =	
  GCD(a,b)	
  
Teorema	
  
•  A	
  EDL	
  ax+by=c	
  tem	
  solução	
  SSE	
  	
  
d|c	
  ∴	
  d	
  =	
  GCD(a,b).	
  
	
  
•  Se	
  (x0,y0)	
  é	
  uma	
  solução	
  par,cular	
  da	
  equação,	
  
então	
  todas	
  as	
  soluções	
  são	
  da	
  forma:	
  
t
d
ayy
t
d
bxx
⎟
⎠
⎞
⎜
⎝
⎛−=
⎟
⎠
⎞
⎜
⎝
⎛+=
0
0
,	
  onde	
  t	
  é	
  um	
  inteiro	
  qualquer	
  
Teorema	
  2.9	
  -­‐	
  Exemplo	
  
•  Ex.:	
  172x+20y	
  =	
  1000	
  
Calcular	
  o	
  GCD(172,20):	
  
172	
  =	
  20·∙8	
  +	
  12	
  
20	
  =	
  12·∙1	
  +	
  8	
  
12	
  =	
  8·∙1	
  +	
  4	
   	
  GCD(172,20)	
  =	
  4	
  
8	
  =	
  4·∙2	
  +	
  0	
  
	
  
Como	
  4|1000,	
  então	
  existe	
  solução!	
  
	
  
	
  
	
  
Teorema	
  2.9	
  -­‐	
  Exemplo	
  
•  Seguindo	
  o	
  caminho	
  inverso,	
  temos:	
  
4	
  =	
  12	
  -­‐	
  8·∙1	
  
4	
  =	
  12	
  –	
  (20-­‐12)	
  
4	
  =	
  2·∙12	
  –	
  20	
  
4	
  =	
  2·∙(172-­‐8·∙20)-­‐20	
  
4	
  =	
  2·∙172	
  -­‐16·∙20	
  –	
  20	
  
4	
  =	
  2·∙172	
  -­‐(16+1)·∙20	
  
4	
  =	
  2·∙172	
  +(-­‐17)·∙20 	
  ·∙250	
  
1000	
  =	
  172	
  ·∙500	
  +	
  (-­‐4250)·∙20	
  
	
  
	
  
	
  
	
  
x0	
  =	
  500	
  
y0	
  =	
  -­‐4250	
  
Queremos	
  chegar	
  a	
  	
  
172x+20y	
  =	
  1000	
  
Teorema	
  2.9	
  -­‐	
  Exemplo	
  
•  Sendo	
  assim,	
  x=500	
  e	
  y=-­‐4250	
  fornece	
  uma	
  
possível	
  solução	
  da	
  equação.	
  Outras	
  soluções	
  
possíveis	
  são	
  expressas	
  por:	
  
x	
  =	
  500	
  +	
  (20/4)t	
  
y	
  =	
  -­‐4250	
  –	
  (172/4)t	
  
	
  
x	
  =	
  500	
  +	
  5t	
  
y	
  =	
  -­‐4250	
  –	
  43t	
  
	
  
	
  
Se	
  for	
  exigido	
  que	
  as	
  
soluções	
  sejam	
  inteiras	
  e	
  
posi,vas?	
  
t
d
ayy
t
d
bxx
⎟
⎠
⎞
⎜
⎝
⎛−=
⎟
⎠
⎞
⎜
⎝
⎛+=
0
0
11/18/13	
  
3	
  
Teorema	
  2.9	
  -­‐	
  Exemplo	
  
•  Soluções	
  posi,vas:	
  
1.  x>0	
  ⇒ 500 + 5t > 0 
 5t > -500 
 t > -100 
 
2.  y>0	
  ⇒	
  -­‐4250	
  -­‐43t	
  >	
  0	
  
	
  43t	
  <	
  -­‐4250	
  
	
  t	
  <	
  -­‐4250	
  /	
  43	
  =	
  -­‐98,83...	
  
	
  t	
  <	
  -­‐98,83...	
  
	
  
•  Logo,	
  -­‐100	
  <	
  t	
  <	
  -­‐98,83...	
  
t	
  =	
  -­‐99	
  ⇒ x = 5 
 y = 7	
  
Únicas	
  soluções	
  inteiras	
  
posi,vas	
  para	
  a	
  equação	
  
Corolário	
  
•  Se	
  GCD(a,b)	
  =	
  1	
  e,	
  se,	
  (x0,y0)	
  é	
  uma	
  solução	
  da	
  
equação	
  ax	
  +	
  by	
  =	
  c,	
  todas	
  as	
  soluções	
  serão	
  
dadas	
  por:	
  
x=x0+	
  bt 	
  ,	
  t	
  ∈	
  Z 
y=y0	
  -­‐	
  at	
  
	
  
•  Ex:	
  5x	
  +	
  22y	
  =	
  18	
  
	
  SOLUÇÃO:	
  x0	
  =	
  8 	
  x	
  =	
  8	
  +	
  22t	
  
	
   	
  	
  y0	
  	
  =	
  -­‐1 	
  y	
  =	
  -­‐1	
  –	
  5t	
  
	
  
Teorema	
  
•  A	
  congruência	
  	
  linear	
  ax	
  ≡	
  b	
  mod	
  n	
  tem	
  solução	
  ,	
  
SSE,	
  d|b,	
  onde	
  d	
  =	
  GCD(a,n),	
  a	
  qual	
  tem	
  d	
  
soluções	
  mutuamente	
  incongruentes	
  modulo	
  n.	
  	
  
•  Se	
  x0é	
  uma	
  solução	
  de	
  ax	
  ≡	
  b	
  (mod	
  n),	
  o	
  
conjunto	
  de	
  soluções	
  é	
  dado	
  por:	
  
•  Corolário:	
  
•  Se	
  GCD(a,n)=1,	
  então	
  a	
  congruência	
  ax	
  ≡	
  b	
  
mod	
  n	
  tem	
  uma	
  única	
  solução	
  módulo	
  n	
  
⎟
⎠
⎞
⎜
⎝
⎛−+⎟
⎠
⎞
⎜
⎝
⎛++
d
ndx
d
nx
d
nxx )1(,...,2,, 0000
Exemplo	
  
•  Considere	
  a	
  congruência	
  linear	
  
18x	
  ≡	
  30	
  (mod	
  42)	
  
•  Note	
  que	
  o	
  GCD(18,42)	
  =	
  6	
  e	
  6|30	
  
•  Pelo	
  teorema,	
  temos	
  6	
  possíveis	
  soluções	
  para	
  a	
  equação	
  
•  Uma	
  possível	
  solução	
  é	
  x=4	
  (por	
  inspeção)	
  
18x	
  –	
  30	
  =	
  42*1	
  ⇒ x = 4 
•  Pela	
  equação,	
  obtemos	
  as	
  outras	
  soluções:	
  
x	
  ≡	
  4+(42/6)t	
  ≡	
  4	
  +	
  7t	
  (mod	
  42) 	
  ,	
  t=0,1,2,...5	
  
	
  
x	
  ≡	
  4,11,18,25,32,39	
  (mod	
  42)	
  
Exercício	
  
•  Encontre	
  as	
  soluções	
  para	
  a	
  congruência	
  linear	
  
9x	
  ≡	
  21	
  (mod	
  30)	
  
Exercício	
  
•  Encontre	
  as	
  soluções	
  para	
  a	
  congruência	
  linear	
  9x	
  ≡	
  21	
  (mod	
  30)	
  
•  Solução	
  
	
  	
  	
  Primeiramente,	
  verificar	
  se	
  possui	
  solução:	
  
	
  GCD(a,n)=GCD(9,30)	
  
	
   	
  30	
  =	
  9.3	
  +	
  3	
  ß	
  GCD(9,30)=3	
  
	
   	
  9	
  	
  	
  =	
  3.3	
  +	
  0	
  	
  
	
  
	
  	
  	
  	
  A	
  congruência	
  9x	
  ≡	
  21	
  (mod	
  30)	
  é	
  equivalente	
  a	
  9x-­‐30y=21	
  
•  Lembrando:	
  GCD(a,b)=d=ax+by	
  
•  No	
  nosso	
  caso:	
  9x	
  +	
  30y	
  =	
  3	
  
•  Solucionar	
  u,lizando	
  o	
  algoritmo	
  euclidiano:	
  
	
  	
  	
  	
  	
  	
  	
  	
  ⇒	
  	
  	
  	
  30	
  –	
  9.3	
  =	
  3	
  
	
  	
  	
  	
  	
  	
  	
  9	
  Ÿ	
  (-­‐3)	
  	
  	
  +	
  30	
  Ÿ	
  (1)	
  =	
  3	
   	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  Ÿ (7)	
  
	
  	
  	
  	
  	
  	
  	
  9	
  Ÿ	
  (-­‐21)	
  +	
  30	
  Ÿ	
  (7)	
  =	
  21	
  
•  x0=-­‐21	
  	
  	
  y0=7	
  
•  Soluções	
  incongruentes:	
  x	
  =	
  -­‐21	
  +	
  10t,	
  para	
  t=0,1,2	
  
•  x1	
  =	
  -­‐21	
  +	
  10	
  =	
  -­‐11	
  
•  x2	
  =	
  -­‐21	
  +	
  2*10	
  =	
  -­‐1	
  
3	
  soluções	
  incongruentes!	
  
11/18/13	
  
4	
  
Teorema	
  Chinês	
  do	
  Resto	
  
•  Uma	
  senhora	
  estava	
  caminhando	
  para	
  um	
  mercado	
  quando	
  
um	
  cavalo	
  se	
  bateu	
  com	
  a	
  sua	
  cesta	
  de	
  ovos.	
  O	
  cavaleiro	
  
queria	
  pagar	
  os	
  danos	
  e	
  perguntou	
  para	
  a	
  senhora	
  quantos	
  
ovos	
  haviam	
  na	
  cesta.	
  
•  Ela	
  não	
  se	
  lembrava	
  exatamente	
  da	
  quan,dade,	
  mas	
  sabia	
  
que	
  se	
  ,rasse	
  os	
  ovos	
  da	
  cesta	
  de	
  três	
  em	
  três,	
  sobravam	
  dois	
  
ovos.	
  Se	
  ,rasse	
  de	
  5	
  em	
  5,	
  sobravam	
  3	
  ovos	
  e	
  de	
  7	
  em	
  7	
  
sobravam	
  2.	
  
•  Qual	
  seria	
  a	
  menor	
  quan,dade	
  de	
  ovos	
  que	
  ela	
  poderia	
  ter?	
  
•  Como	
  formular	
  esse	
  problema	
  usando	
  a	
  notação	
  da	
  aritmé,ca	
  
modular?	
  
Teorema	
  Chinês	
  do	
  Resto	
  
•  No	
  século	
  um,	
  o	
  matemá,co	
  chinês	
  chamado	
  Sun-­‐
Tsu	
  se	
  perguntou:	
  Que	
  número	
  será	
  esse	
  de	
  forma	
  
que	
  quando	
  dividido	
  por	
  3,	
  o	
  resto	
  é	
  2;	
  quando	
  
dividido	
  por	
  5,	
  o	
  resto	
  é	
  3;	
  e	
  quando	
  dividido	
  por	
  7,	
  
o	
  resto	
  é	
  2?	
  
•  A	
  pergunta	
  é:	
  Qual	
  é	
  a	
  solução	
  para	
  o	
  seguinte	
  
sistema	
  de	
  congruências?	
  
•  x	
  ≡	
  2	
  (mod	
  3)	
  
•  x	
  ≡	
  3	
  (mod	
  5)	
  
•  x	
  ≡	
  2	
  (mod	
  7)?	
  
Teorema	
  Chinês	
  do	
  Resto	
  Formalizando...	
  
•  Sejam	
  m1,	
  m2,	
  .	
  .	
  .	
  mn	
  inteiros	
  posi,vos	
  primos	
  entre	
  
si.	
  O	
  sistema	
  
x	
  ≡	
  a1	
  (mod	
  m1)	
  
x	
  ≡	
  a2	
  (mod	
  m2)	
  
...	
  
x	
  ≡	
  an	
  (mod	
  mn)	
  
•  possui	
  uma	
  única	
  solução	
  módulo	
  m	
  =	
  m1.m2...	
  mn.	
  
(Ou	
  seja,	
  existe	
  uma	
  solução	
  x	
  com	
  0	
  ≤	
  x	
  <	
  m,	
  e	
  todas	
  
as	
  outras	
  soluções	
  são	
  congruentes	
  módulo	
  m	
  com	
  
essa	
  solução).	
  
Solução	
  
•  Como	
  calcular	
  x:	
  
•  faça	
  m	
  =	
  m1.m2.	
  .	
  .	
  .	
  mn;	
  
•  para	
  k	
  =	
  1,	
  2,	
  .	
  .	
  .	
  n	
  faça	
  Mk	
  =	
  m/mk;	
  
•  chame	
  Yk	
  o	
  inverso	
  de	
  Mk	
  módulo	
  mk	
  e	
  calcule	
  
Yk,	
  Ou	
  seja,	
  Mk.Yk	
  ≡	
  1	
  (mod	
  mk);	
  
•  x	
  ≡	
  a1M1Y1	
  +	
  a2M2Y2	
  +	
  .	
  .	
  .	
  anMnYn	
  (mod	
  m).	
  
Prova	
  
•  Seja	
  Mk	
  =	
  m/mk,	
  par	
  k=1,2,...n	
  
•  Mk	
  é	
  o	
  produto	
  dos	
  módulos	
  (exceto	
  mk)	
  
•  mi	
  e	
  mk	
  são	
  rela,vamente	
  primos,	
  portanto	
  
GCD(mk,Mk)=1	
  
•  Pelo	
  teorema	
  anterior,	
  temos	
  que	
  existe	
  um	
  
inteiro	
  Yk	
  (um	
  inverso	
  de	
  Mk	
  modulo	
  mk)	
  
Mk.Yk	
  ≡	
  1	
  (mod	
  mk)	
  
	
  
Prova	
  (cont.)	
  
•  Para	
  formar	
  uma	
  solução	
  simultânea,	
  fazemos:	
  
x	
  =	
  a1M1Y1	
  +	
  a2M2Y2	
  +	
  .	
  .	
  .	
  anMnYn	
  	
  
•  Para	
   mostrar	
   que	
   x	
   é	
   uma	
   solução	
   simultânea,	
  
observe	
  que	
  Mj	
  ≡	
  0	
  (mod	
  mk	
  )	
  ,	
  sempre	
  que	
  j	
  ≠	
  k	
  	
  
•  Dessa	
  forma,	
  todos,	
  exceto	
  o	
  k-­‐ésimo	
  termo,	
  da	
  
soma	
  são	
  congruentes	
  a	
  0	
  mod	
  mk.	
  Uma	
  vez	
  que	
  
Mk.Yk	
  ≡	
  1	
  (mod	
  mk),temos:	
  
x	
  ≡	
  akMkYk	
  ≡	
  ak	
  (mod	
  mk),	
  para	
  k	
  =	
  1,2,...n	
  
•  Temos	
  que	
  x	
  é	
  uma	
  solução	
  simultânea	
  para	
  as	
  n	
  
congruências.	
  
11/18/13	
  
5	
  
Exemplo	
  anterior	
  
1.  m	
  =	
  3.5.7	
  =	
  105;	
  
2.  M1	
  =	
  m/3	
  =	
  35,	
  M2	
  =	
  m/5	
  =	
  21,	
  	
  
e	
  M3	
  =	
  m/7	
  =	
  15	
  
3.  As	
  congruências	
  lineares:	
  
4.  Tem	
  solução:	
  	
  
5.  x	
  ≡	
  2.35.2	
  +	
  3.21.1	
  +	
  2.15.1	
  (mod	
  105)	
  
	
  	
  	
  	
  	
  x	
  ≡	
  233	
  ≡	
  23	
  (mod	
  105).	
  
•  Resp.	
  Pelo	
  menos	
  23	
  ovos	
  
x	
  ≡	
  2	
  (mod	
  3)	
  
x	
  ≡	
  3	
  (mod	
  5)	
  
x	
  ≡	
  2	
  (mod	
  7)	
  
Outro	
  exemplo	
  
•  Que	
  inteiros	
  deixam	
  resto	
  1	
  quando	
  divididos	
  
por	
  2	
  e	
  resto	
  1	
  quando	
  divididos	
  por	
  3?	
  
•  x	
  ≡	
  1	
  (mod	
  2)	
  e	
  x	
  ≡	
  1	
  (mod	
  3);	
  
•  m	
  =	
  6,	
  M1	
  =	
  3	
  e	
  M2	
  =	
  2;	
  
•  3Y1	
  ≡	
  1	
  (mod	
  2)	
  →	
  Y1	
  =	
  1;	
  
•  2Y2	
  ≡	
  1	
  (mod	
  3)	
  →	
  Y2	
  =	
  2;	
  
•  x	
  ≡	
  1.3.1	
  +	
  1.2.2	
  (mod	
  6)	
  
•  x	
  ≡	
  7	
  (mod	
  6).	
  
Método	
  iterativo	
  
•  Ou	
  “back	
  subs2tu2on”	
  
•  Exemplo:	
  
•  x	
  ≡	
  1	
  (mod	
  5),	
  x	
  ≡	
  2	
  (mod	
  6),	
  e	
  x	
  ≡	
  3	
  (mod	
  7)	
  
•  A	
  primeira	
  congruência	
  pode	
  ser	
  escritacomo	
  	
  
•  x=5t+1	
  
•  Subs,tuir	
  na	
  segunda	
  congruência:	
  
•  5t+1	
  ≡	
  2	
  (mod	
  6)	
  à	
  t	
  ≡	
  5	
  (mod	
  6)	
  
•  A	
  qual	
  também	
  pode	
  ser	
  escrita	
  como:	
  
•  t	
  =	
  6u	
  +5	
  
•  Subs,tuindo	
  em	
  x	
  =	
  5t	
  +	
  1,	
  temos	
  
•  x	
  =	
  5(6u+5)	
  +	
  1	
  =	
  30u+26	
  
Método	
  iterativo	
  (cont)	
  
•  Exemplo:	
  
•  x	
  ≡	
  1	
  (mod	
  5),	
  x	
  ≡	
  2	
  (mod	
  6),	
  e	
  x	
  ≡	
  3	
  (mod	
  7)	
  
•  Subs,tuindo	
  x	
  =	
  30u+26	
  na	
  terceira	
  congruência,	
  
temos	
  
•  30u+26	
  ≡	
  3(mod7).	
  	
  
•  30u+23	
  =	
  7q	
  	
  
•  Qual	
  o	
  valor	
  de	
  u?	
  
•  u	
  ≡	
  6	
  (mod	
  7)	
  à	
  u=7v	
  +	
  6,	
  subs,tuindo	
  em	
  x=30u+26,	
  
temos:	
  
•  x	
  =	
  30(7v	
  +	
  6)	
  +	
  26	
  =	
  210v	
  +	
  206	
  
•  Ou,	
  em	
  formato	
  de	
  congruência:	
  	
  	
  
x	
  ≡	
  206	
  (mod	
  210)	
  
	
  
O	
  Pequeno	
  teorema	
  de	
  Fermat	
  
•  Se	
  p	
  é	
  primo	
  e	
  a	
  é	
  um	
  inteiro	
  não	
  divisível	
  por	
  p,	
  
então	
  
ap−1	
  ≡	
  1	
  (mod	
  p).	
  
•  Portanto,	
  para	
  todo	
  inteiro	
  a,	
  temos:	
  
ap	
  ≡	
  a	
  (mod	
  p).	
  
	
  
•  Bastante	
  ú,l	
  no	
  cálculo	
  dos	
  restos	
  módulo	
  p	
  de	
  
grandes	
  potências	
  de	
  inteiros	
  
Exemplo	
  
•  Encontre	
  7222	
  mod	
  11	
  
•  Solução:	
  
•  Usar	
  o	
  pequeno	
  teorema	
  de	
  Fermat	
  ao	
  invés	
  de	
  
usar	
  o	
  algoritmo	
  da	
  exponenciação	
  modular.	
  
•  Pelo	
  teorema,	
  temos	
  que	
  	
  710	
  ≡	
  1	
  (mod	
  11),	
  
portanto,	
  (710)k	
  ≡	
  1	
  (mod	
  11)	
  para	
  todo	
  inteiro	
  
posi,vo	
  k	
  
•  Dividimos	
  o	
  expoente	
  222	
  por	
  10,	
  temos	
  	
  
222	
  =	
  22	
  ·∙	
  10	
  +	
  2.	
  
•  7222	
  =	
  722·∙10+2	
  =	
  (710)2272	
  ≡	
  (1)22	
  ·∙	
  49	
  ≡	
  5	
  (mod	
  11)	
  	
  
•  Portanto,	
  7222	
  mod	
  11	
  =	
  5	
  	
  
11/18/13	
  
6	
  
Exercício	
  
•  Use	
  o	
  pequeno	
  teorema	
  de	
  Fermat	
  para	
  
encontrar	
  7121	
  mod	
  13	
  	
   •  Ordem:	
  menor	
  potência	
  de	
  um	
  inteiro	
  que	
  deixa	
  
resto	
  1	
  
•  Encontrar	
  x	
  tal	
  que	
  gx	
  ≡	
  1	
  mod	
  p	
  
•  Exemplo:	
  Qual	
  a	
  ordem	
  de	
  2	
  modulo	
  7?	
  
•  21 ≡	
  2	
  (mod	
  7),	
  22 ≡	
  4	
  (mod	
  7),	
  23 ≡	
  1	
  (mod	
  7)	
  
•  Portanto,	
  ord7	
  2=3 
Conceito:	
  ordem	
  e	
  raiz	
  primitiva	
  
•  Raiz Primitiva: um inteiro positivo x tal 
que as potências de x geram todos os 
inteiros relativamente primos a n, sendo 
n um inteiro positivo 
•  O mesmo que um gerador de um 
grupo 
•  Ex.:	
  3	
  modulo	
  7	
  
•  31 ≡	
  3	
  (mod	
  7),	
  32 ≡	
  2	
  (mod	
  7),	
  33 ≡	
  6	
  (mod	
  7)	
  
•  34 ≡	
  4	
  (mod	
  7),	
  35 ≡	
  5	
  (mod	
  7),	
  36 ≡	
  1	
  (mod	
  7)	
  
Conceito:	
  ordem	
  e	
  raiz	
  primitiva	
  
•  Exemplo:	
  
•  U(14)={1,3,5,9,11,13}	
  	
  
•  x	
  	
  	
  	
  	
  x,	
  x2,	
  x3,	
  ...	
  (mod	
  14)	
  	
  
•  	
  1	
  :	
  	
  	
  1	
  	
  
•  	
  3	
  :	
  	
  	
  3,	
  	
  9,	
  13,	
  11,	
  	
  5,	
  	
  1	
  	
  	
  
•  	
  5	
  :	
  	
  	
  5,	
  11,	
  13,	
  	
  9,	
  	
  3,	
  	
  1	
  
•  	
  9	
  :	
  	
  	
  9,	
  11,	
  	
  1	
  
•  11	
  :	
  	
  11,	
  	
  9,	
  	
  1	
  
•  13	
  :	
  	
  13,	
  	
  1	
  
Raiz	
  primitiva	
  
•  Nem	
  todo	
  inteiro	
  tem	
  uma	
  raiz	
  primi,va	
  
•  Ex.:	
  modulo	
  8	
  
•  Rela,vamente	
  primos	
  a	
  8:	
  U(8)={1,3,5,7}	
  
•  U(8)	
  =	
  {1,3,5,7}	
  
•  〈1〉	
  =	
  {1}	
  
•  〈3〉	
  =	
  {3,1}	
  
•  〈5〉	
  =	
  {5,1}	
  
•  〈7〉	
  =	
  {7,1}	
  
•  U(8)	
  ≠	
  〈a〉	
  para	
  qualquer	
  a	
  em	
  U(8)	
  
Raiz	
  primitiva	
  
a)  Mostre	
  que	
  5	
  é	
  uma	
  raiz	
  primi,va	
  de	
  6	
  
b)  Mostre	
  que	
  2	
  é	
  uma	
  raiz	
  primi,va	
  de	
  11	
  
Exercício	
  
11/18/13	
  
7	
  
Discrete logarithm problem (DLP): 
 
 
Dado um primo p e r a raiz primitiva de p, o 
logarítmo discreto (ou índice) de um inteiro a 

na base r modulo p é o expoente x tal que 
 r x ≡	
  a	
  mod p, 0 ≤a	
  ≤	
  p-­‐1	
  
 
 
Dizemos que x é um índice ou logaritmo 
discreto de a na base r módulo p 
O	
  Problema	
  do	
  logaritmo	
  discreto	
  
•  No	
  exemplo	
  anterior:	
  
•  31 ≡	
  3	
  (mod	
  7),	
  32 ≡	
  2	
  (mod	
  7),	
  33 ≡	
  6	
  (mod	
  7)	
  
•  34 ≡	
  4	
  (mod	
  7),	
  35 ≡	
  5	
  (mod	
  7),	
  36 ≡	
  1	
  (mod	
  7)	
  
•  3	
  é	
  uma	
  raiz	
  primi,va	
  módulo	
  7	
  
•  Qual	
  o	
  logaritmo	
  discreto	
  de	
  6	
  base	
  3	
  modulo	
  7?	
  
•  	
  	
  33 ≡	
  6	
  (mod	
  7)	
  è	
  3	
  
•  log3	
  6	
  =	
  3	
  	
  
•  Ou	
  seja:	
  
•  ind31	
  =	
  6,	
  ind32	
  =	
  2,	
  ind33	
  =	
  1,	
  
•  ind34	
  =	
  4,	
  ind35	
  =	
  5,	
  ind36	
  =	
  3.	
  
Logaritmo	
  Discreto	
  Exemplo	
  
Exercício	
  
•  Encontre	
  o	
  logaritmo	
  discreto	
  de	
  3	
  e	
  5	
  modulo	
  
11	
  na	
  base	
  2	
  
•  <2>	
  =	
  {2,	
  4,	
  8,	
  5,	
  10,	
  9,	
  7,	
  3,	
  6,	
  1}	
  
•  log2	
  3	
  =	
  8	
  	
  
•  log2	
  5	
  =	
  4	
  	
  
}  Para	
  valores	
  pequenos	
  de	
  p,	
  é	
  fácil	
  resolver	
  um	
  DLP	
  por	
  
tenta,va	
  e	
  erro,	
  ou	
  busca	
  exaus,va	
  
}  Por	
  exemplo,	
  dado	
  p	
  =	
  11,	
  r	
  =	
  2	
  e	
  b	
  =	
  9,	
  podemos	
  tentar	
  
valores	
  diferentes	
  de	
  a	
  até	
  encontrar	
  a	
  solução	
  correta	
  para	
  
2a	
  	
  mod	
  11	
  =	
  9	
  
}  a=6	
  à	
  26=64	
  mod	
  11	
  =	
  9	
  
}  hp://www.alpertron.com.ar/DILOG.HTM	
  
}  Entretanto,	
  para	
  um	
  valor	
  grande	
  de	
  p,	
  i.e.,	
  se	
  p	
  tem	
  
aproximadamente	
  100	
  dígitos	
  decimais,	
  então	
  não	
  é	
  possível	
  
resolver	
  um	
  DLP	
  usando	
  a	
  tecnologia	
  atual	
  
	
  
	
  
	
  	
  
	
  
	
  
O	
  Problema	
  do	
  logaritmo	
  discreto