1

Exercícios de Introdução à Teoria dos

Números e Aritmética Transfinita

Secção 

1. Consideremos a relação  em    definida por

   se e só se       .

Mostre que se trata de uma relação de equivalência.

Resolução: (Reflexividade)    se e só se       .
(Simetria)                       
(Transtividade)                        . Então
               donde            

2. Mostre que   é uma ordem total em  e que para quaisquer      se tem:

(a)                (b) se     então               
(c)              (d) (     ·    ·  )    .
Resolução: Sendo     e     tem-se
           se e só se       .

Também se tem
             e             .

(a) Seja     Sabe-se que

                 e                 

Então
                        

                   

(b) A hipótese            diz que         . Tem-se

 2

                        

               
               
           
                   

(c) Tem-se                         

                  
(d) Tem-se
                         
               
               
           
                  

3. Mostre, por indução finita, que:

(a)                .
   

(b)                      .

(c)                 e deduza que       

   
(d)           
   

Resolução: (a) Para    é evidente. Assumindo que          

   

quer-se mostrar que                 , isto é, que
     

                  
    )          
  

Esta última expressão é equivalente a      , que é uma igualdade

 
      

verdadeira.
(b) Para    é evidente. Assumamos que se tem                    e
quer-se mostrar que                           , isto é, que

                      (1    )    ,

que é verdadeira.

(c) Para    é evidente. Assumamos que se tem             e quer-se

  
mostrar que               , isto é, que
  
 3

   

    
   

     

Esta expressão é equivalente a     , que é verdadeira.
   
A partir da igualdade anterior conclui-se              A desigualdade
vem de se ter

                                     

Daqui vem, multiplicando ambos os lados por , que    
   
(d) Para    é evidente. Assumamos que se tem           e quer-se
   
    
mostrar que           .
      
     
Tem-se 
     
   . Será que se tem
         
  
  
  ?
    

Será verdade se
         
  
   
                  
 

ou seja           . Esta expressão é equivalente a

                                


4. Mostre que é um número natural,   .
 
1ª resolução: Tem-se

             


                 
                

           
               .

2ª resolução: (por indução). Para    é evidente que     divide     .

Assumamos que     (isto é, existe         ) e mostremos que
 4

        ou seja que          Mas é imediato que
                  . 

5. Os números de Catalan são definidos por

 
  
  .
    

Mostre que:
              
(a)    (b)    .
         
  
Resolução: (a) por indução em . Para    vem que      
   
            
Suponhamos que  
             
                
Quer-se mostrar que   Vem que
                 

 
                              
                            
              
   
                    

como pretendido.
(b) Tem-se
           
      
               

6. Prove por indução que

      

Resposta: O caso    é imediato, pois         

Suponhamos, por hipótese, que       , isto é, existe         
  Quer-se mostrar que          isto é, que existe    
          Tem-se que
 5

               

           
               
         
               ,

como pretendido. 

7. Use o segundo principio de indução para mostrar que

                

Comece por mostrar que             

Resolução: É imediato que

                    

               

Usemos o segundo princípio de indução. Para    é evidente. Assumimos que

              , e
              

Ora
            
                         
                       
                               
                               
             
como pretendido. 

8. Define-se a "sucessão de Fibonacci" como    onde         

    e, em geral,      

(a) Mostre que        .

 

(b) Na alínea anterior foi usado que princípio de indução?
(c) Mostre que
mdc        

Resolução: (a) Tem-se que          e     

     .
 6

Assumimos que    se tem      e quer-se mostrar que      . Isso é

imediato pois

               

      
   
            
            

        
 
pois     
 
(b) O segundo princípio de indução.
(c) Por indução. Tem-se que mdc     mdc    Assumamos que se tem
mdc         e quer-se mostrar que mdc     ,   .
Suponhamos que existe    tal que    e    . Então        .
Mas então    e    logo     mdc(     , o que é absurdo. 

9. Prove

(a)     , (b)      ,

 
 

 


(c)   , (d)     .

  
   

  
 

Resolução: (a) Em         , basta fazer     .


 



(b) Derivando         em ordem a  vem que    






    . Fazendo      vem o resultado.






(c) Por indução. Para    é evidente. Assumimos que   . Então


 

 

        

+1 
     


 
    

d) Calculando    obtém-se    cujo termo central é     .


   

 
 7

Mas o termo central de

                     

   
   
                
    
   

é justamente       . Basta igualá-los.


 




10. Prove

(a)        


  

     

(b) Simplifique            .






Resolução: (a) Provamos por indução em .

            , assumindo por convenção que   



Para    temos



Para    temos            


  se     se     

   se        se   

Suponhamos que o resultado é válido para  e provemos que ainda é válido para   
Tem-se
 8

                

  
        
         

 
   
  

     

  
  

    

       


  

  

           






          


     

 


          

    


 


    
  
     


 
      

Note-se ainda que se    vem que

              

       
 

 


ficando assimprovado que        


  

       .

(b) Tem-se

                   

 
      


 
  

           

 
 

 

         

11. (a) Mostre que cada inteiro  tem uma expressão única na forma    onde
     .
(b) Mostre que o último par de algarismos (na representação decimal) de   
coincide com o último par de algarismos de  .
 9

(c) Seja    e  a representação decimal de um número (isto é,     ).

Mostre que a representação decimal de  tem a forma    (isto é,
      .
Resolução: (a) Temos que       , com     . Se      o resultado é
verdadeiro. Se    , escrevemos                  e é
verdade que          ,  .
(b) Note-se que           .
(c)                     .
Exemplo:        

12. (a) Seja    tal que        onde    e     . Mostre que

   .
(b) Mostre que o conjunto         é fechado para a multiplicação usual.
(c) Mostre que o conjunto         contém um primo.
(d) Mostre que o conjunto         contém um número infinito de primos.
Resolução: (a) Uma vez que  é ímpar então  tem de ser ímpar logo    .
(b) Com   pertencentes ao referido conjunto basta fazer
                  .

(c)        são exemplos.

(d) Suponhamos que o conjunto           só contém um número finito de
primos, digamos     
Sabemos por (c) que  contém primos; logo   . Seja         . Ora,
             Mas        é um produto de primos
ímpares, pelo que cada  ou tem a forma    ou tem a forma    , por (a). Se cada
 tivesse a forma    então  tem também de ter a forma     por (b), o que é
absurdo pois            não é dessa forma.
Logo um dos  tem a forma    ; mas este primo  não pode ser nenhum de
    . Para comprovar esta última afirmação, temos que
     
   com   ) e         ; suponhamos, por exemplo,

que    . Então          é divisível por  , o que é absurdo.
Como o absurdo vem de, no inicio, se ter suposto que  contém um número finito de
primos, conclu-se que essa quantidade é infinita. 

13. (a) Seja    tal que        onde    e     . Mostre que

   .
 10

(b) Mostre que o conjunto         é fechado para a multiplicação usual.

(c) Mostre que o conjunto         contém um primo.
(d) Mostre que o conjunto         contém um número infinito de primos.
Resolução: (a) O primo  tem de ser ímpar, logo admite uma das três formas
        .

Mas os números da forma    (  ) são múltiplos de  e portanto não podem ser

primos.
(b) Com   pertencentes ao referido conjunto basta fazer

                  

                  

(c)       são exemplos.

(d) É imediato pelo teorema de Dirichlet, tendo em conta que    .
Suponhamos que o conjunto           só contém um número finito de
primos, digamos     
Sabemos por (c) que  contém primos; logo   . Seja         . Ora,
             Mas        é um produto de primos
ímpares, pelo que cada  ou tem a forma    ou tem a forma    , por (a). Se cada
 tivesse a forma    então  tem também de ter a forma     por (b), o que é
absurdo pois            não é dessa forma.
Logo um dos  tem a forma    ; mas este primo  não pode ser nenhum de
    . Para comprovar esta última afirmação, temos que
     
   com   ) e         ; suponhamos, por exemplo,

que    . Então          é divisível por  , o que é absurdo.
Como o absurdo vem de, no inicio, se ter suposto que  contém um número finito de
primos, conclui-se que essa quantidade é infinita. 

14. É possível provar que todos os divisores de números da forma     são da

forma   . Assumindo este resultado, mostre que existe um número infinito de
primos da forma      ,   
Sugestão: supondo que, da forma     , só existem os primos      
considere o número        .
 11

Resolução: Suponhamos que existe apenas um número finito de primos      

dessa forma. Consideremos      )   que é da forma   . Os seus
divisores têm a mesma forma e, em particular, um dos primos anteriores (seja  , por
exemplo) divide  . Mas      ) logo      )  (   )  ) e
portanto    (absurdo). 

15. Seja  um número primo. Mostre que   ,    é divisível por  (este

resultado é conhecido como "pequeno teorema de Fermat")
Resolução: Por indução em , assumindo  fixo. Para    é evidente que       .
Assumindo que     ,       quer-se mostrar que         
Note-se que

        

 
     

  

              
 
 

   


Ora              e por hipótese de indução sabe-se que       . Então

        , como pretendido. 

16. (a) Mostre que todos os quadrados perfeitos são da forma  ou   .

(b) Mostre que    nunca é um quadrado perfeito.
Resolução: (a) Todos os números são da forma       ou   
Se    então         ;
se      então                     ;
se      então                       
(b) Dividindo    por  vem que          que não é de nenhuma das
formas vistas na alínea anterior. 

    
17. Mostre que os números da forma são naturais.

Resolução: Todos os números naturais são da forma          .
Estudemos os vários casos:
se    então 
  
      
se      então 
  
        
se      então 
  
        
 12

se      então 
  
        
se      então 
  
        
se      então 
  
        .
Alternativamente escrevamos
         
 .
 
No numerador há três naturais consecutivos, portanto um é múltiplo de . Encontramos
dois pares consecutivos o que implica que um é múltiplo de  e outro de . Portanto o
numerador é múltiplo de        

18. Prove, usando descida infinita, que se  não é um quadrado perfeito então  
não é um número racional.
Resolução: Suponhamos que     com    . Seja ainda    tal que
  
      ; então,      e     . Tem-se:
   
                         .


        
       

É claro que

      

porque       . Como o mesmo raciocínio pode ser repetido infinitas vezes,

obtém-se um absurdo porque todo o subconjunto de naturais admite elemento mínimo.
Logo  não pode ser um número racional. 

19. Considere     tais que    divide    . Mostre, usando descida

  
infinita, que é um quadrado perfeito.
  
   
Resolução: Suponha que   e que  não é um quadrado perfeito. Escrevamos
  
esta igualdade na forma                e assumamos que
    é uma solução desta equação. Por simetria podemos assumir que      .
Suponhamos que esta é a solução desta equação que miminiza    
Fixando  e  então  é uma das soluções da equação quadrática
         

Seja  a outra solução desta equação. Então

 13

                   

e portanto             

A partir da segunda igualdade conclui-se que   ; a primeira implica que    pois
de contrário      e  seria um quadrado perfeito, o que contradiz a hipótese. Tem-
se também que    pois se fosse negativo viria que      donde

               

Mas
             
                       

Portanto    Por fim tem-se que

        
        
  

Daqui se conclui que    ) é solução da equação e que        contrariando a

minimalidade de    . Portanto  é um quadrado perfeito. 
 14

Secção 2

1. Seja      , ímpar. Mostre que existem      tais que      

Resolução: Reparamos que se    for ímpar com    onde       , então
existem sempre     tais que      e     . Basta fazer        e
 
supor      e     . Vem que   e  . Logo,      . A
 
hipótese de  ser ímpar assegura que  e  sejam naturais. 

2. Sejam    e   .
(a) Se  for ímpar, mostre que
              .
(b) Mostre que
              .
(c) Use (b) para mostrar que se    então       .
Resolução: (a) (b), imediatas, fazendo a divisão, ou aplicando a regra de Ruffini.
(c) Se    então existe    tal que    e

                     

donde se conclui que       . 

3. Sejam     ,   , tais que     . Mostre que  é par e        .

Resolução: Se   ,       é primo, então  tem de ser par pois, de contrário,
   seria par e maior que ; logo não seria primo. Suponhamos agora, por absurdo,
que  admite um divisor primo   . Então    com   , e viria que
               , com    .

Como  é ímpar, por 2(a) vem que       . Tendo em conta que         

conclui-se que    não pode ser primo. Portanto  tem de ser uma potência de  

4. Sejam        tais que     . Mostre que    e   .

Resolução: Suponha-se que   ,       é primo, mas que   . Por 2(b)     
é um seu factor e logo não é primo. Portanto o número tem de ser da forma   
Suponhamos, por absurdo, que  não é primo, isto é,    com    . Viria então que
 15

             

   
        )
 
não é primo. 

5. Calcular o máximo divisor comum dos seguintes pares de números usando o

algoritmo de Euclides:
(a)       (b)      
e escrever  na forma      onde    .
Resolução: (a) mdc   mdc       
Pelo algoritmo de Euclides vem que
      
      
      

Portanto   mdc .

Usando o método no sentido contrário temos

                      

b) Pelo algoritmo de Euclides vem que

      
      
      
      
      

logo mdc    Usando o método no sentido contrário temos

                        
                   
                   

Portanto          

6. Seja   . (i) Mostre que mdc     .

(ii) Se  for ímpar, mostre que   mdc     ; se  for par, mostre que
  mdc     .
Resolução: (i) Tendo em conta que    e      vem que         
 16

(ii) Seja  tal que    e     . Então     2    2 Se  for ímpar

         ; se  é par vem que   . 

7. Sejam    . Se mdc   , mostre que:

(i)   mdc         (ii) se    e    então   
Resolução: (i) Como      e      então

           e           

e daqui vem que   mdc   mdc 

Se  é ímpar então mdc(    e portanto   mdc   , donde   ;
Se  é par então    e portanto   mdc     mdc   . Logo    e   .
(ii) se    e    existem     tais que      . De    e mdc   
conclui-se que    donde existe    tal que   . Mas então vem que    
   e   . 

8. Seja   . Mostre que mdc       .

Basta notar que se      e      então             , logo
         Mas então           .
Alternativamente é imediato que   . Podemos fazer, pelo algoritmo de Euclides:
             e         ;
           e       ;
         e     ;
       e mdc(       ;
ou podemos usar a fórmula de Bézout. Como é possível escrever
                   ,

tem-se o resultado. 

9. Seja   . Mostre que   mdc         .

Resolução: Notemos que

                           .

Logo    e portanto    Mas então         . 

 17

10. Sejam     tais que    . Mostre que   .

Resolução: Escrevendo      e      (em que estes primos são todos
os que aparecem nas decomposições de  e ) vem que

           donde      ,     

e portanto    ,     . Então   
Alternativamente, sem usar explicitamente a unicidade de factorização, seja
  mdc  escreve-se     e     onde     são primos entre si. Existem
    tais que      pelo que          . Por hipótese, existe   
tal que      logo            e   ,   . Logo   ,    e   
.

11. Encontre     tais que    mas   .

Resolução:      . Tem-se        mas    

12. Sejam     . Mostre, sem utilizar a unicidade de factorização, que se

mdc    então mdc      .
Resolução: De mdc    conclui-se que existem     tais que      e
portanto        Desenvolvendo vem que      , ou seja existem
     tais que       . Em particular, mdc    .
Tem-se também que          Vem então que        
          e portanto mdc     . 

13. Se    então   mdc  mdc 

Resolução: Escrevemos            e      (em que estes
primos são todos os primos que aparecem nas decomposições de   e  ).
A hipótese diz-nos que       ,     .
min   min   min  
Ora mdc     e mdc    min   e

min  min  

mdc mdc    min  min   

Em todos os casos tem-se que   min     min   

Alternativamente, sabe-se que existem        tais que mdc      e
mdc       Tendo em conta que    existe    tal que    . Logo
mdc  mdc                 
                 

donde   mdc  mdc , como pretendido. 

 18

14. Sejam     . Mostre que mdc     mdc  .

Resolução: Escrevemos            donde

           .

Tem-se que

min ,  min , 

mdc       min , 
 min ,   min , 
    min , }
min ,  min , 
   min ,    mdc  ,

como pretendido. 

15. Sejam       e seja     . Mostre que mdc   mdc 

Resolução: Seja   mdc . Como    e    vem que    logo   mdc  

16. Se    , mostre que mdc   mdc     mdc   mmc .

Resolução: Se    e    então     . Reciprocamente      e    implica que
        . Logo os divisores são os mesmos e consequentemente os respectivos
máximos divisores comuns.
Vamos agora ver que   mdc   mmc  é igual a mdc   .
Em primeiro lugar, se   mdc  então    e     com mdc    . Sabe-se
   
que mmc       . Tem-se também que
 
  mdc   mmc   mdc        mdc     

donde    . Reciprocamente        mmc               . De

forma análoga       mmc             . Mas mdc    
implica que mdc       donde existem   tais que       . Vem então que
        e portanto    . 

17. Seja   . Mostre que:

(a) ( ímpar)       (b) ( ímpar   )      ,
(c)      (d)        .
Resolução: (a) Se  é ímpar então          é par sendo que um dos
factores é divisível por  e o outro por . Logo  divide   
 19

(b) Se  é ímpar então          é par sendo que um dos factores é

divisível por  e o outro por . Consideremos os três números       . Um tem
de ser divisível por . Mas como    então      ou     .
Então         .
(c) Sabe-se que                       
Se                      e     
Se                     e     
Se              
              e     
      

Se                            e     
     

Se                            e     
      

Se                            e     
     
Se      tem-se                  e     
Portanto     . Quer-se agora ver que      Ora

                        .

Sabe-se que um dos três números        é divisível por  e também que pelo
menos um deles é divisível por . Como           e     vem
que     .
(d) Tem-se           .
• Sabemos (pela resolução da alínea anterior) que
                .

• Vem ainda que        . Se    então          

Se    então      e      um dos quais é divisível por . Portanto

             
• Finalmente  divide algum dos números       .
Se    então          
Se      então      para algum    e    9            
donde    é divisível por 
 20

Se      então      para algum    e               

donde    é divisível por  

18. Seja    tal que    é o quadrado de um inteiro. Mostre que   .

Resolução: De      deduz-se que           .
Logo            e     . Mas             
Vem então que    e       . 

19. Seja   ,   , tal que    é primo. Mostre que     .

Resolução: Como  e    são primos ímpares vem que     . Note-se que  divide
algum dos três números consecutivos       . Mas não pode dividir  nem   
porque são primos e   . Então     
De      e      conclui-se que      

20. Seja    tal que    é o quadrado de um inteiro. Mostre que   .
Resolução: Tem-se que      donde     . Notemos que  não pode ser 
porque de contrário existiria  tal que    (absurdo); de maneira análoga   
pois de contrário existiria  tal que        (absurdo).
Temos então que       , com    . Temos que mdc       
Mas se fosse  o número  seria par, o que não acontece. É agora imediato que    e
   têm de ser primos Logo      é a decomposição de  em factores
primos que sabemos ser única. Então      e          e   
(absurdo), ou      e          e    

21. Calcule
          e        

para    e   .

Resolução: Tem-se
      ,     
         
           
logo            
                
 21

                

                

                     ;

                      
                        
                         

22. Mostre que:

(a)   é ímpar   é um quadrado perfeito.
(b) se  é livre de quadrados (isto é,        em que todos os  são distintos e
elevados à potência ) então     , onde  é o número de divisores primos de .
Resolução: (a) Sabe-se que se     , ( ,   primos distintos e       )
então      




Seja  ímpar e     . Então

   (     é ímpar      são pares
        
         é um quadrado.

(b)    (    , onde       . Então      

23. Mostre que 

  
 

 

Resolução: Comecemos por notar que      ; por esse motivo o conjunto dos
divisores de ,     , pode também ser escrito na forma    . Vem então

 
 

       
   
 
 
  


24. Determine    da forma     tal que     Note que  
   é a sua decomposição em factores primos.
Resolução: Temos
                               
 22

Ora                e        donde    e   . Então

          

25. Seja  uma valuação. Prove que:

         ,           
            ,           .
Resolução: (a) Sabe-se que         donde
                  

e portanto   . Por outro lado, de

                         

vem que     
(b) Sabe-se que         donde
                   

(c) Por indução. Se    é trivial. Suponhamos que se tem       para algum
   Então                         
(d) Tem-se
              ,

e daqui vem o resultado. 

26 Seja   a valuação -ádica. Prove que:

(a            



(b              



(c)    
                 

 

Resolução: (a)                          

 
   

(b) Se    vem que                  

  
   
 
Se      sabe-se que       . Então aplicando valuações na igualdade

           

   

 23

vem

             

   


donde

                          

   


e daqui vem que

                          

 
 

        



(c)                  

  
 
   
                             
    ,
   
como pretendido. 

27 Sendo   a valuação -ádica, prove que

  
               ,

  
                para       

        
Resolução: (a) Usando a fórmula    vem que     
 
Escrevendo  em base  vem que

 =                ,

logo      e temos o resultado.

   
(b) Usando a fórmula    vem que

     
    


Escrevendo  em base  vem que                 , logo      e

temos o resultado. 
 24

28. (a) Quantos zeros existem na "cauda" de  ?

(b) Determine a maior potência de  que divide 
Resolução: (a) Basta calcular

5                    

  
  

(b) Seguindo um raciocinio semelhante ao que foi usado para calcular a maior potência
de  que divide  temos de calcular

           

 


 
 25

Secção 3

1. Encontre a solução geral,       (se existir) de cada uma das equações
seguintes. Indique quais destas soluções são não-negativas.
(a)      (b)     
(c)      (d)     
(e)      (f)     
(g)       (h)     
Resolução: Seja uma equação      e   mdc     .
   
Então a solução é da forma             
   
(a) Temos            mdc          
   e       
  

A solução é da forma 
           
          
As soluções não-negativas são obtidas para    verificando

   
         e         , isto é,    
   
logo não há soluções.
(b) Temos            mdc            donde     e    e
      

  
A solução é da forma 
         
           
 
  
As soluções não-negativas são obtidas para    verificando

  
         e          , isto é,       .
  
Há soluções quando    (que é     ) e    (que é     ).
(c) Temos que        mdc               donde    e
   e       

A solução é da forma 
    
    
As soluções não-negativas são obtidas para    verificando
 26

  
        e         , isto é,   .
  

As primeiras soluções são   (para   ),   (para    , etc.
(d) Temos       mdc    . Mas  /  logo não há soluções.
(e) Tem-se           mdc                   donde
    e    . Tem-se ainda que       

A solução é da forma 
     
     
As soluções não-negativas são obtidas para    verificando

 
          e           , isto é,    .
 

As primeiras soluções são   (para    ),   (para    , etc.
(f) Tem-se          mdc              donde    e
   . Tem-se ainda que       

A solução é da forma 
    
     
As soluções não-negativas são obtidas para

 
             e              .
 
logo há soluções para     e    , que são   e  , respectivamente.
(g) Tem-se que            mdc          0      (  
donde     e    . Tem-se ainda que        

A solução é da forma 
    
    
As soluções não-negativas são obtidas para

 
           e           .
 
Portanto há soluções para   . As primeiras soluções são   (para   ),  
(para   , etc.
(h) Temos       mdc   . Mas  /  logo não há soluções. 

2. Quando o Carlos foi levantar o cheque ao balcão, o funcionário enganou-se e

confundiu o número de euros com o de cêntimos. O Carlos só se deu conta desse facto
 27

quando, depois de ter gasto 68 cêntimos se deu conta de que tinha na conta o dobro do
montante original. Qual é o menor valor que podia ter sido escrito no cheque?
Resolução: Seja  o número de euros e  o de cêntimos,      . A relação
proposta no problema é dada pela igualdade
        ,

que também se pode escrever na forma      

Tem-se           mdc                donde
   e   . Tem-se ainda que       
   
Sabemos que a solução é da forma              Neste caso é
   

     
     

As soluções não-negativas (    ) são obtidas para

     (ou seja   0   
   e
     (ou seja      
  )
Mas também se tem que    , donde
                e
               
Portanto     é solução.
E, com efeito,                   e verifica-se que
            . 

3. Encontre todos os ternos Pitagóricos (primitivos ou não)       tais que

    .
Resolução: Os ternos pitagóricos primitivos são da forma
     (ímpar),    (par) e      (ímpar).

Tendo em conta a igualdade      temos de escrever       e  como

soma de dois quadrados e deduzir  e  .

• 11               ( não integra nenhum terno pitagórico).

•                (portanto se         ).

•                ( não integra nenhum terno pitagórico).
•                     (portanto se         ).
 28

•                     ( não integra nenhum terno pitagórico).

Os ternos pitagóricos primitivos com      são    e   .
E quanto a ternos não-primitivos? Um estudo semelhante mostra que se      só há
um único terno pitagórico primitivo, o    (os  nesse intervalo são analisados por
poderem dar origem a ternos pitagóricos, não primitivos, tal que     ). E, com
efeito, os seus múltiplos       e    não são primitivos, mas têm 
no intervalo pretendido. 

4. Mostre que nem  nem  podem fazer parte de um terno pitagórico enquanto
   é o único terno pitagórico que contém  ou .

Resolução: Os casos em que      ou  são descartados rapidamente. Basta

enumerar todas as possibilidades e ver que não existe nenhum terno pitagórico.

Suponhamos agora, sem perda de generalidade, que    ou    ou    ou   .

Caso em que   . Se  fizesse parte de um terno pitagórico poderíamos escrever

       donde        e portanto       . De      conclui-se que
    , isto é,     . Mas            , o que é absurdo. A hipótese
     implica que      donde       ou       (absurdo, pois     ).

Caso em que   . Se  fizesse parte de um terno pitagórico poderíamos escrever

       donde        e portanto       . Se      vem que
      ou . Suponhamos que     . Então               e
não existe solução.
Suponhamos que      . Então            , o que é absurdo.
Suponhamos, por fim, que      . Então                    
donde vem    , o que é absurdo.
A hipótese     4 implica que: (i)      donde       (absurdo, pois
    ), ou (ii)      donde vem       (absurdo) ou      , o que
implica    (absurdo), ou (iii)      donde vem       (as restantes
hipóteses implicam que uma das variáveis seja nula). Mas então         
(absurdo).

Caso em que   . Um estudo semelhante ao que foi visto nos casos anteriores pode ser
feito. Só vamos examinar alguns casos.
Se  fizesse parte de um terno pitagórico poderíamos escrever        e, como
   , tem de ser da forma     . Não pode ser      porque de contrário ter-se-
ia         que só é possível se   
Se      então                            . E com
efeito (   é um terno pitagórico.
 29

Caso em que   . De novo só vamos examinar alguns casos. Se  fizesse parte de um

terno pitagórico poderíamos escrever        e, como    , tem de ser da forma
          ou     . Não pode ser      porque de contrário ter-se-ia
        que só é possível se   
(i)     . Então                           , não tem
solução nos naturais.
(ii)      Então                         , não tem
solução nos naturais.
(iii)      Então                         , não tem
solução nos naturais. 

5. Seja    um terno Pitagórico primitivo. Mostre que    e que    .

Resolução: A primeira relação corresponde a afirmar que    ou    (mas não ambos,
porque senão o terno não seria primitivo). Suponhamos então que  e  não são
múltiplos de . Seja          . Então

                   .

Note-se agora que um qualquer número é da forma     ou    Os seus

quadrados são, respectivamente, da forma             
         e                 .
Consequentemente como     é da forma   , não pode ser um quadrado
perfeito. Daqui vem um absurdo; logo ou , ou  , é múltiplo de .
Suponhamos agora que    ou    (mas não ambos, porque senão o terno não seria
primitivo). Se um deles for divisível por  está provado. Suponhamos que tal não ocorre
e examinemos os vários casos:
(i)          . Então                   .
(ii)          . Então                   .
Em ambos os casos não há terno pitagórico porque nenhum quadrado perfeito é da
forma    ou    (pode-se verificar de forma análoga ao que acima foi feito para
o número ).
(iii)          . Então                  .
Se o quadrado pitagórico existir   é divisível por  e portanto  também; daqui vem
que    . 

6. Seja             a sucessão de Fibonacci definida por

               .

(a) Mostre, por indução, as igualdades:

 30

(i)        

(ii)   

  
(b) Mostre que

        

é um terno pitagórico.
Resolução: (a) Vai-se provar que        .
Por indução em    . Para    temos        , que é verdadeira por
indução: para    temos                  . Considere-se que é válida
para     , isto é, que        . Então
                
                  ,

como pretendido. Suponhamos a hipótese verificada para     . Para     

temos
                
                ,

como pretendido
Vai-se agora provar que   

  , por indução em . Para    vem
          . Seja a expressão válida para   , isto é,   

  .
Usando a propriedade anterior (fazendo       ) vem que

              

         

        
  
  .

(b) Quer-se ver que


         

,

isto é, usando a propriedade anterior no segundo membro,

 
        
 
    

ou seja
 
       

   

  

7. Um triângulo rectângulo cujos lados têm comprimentos dados pelos elementos de

um terno pitagórico primitivo    designa-se por triângulo pitagórico. Sabe-se
que é possível escrever   e  na forma
 31

             

em que    ,   , são primos entre si e com paridades opostas.

(a) Mostre que a área de um triângulo pitagórico é dada por     
(b) Mostre que a área de um triângulo pitagórico é divisível por .
(c) Considere-se a circunferência inscrita no interior de um triângulo pitagórico.
Mostre que o seu raio é um número natural.
Resolução: (a) A área  de um triângulo rectângulo é dada pela metade do produto dos
catetos, ou seja
    
       
 

(b) Tem-se que        em que   têm paridades opostas. Portanto um de
entre eles é divisível por  Agora quanto à divisibilidade por  Se  ou  forem
divisiveis por , o resultado é imediato. Vamos agora supor que não é o caso.
Se           então                  . De
forma análoga, se           então               
   . Mas já foi visto (exercício 5) que nenhum quadrado perfeito é desta forma e
portanto   não podem ser desta forma. Finalmente, considere-se que      e
     (ou      e     ) então          e, portanto  divide
  . Em conclusão  é divisível por  e por  ou seja por 
(c)
 32

Por um lado tem-se que a área é dada por     . Designando o centro da
circunferência inscrita por , também se tem que a área é a soma das áreas dos
  
triângulos   e  ou seja  e . Então
  
       
        
   
          
      

  
          

         
     

que é um número natural. 

 33

Secção 4

1. Determine o resto quando se divide

(a)  por , (b)  por .
Resolução: (a) Temos de calcular  mod . Mas             e
portanto   40 mod  De forma semelhante 40         . Portanto
   mod . De novo          e portanto    mod 
(b) Temos de calcular  mod . Mas 41       e portanto    mod  De
forma semelhante       . Ora        e portanto vem que
   mod . Tem-se que              e portanto    mod .
Notar que seria mais rápido fazer    mod        mod . Como
      vem que     mod , isto é,    mod  

2. Qual é o resto de        quando se divide por ?

Resolução: Basta verificar que        mod           mod 
         mod  e          mod . Então
      
                           
                            mod 
                              mod 

Finalmente          mod  

3. Mostre que se    mod  então mdc   mdc 

Resolução: De    mod  vem que     , para algum   .
Seja    . Então    e   . Então       .
Reciprocamente seja    . Então    e   . Então       .
Conclui-se que um número é divisor de  e  se e só se é divisor de  e . Em particular
os máximos divisores comuns têm de coincidir. 

4. Quais das seguintes afirmações são correctas?

(a)    mod      mod ,      
(b) Seja      . Tem-se    mod      mod 

(c)    mod      mod 


 
 34

(d)    mod      mod 

 
   
(e)        mod    
(f)    mod        

(g)    mod        mod 

 
   
(h)    mod  e         mod 
(i)    mod      mod      mod mmc 
Resolução: (a)    mod       . Se    então          mod 
(b) Contra-exemplo: seja    e   . Tem-se que       mod  mas não é
verdade que se tenha    mod 

(c) Vem    mod 

 
           
   
     e portanto    mod .

(d) Vem que    mod 

 
   
   

        mod 
 

   
(e) Se    então      e       
(f) Contra-exemplo: sejam       e   . Tem-se    mod  mas   

(g)    mod 
 
          
   
 
Tem-se que   donde     
   
(h)    mod             . Mas como     vem
imediatamente que          mod 
(i)    mod      mod               
          
Notando que  

    vem que

mmc             mod mmc .



 

5. Mostre que nenhum número natural cuja soma dos algarismos seja  pode ser um
quadrado ou um cubo.
Resolução: Sabe-se que um qualquer quadrado verifica       mod  e que um
qualquer cubo verifica      mod  Se  for um número cuja soma dos algarismos
for  vem que    mod , e nenhum quadrado ou cubo assume este valor. 
 35

6. Mostre que:
(a)      mod  (b)      mod .
Resolução: (a)                mod .
(b) Tendo em conta que    mod  e    mod  vem que
       mod 
Mas                   mod  donde as potências de  mod  se
repetem de  em  Note-se agora que    mod .
Tem-se também que          mod  donde as potências de  mod  se
repetem de  em  Note-se agora que    mod .Então a expressão anterior é
congruente com    mod , isto é, com
       mod        mod    mod  

7. Para    mostre que

(a)         (b)      
(c)       (d)     
Resolução: (a) Quer-se provar        mod  Visto que     e    
esta expressão é equivalente a         mod            mod 
Ora                mod . Notar que   ( )     mod 
(b) Quer-se ver que      mod  Visto que 4     mod  esta
expressão é equivalente a        mod         mod 
(c) Quer-se ver que      mod  Visto que      mod  esta
expressão é equivalente a         mod          
(d) Quer-se ver que      mod  Visto que 2     mod  esta
expressão é equivalente a                mod  

8. (a) Suponha que  

  mod . Mostre que    não é um cubo mod .
(b) Suponha que  
  mod . Mostre que    não é um cubo mod .
Resolução: (a) Os cubos mod  são             ou seja tomam valores
no conjunto       Por sua vez as quartas potências tomam valores no
conjunto    Portanto    mod  só pode tomar valores no conjunto
         mod , isto é, no conjunto     . Como      a
expressão    nunca pode ser um cubo.
(b) Os cubos mod  são       ou seja tomam valores no conjunto    . As
segundas potências são       ou seja tomam valores no conjunto   
 36

Portanto    mod  só pode tomar valores no conjunto          mod

, isto é, no conjunto     . Como      a expressão    nunca pode
ser um cubo. 

9. Escolhendo módulos apropriados mostre que não existem soluções inteiras das
equações:
(a)            , (b)             .
Resolução: (a), (b) As potências sextas mod  só tomam valores no conjunto   
    mod  Portanto          mod           
Repare-se que                   e    mod ;
daqui vem que   1 mod .
Agora vem que      mod  e que      mod  estão fora do conjunto. 

10. Seja          Determine os inversos (quando existem) dos
elementos de  para
(a)    (b)    (c)   
Resolução: (a) Os elementos invertíveis em 10 são     e os seus inversos são
           

(b) Todos os elementos de 1 são invertíveis e os seus inversos são

                 

(c) Os elementos invertíveis em 1 são     e os seus inversos são
            

11. (a) Calcule  mod . Sugestão: note que     

(b) Calcule  mod . Sugestão: note que     
Resolução: (a) Tem-se      donde      mod        mod 
É evidente que    mod . Daqui vem que

                           mod 

(b) Tem-se      donde       mod          mod 

Daqui vem que    pois      mod  
 37

12. Seja  primo ímpar e  verificando       . Então

(a)       mod , (b)     mod        .

  
 
Resolução: (a) Em primeiro lugar tem-se que

 
          
 
      

Portanto

         




Mas       mod  donde

                   mod 

Então        mod  Como      vem que    e portanto
    Então        mod .



(b) Tendo em conta que       é imediato a partir de (a). Notar

  
  
ainda que       
 

 

13. Aplique o teorema de Lucas para calcular:

(a)  mod  (b)  mod 

 
 

Resolução: (a) Sabemos que                e               .

Então  mod       mod        mod    mod .
    
    
(b) Sabemos que
                   e                   .
Então

 mod        mod    mod 11),

  1  8 
     

o qual é imediato porque    





14. (a) Demonstre o critério de divisibilidade por : Seja         
         e              . Então
 38

 é divisível por  se e só se                 

(b) Prove que    mod  e que  

  mod 
Resolução: (a) Se  é divisível por  existe    tal que          
       , isto é,

                          .

Considerando agora
             
                         
                         
               

é imediato que                 

Reciprocamente suponhamos que                  Então existe
   tal que                 . Mas
                -1        )  
    )      

e portanto   
(b) Usando o critério anterior ter-se-á    mod  sse       , o que é verdade.
De forma análoga     mod  sse       ; por seu lado  
  mod  sse
      , o que é verdade. 
 39

Secção 5

1. (a) Se mdc    mostre que o conjunto

            

é um SRC mod .

(b) Um conjunto de quaisquer  inteiros consecutivos é um   mod .
Resolução: (a) Só temos de ver que         mod , com         .
Supondo que        mod  vem que    mod        mod .
Como     mod  conclui-se que    (mod  donde   , tendo em conta que
        , o que é absurdo.
(b) Basta fazer    e   qualquer em (a). 

2. Mostre que           é um   mod  mas que

          não é.
Resolução: Como  é uma raiz primitiva mod  vem que           é um
 mod . Alternativamente podemos verificar que          são todos
distintos mod 11; como são onze elementos formam  mod .
O conjunto           não é pois    mod     mod , etc. 

3. (a) Calcule     

(b) No conjunto      determine os  números coprimos com 
(b) No conjunto      determine os  números coprimos com 
Resolução: (a)               ;
             ;
                          ;
                          
               ;
                     
(b)        
(c)             

4. Sejam     e sejam   mdc  e   mmc . Mostre que


  

 40

Resolução: 1ª resolução: Tem-se que

mdc  
         
mdc  

2ª resolução. Sejam        todos os primos que surgem nas factorizações de  e .

Então

   e    e       

   
max   min  

   

Tem-se      e portanto      

 
max   max  min  

 

Por outro lado                
   

   

Só falta notar que max     min            

5. Mostre que se      em que  e    são primos ímpares, se tem

    .
Resolução: Visto que    é primo ímpar vem que mdc(      (por Bézout, por
exemplo) Então

          

Por outro lado            e é imediato que mdc(   . Vem então:

               

6. Seja      . Mostre que



 


mdc

Resolução: Nos primeiros   números encontramos          e nos números


 

seguintes encontramos            , todos coprimos com . Basta notar que se 



e  são coprimos existem     tais que      (identidade de Bézout) Somando

     vem que                        , logo
 
existem     tais que          Notar que o termo central nunca conta. A
soma de todos estes números é

                        

 41

7. Sabemos que      se   . Mostre que se   ,   , é tal que

     então   .
Resolução: 1ª resolução:  conta os números        tais que    . Se
eles são    então isso significa que todos os números entre  e    não dividem 
(com a excepção óbvia de ). Se  não tem divisores inferiores a  para além do , tem
forçosamente de ser primo.
2ª resolução: Seja     e suponhamos que    isto é,    . Então
               se e só se   
Suponhamos agora que    Então

          2           

    2           2     
          
  
   
         
   ,


com a última desigualdade justificada por se ter      (  ), e vem um
absurdo (estamos a assumir que existem factores  e  . 

8. Determine todas as soluções das equações:

(a)    (b)    (c)   
(d)    (e)   

Resolução: Suponhamos que     , com    e os  são primos distintos. Então





      


(


(a) Suponhamos que   . Então    é uma solução. Suponhamos que   1.

Pela fórmula acima então     , para todos os . Portanto    é o único factor
primo de  e portanto    . Como se tem que       vem que   .
Portanto    e a equação inicial tem apenas as soluções  e 
(b) Suponhamos que   . Então   1. Tendo em conta  sabemos que
     . Portanto      ou     , donde    ou    Escrevamos
    . Sabe-se que           
Se    vem que           e   
Se    vem que    e portanto   . Vem que              e
   ou   
Vem então que     ou 
 42

(c) Suponhamos que   . Tendo em conta  sabemos que      , isto é,
     ou     , o que implica que    (caso excluído porque  não é primo)
ou    Então    e       é impossível.
Alternativamente sabe-se que  é ímpar se e só se    , caso em que   .
Portanto a equação    não pode ter soluções.
(d) Suponhamos que   , o que implica que   1. Tendo em conta  sabemos
que      , isto é,      ou      ou     , o que implica que
    ou  Portanto      . É evidente que      1 e   . Examinemos
estes casos um a um.
(i) Se    então            implica que     
Se    vem     o que é absurdo.
Se    vem     donde    ou   .
Logo    ou    são solução.
(ii) Se    então       
Se    vem        donde   ; se    vem     donde   .
Então   1 ou   

(e) Temos que     donde          

 

 

Sabe-se que      donde         ou . Então       ou . É claro



que o  se exclui e sendo assim       , para alguns        É evidente que

         e   . Examinemos todos estes casos um a um.
(i) se    então    a menos que      e se tenha    Logo    
são soluções.
(ii) Seja então    e       Se    vem que

        
  
  

e vêm as soluções          e      

Se    vem que

        
  
  

e vêm as soluções       e     

As soluções são         

9. Seja    e suponha que     onde  é ímpar. Se  tem   

factores primos ímpares distintos, mostre que    .
 43

Encontre um exemplo concreto de    tal que    .

Resolução: Sabe-se que    11  com       distintos e ímpares.
Seja   . Tem-se que        11         
  
   11  
     . Logo     donde         
é par é par
Se    um cálculo semelhante permite obter o mesmo resultado.
Quanto ao exemplo: considere-se, por exemplo,      . Tem-se

                         .

Aqui       e        . 

10. Seja   . Mostre que   

 se  é ímpar
 se  e par

Resolução: Podemos usar a relação    , onde    .

(i) Se  for ímpar tem-se    . Vem então que

  1
      
  1

pois 1  2  

(ii) Se  for par vem que
  
       
  

11. Sejam     , distintos, e suponha que       (    ). Mostre que

    
      
     
      

Resolução: Se       então
 44

           

           
   
  
           
  
  
      
      
  
      

como pretendido. 

12. (a) Prove o teorema de Daniel Dias da Silva: "Seja      onde   

são tais que mdc      se   . Então

 
    mod ."
   
   

(b) Sejam     tais que mdc   . Prove que      mod .

Resolução: Seja           Então vem (usando várias vezes o
teorema de Euler) que
  
e  
     
           
 
logo      .
   
   
Como o mesmo se passa com     conclui-se que
 
   ,
   
          

que é o resultado pretendido.

 
(b) Tem-se          mod        mod  

13. (a) Prove que se  for composto então

     .

(b) Para    prove que

         

Sugestão: para    use (a).

Resolução: (a) Seja              com   
 45

Escrevamos    . Tem-se    donde        


e portanto   ; vem então que

   
Daqui se conclui que   
   

  




Sabe-se que              

   
pois todos os
   
restantes factores são inferiores a  Daqui vem que

         ,

 
 

como pretendido. Notar que se    , com  primo, o limite superior é atingido.

(b) Esta relação é verdadeira para    pois
                    

Para   , sabe-se que, usando (a),

                  

                        

como pretendido. 


14 Mostre que existe uma infinidade de números naturais tais que   


Resolução: Os  têm de ser multiplos de , pois de contrário a expressão não faria

sentido. Suponhamos que     , onde     e  um primo diferente de . Tem-se
(    ( (         
  
Queremos que se tenha        . Mas         
 
implica que se tenha                   .
Consideremos então os naturais da forma    com     Tem-se, com efeito, que
 
(    ( (              


15. (a) Sendo     tais que     , mostre que se mdc    então

mdc     

(b) Conclua que para     é par.

 46

Resolução: (a) Se mdc    existem     tais que     . Mas então

           donde      
Reciprocamente se mdc      existem      tais que       
então    (      .
Alternativamente o conjunto dos divisores de  e  coincide com o dos divisores de  e
  . Portanto o máximo divisor comum tem de ser o mesmo.
(b) Para    podemos agrupar os números coprimos com  em pares     e
portanto  é par. Se    então    e      

16. Se  for um primo e    mostre que         

Resolução:              , pois mdc     
Esta expressão simplifica-se para     2 
Sabe-se que    , usando a propriedade     , com   
Vem então que            , como pretendido. 
 47

Secção 6

1. Encontre o resto da divisão de  por  (note que  é primo).
Resolução: Sabe-se que       mod  que neste caso se traduz por    
mod . Sabe-se que     mod . Daqui vem que
    mod         mod  e portanto    mod . 

2. Seja  um primo ímpar. Mostre que

       mod           

Resolução: Quer-se ver que        mod 

 .

É claro que        mod  e também que        mod  Vem então que

                 mod .

É obvio que            donde 

         Tendo em conta que
    conclui-se que
 

       mod .
  



3. Usando o teorema de Wilson mostre que se  é um primo ímpar, então


                mod .

Resolução: Sabe-se que           mod  e daqui vem que

      mod        mod          mod 

Então

                                         mod 

Temos que
                         

                   mod 

Daqui vem que

  
                         mod 
+
                 mod ,

como pretendido. 
 48

4. Seja   . Mostre que      mod  e       mod 

Resolução: É imediato que
      mod           mod        mod .

De forma análoga
      mod             mod         mod . 

5. Mostre que          mod ; deduza que          mod

 e que     mod . Mostre ainda que     mod .
Resolução: Tem-se que            mod  e
                                     mod 
Sabe-se que     mod  pelo teorema de Wilson. Mas         
donde
    mod               mod 
     mod 

Note-se agora que     . Sabe-se que     mod . Usando o resultado:
"Sejam     tais que mdc    Se    mod  e    mod  então   
mod " vem que     mod  

6. (a) Mostre que    mod  não implica que    mod .

(b) Mostre que    mod , com       , implica   
mod .
Resolução: (a)    mod  mas não se tem    mod .
(b) Pelo teorema de Fermat    mod  e    mod . Então    mod  é
equivalente a    mod  

7. (a) Fazendo cálculos, mostre que  

  mod  e conclua, pelo teorema de
Fermat, que  não é primo.
(b) Fazendo cálculos, mostre que  
  mod  e conclua, pelo teorema de
Fermat, que  não é primo.
(c) Fazendo cálculos, mostre que    mod . Mostre que, no entanto, 
não é primo.
Resolução: (a)   ( ) mod . Tem-se que      mod , donde
                   mod 
 49

(b)         mod .

Tem-se que    mod ,    mod       mod 
     mod       mod       mod 
Tendo em conta que      mod  conclui-se que 0   mod .
Vem então que                  mod 
Se  fosse primo viria que    mod . Como não se passa, não é primo.
(c) Tem-se que    mod  e    mod  donde    mod 
Vem então que                mod 
No entanto não é primo; basta testar por todos os primos     
Alternativamente        mod  e portanto  é divisível por  

8. Seja    tal que mdc   . Mostre que     mod .

Resolução: Sabemos que      donde mdc    implica que também se
tem mdc   mdc    Então     mod  e     mod . Daqui vem
que     mod  e     mod  donde se conclui que     mod .
Usou-se o resultado: Sejam   tais que     Se    mod  e    mod 
então    mod  

9. Use o teorema de Fermat para mostrar que

  
   
  

Resolução. Comecemos por verificar que

       
   
   

Só é preciso mostrar que        mod  e para tal basta mostrar que
       mod  e        mod  Temos que
               mod ,

onde se usou que    mod ; por outro lado

               mod ,

onde se usou que    mod  

10. (a) Use o teorema de Fermat para determinar o algarismo das unidades de  .
 50

(b) Quais são os últimos três algarismos de  ?

(sugestão: comece por provar que          mod ).
Resolução: (a) Calculemos      . Tendo em conta que    vem que
     mod . O algarismo das unidades é 
(b) 1º método:
             (mod  e portanto   .
Notar que a sugestão se pode provar facilmente por indução e que   
Temos que       . Então          fazendo as
contas directamente com os algarismos (ou seja, dividindo por ). Os últimos
algarismos de  são 
Alternativamente      (mod . Mas        (mod
 e portanto    (mod  Então      (mod .
2º método: com   , tem-se          (mod , que se
simplifica para                         
                          mod 
E tem-se ainda que
                         mod  

11. Determine os últimos dois algarismos na expansão decimal de

   .

Resolução: Para deduzir os últimos dois algarismos de  é necessário encontrar o resto de

 quando este número é dividido por 
Como sabemos que mdc    vem pelo teorema de Euler que se tem   
mod ; ora             . Tem-se que
   mod .

Daqui vem que    mod        mod  

12. Usando o teorema de Fermat prove que se  é um primo ímpar, então:

(a)               mod ,
(b)              mod .
Resolução: (a) Todos os números  entre  a    verificam a relação mdc(   
Então             
            mod 

 51

(b) De forma análoga tem-se que

  
                         mod . 


13. Sejam    primos ímpares. Mostre que:

(a) Se        e mdc    então    mod ,
(b)       mod  ).
Resolução: (a) De mdc    deduz-se que mdc   mdc    pois são
primos ímpares distintos. Vem que   mod  e   mod 
Tem-se        donde       , para algum  , e portanto    
mod , isto é,   mod . Como já se sabe que    mod  conclui-se que
  mod 
(b) Pelo teorema de Fermat vem que  mod . Como     mod  conclui-se que
      mod ). Analogamente se deduz que       mod  ). A
conclusão é agora imediata.
Notar que o resultado "Seja      onde    são tais que mdc      se
  . Então

 
    mod ."
   
   

permite obter uma resolução alternativa. 

14. Seja  um primo. Mostre que se   , então:

(a)        (b)        
Resolução: (a) É sabido que    mod  e que       mod .
Então          mod  e portanto
      .

Alternativamente      e        implica que

     e       

donde

                

como pretendido.
(b) De       mod  vem que          mod  e portanto
       . 
 52

15. Prove que para cada primo  a diferença

       

(no primeiro número cada algarismo surge exactamente  vezes) é múltiplo de 

Resolução: Podemos excluir, desde já, alguns casos simples: se    ou    é trivial.
Suponhamos que    e notemos que 
  
   

 vezes
Então
     
           
                  
   

e portanto
       
  
                      

donde
                         

Mostrar que    é divisivel por  é equivalente a, tendo em conta

mdc   , mostrar que         é divisivel por .
Note-se que pelo teorema de Fermat se tem    mod. Então
        
                        
                    
                    
                       mod ,

como pretendido. 

16. Seja  um primo da forma       . Mostre que

         e   

Resolução: Se        é imediato que      .

Consideremos a outra implicação. Tem-se que           mod  Se
   está provado, pois implica que   . Suponhamos agora que  / . Então, pelo
teorema de Fermat vem que    mod  donde    mod  portanto
     mod        mod        mod 
 53

Vem então que

  
  
     mod          mod 

Suponhamos, por absurdo que  / . Então pelo teorema de Fermat    1

mod  Mas       1 mod , pois estamos a considerar primos da forma   .
Tem-se o absurdo e consequentemente tem de ser   . Recordemos que se partiu da
hipótese que     mod . Vem que    mod  e portanto   , absurdo. 

17. Mostre que existem infinitos números naturais  tais que

  

é natural (sugestão: usar o teorema de Fermat, com    onde  é primo  ).
Resolução: Para se usar o teorema de Fermat podemos supor   , onde  é um
primo   Tem-se então que         mod . Então
              
   
   

Temos que      , para algum    pelo teorema de Fermat. Por outro lado
      . Portanto
      

e, consequentemente, como existem infinitos primos    existe uma infinidade de

  
números da forma que são naturais. 

 54

Secção 7

1. Determine as ordens de   e :
(a) mod  (b) mod 
(c) mod  (d) mod 
Resolução: (a)    e os seus divisores são     
Tem-se que          mod     mod ;    .
Tem-se            mod        mod     mod  e
portanto    .
Tem-se      mod    13    mod  58      mod  5  
mod  e portanto    .
(b)    e os seus divisores são      
Tem-se que       mod     mod      mod ;    .
           
(c)    e os seus divisores são    
Tem-se que            mod ;    .
           
(d)    e os seus divisores são        
Tem-se que       mod       mod ;
            

2. Seja  um primo.
(a) Quantas raízes primitivas e distintas mod  existem?
(b) Enumere todas as raizes primitivas mod 11 e mod 15.
Resolução: (a)     
(b) mod  há 10   e são     Os restantes números têm ordem       (o
número ) e  (o número 
Mas mod  não há raizes primitivas, de acordo com o teorema da raiz primitiva. 

3. Indique quantas raízes primitivas mod  existem para cada primo  tal que
    , exibindo pelo menos uma para todos os primos inferiores a 
Resolução:   . A única raiz primitiva é 
 55

   Há    raizes primitivas; é o 

   Há    raizes primitivas; são  e 
   Há    raizes primitivas; são  e 
   Há    raizes primitivas; uma é o 
   Há    raizes primitivas; uma é o 
   Há    raizes primitivas; uma é o 
   Há    raizes primitivas; uma é o 2.
   Há    raizes primitivas    Há    raizes primitivas,
   Há    raizes primitivas    Há    raizes primitivas,
   Há    raizes primitivas    Há    raizes primitivas,
   Há    raizes primitivas 

4. Indique quantas raízes primitivas mod  existem para cada um dos números:
(a)  (b)  (c) 
Resolução: (a)    admite raizes primitivas. São            
(b)      admite raizes primitivas. São              
(c)      não admite raizes primitivas (pelo teorema da raiz primitiva). 

5. Tendo em conta que  é uma raiz primitiva mod  determine todos os naturais no
conjunto    que são raizes primitivas mod 
Resolução: Sabe-se que (   Como  é raiz primitiva mod  os naturais
coprimos com  são congruentes com algum dos números       
Sabemos que  é raiz primitiva mod  se e só se mdc   , isto é, se      
As raizes primitivas são      e  (mod ), isto é,    e 1 (mod ). 

6. Seja    tal que    mod . Seja  uma raiz primitiva mod . Mostre que
  também é raiz primitiva mod  Encontre um exemplo para mostrar que isto
pode falhar se    mod 
Resolução: Sendo       vem que        . Tem-se também que
          mod .
Suponhamos que  é par Então   1 mod  e portanto     Mas  é raiz
primitiva e daqui se conclui que      Consequentemente   é raiz primitiva
 56

Suponhamos agora que  é ímpar. Então 2    2 2   mod  e portanto
    . Isto implica que        , isto é,    , o que é absurdo.
Tomemos agora      mod .  é uma raiz primitiva, ou seja tem ordem ; mas
    mod  tem ordem 3. 

7. Suponhamos que     e que     Mostre que   divide
 . Em particular se mdc    tem-se    
Resolução: De   mod  vem    mod ; de    mod  vem    mod .
Então       mod  Portanto    
Considere-se agora que mdc   .
Seja      e      onde os  e os  são distintos, visto que
   . Seja    ; sabe-se que    e portanto    
   
    com      e      .
 
Tem-se que    e    . Seja     e      . Então

         mod 

donde
   
               mod 

Conclui-se que    e portanto    . De forma análoga se deduz que    e portanto

  . 

8. Seja  um primo ímpar. Mostre que:

(a) Existem tantas raizes primitivas distintas mod  , como mod  
(b) Toda a raiz primitiva mod   também é raiz primitiva mod 
(Sugestão: considere  com ordem     . Mostre que    mod  
     mod   e portanto      .)


Resolução: (a) Basta notar que mod  e mod  existem raizes primitivas e que
         .
Alternativamente pode-se verificar que se  for raiz primitiva mod   (podemos supor
que é ímpar, pois se for par, então    é ímpar e também é raiz primitiva mod  
então mdc     e     divide (   ((   ( 
Mas    mod   implica que    mod   e portanto    (   . Vem
então que      ( , isto é, é raiz primitiva mod  
 57

Reciprocamente se  for raiz primitiva mod   então mdc(     com  ímpar. Se
    vem que   ( . Tem-se também que    mod   donde    
  para algum   . Mas    é par e portanto   ,    Portanto    
  para algum    e daqui vem que    mod  . Então (   (    .
Conclui-se que   (  e portanto  é uma raiz primitiva mod  .
b) Temos que mdc(     donde mdc    Sendo     vem que   
mod  e portanto       . Tem-se também que     , para algum   
Seja    e calculemos

        

    
     
 

            
 
        
       
  

Mas como           e  


vem que


           

   
 

Portanto    mod  . Como se sabe que  é raiz primitiva mod   então


    (    donde      Portanto      e  é uma raiz primitiva

mod . 

9. Prove que se   são raizes primitivas mod   primo ímpar) então  não é raiz
primitiva mod .

Resolução: Se    então    e    donde     
 e  não é uma raiz
primitiva mod .
Se  é uma raiz primitiva mod  e    então    , com mdc     . Em
particular  tem de ser ímpar porque    é par. Mas então    que não pode ser
raiz primitiva porque mdc        

10. Seja   ,   ,    mod . Seja           tal que    .
(a) Observe que  é raiz do polinómio      . Como
           

e como  não é raiz de   ,  tem de ser raiz de     ; logo,       .

(b) Mostre que     , pelo que      . Mostre que      para
     e deduza que      .
Resolução: (a) Evidente.
 58

(b) Tem-se       donde              mod  e portanto

     . Caso       teria de ser        ou 
1. Se      mod  então    mod  (absurdo).
2. Se      mod  então        mod        mod . Vem que
   mod  (absurdo) ou    ; neste último caso vem que           e
portanto    , o que é absurdo.
3. Se      mod  então
       mod          mod          mod 
      mod       mod      mod  (absurdo).

Portanto      . 

11. (a) Seja   ,   . Utilize a teoria dos grupos finitos cíclicos para mostrar:
(1) Se    mod  então existe    tal que      mod .
(2) Se     mod  então não existe    tal que      mod .
(b) Para      , encontre    tal que      mod .
Resolução: (a.1) Se    mod  então      pois     , para algum
  . Então pelo teorema de Lagrange existe  de ordem  e esse grupo  é cíclico, ou
seja é gerado por    . Então      e portanto    
(a.2) Se    mod  então      pois             
Suponhamos que existe  tal que      mod . Então     donde     .
Mas então           , o que é absurdo.
(b)   . Temos que     mod ,    Temos que 8    mod 13.
   Temos que     mod ,    Temos que     mod  

12. Usando uma tabela de indices para uma raiz primitiva mod  resolva as
congruências:
(a)    mod  (b)    mod 
(c)    mod  (d)    mod 
Resolução: Seja a raiz primitiva  e consideremos a tabela
          
ind           

(a) Aplicando indices temos

     mod        mod      mod 
Consultando a tabela    mod  é solução.
 59

(b) Aplicando indices temos

     () mod        mod     4 mod 5
Consultando a tabela     mod  são solução.
(c) Sabe-se que

   mod  tem solução se e só se     mod  com   mdc( 

Neste caso               mdc   . Ora


 2         1 (mod 

e portanto não tem solução.

(d) Aplicando indices temos
     mod        mod      mod ,
isto é,    mod . Consultando a tabela    mod  é solução. 

13. Usando índices determine o resto de   por ?

Resolução: Notar que  é raiz primitiva mod  e que     logo existe uma
solução da equação     mod .

                
ind                 

Consideremos a equação     mod . Aplicando índices vem

     mod            mod 
        mod      (mod 
E se tomarmos a raiz primitiva ?

                
ind                 

Aplicando índices vem

     mod            mod 
          mod      (mod 
Alternativamente, também se tem (sem usar índices)
                         
                 (mod 
 60

14. Sejam       .
(a) Suponha que    divide   . Mostre que    é solução da congruência
   mod  se e só se  é solução da congruência      mod  .
  
  
(b) Suponha que    divide   e que    ; então existe     .
Mostre que    é solução da congruência    mod  se e só se  é solução da
congruência      mod .
 
 
Resolução: (a) Se          existem        tais que        
   .
Suponhamos que     . Então              e portanto

         mod  .
     
      
     
Reciprocamente        Então             
(b) De     conclui-se que existem     tais que      
         mod  e portanto existe     mod 
Assumimos que    mod . Então      e portanto     . Vem
então que          (mod 
Note-se que      mod  e portanto           o que implica
que       pois    , e portanto    (mod ); analogamente se
prova que    (mod ). Vem então que    (       (mod 

No outro sentido se        então           

   

   

Usamos o resultado: Sejam     e   ,   . Seja   mdc . Existe solução

   da congruência    mod  se e só se   . Se    e se  é uma solução, então
existem exactamente  soluções distintas mod , dadas por

             .



15. Encontre todas as soluções, incongruentes mod , com       , das
congruências seguintes:
(a)    mod  (b)    mod 
(c)    mod  (d)    mod 
(e)    mod  (f)    mod .
Resolução: (a) Tem-se que   mdc   . Existe solução da congruência porque
  . As soluções são da forma     . Neste caso a solução é   
(b) Tem-se que   mdc   3. Não existe solução da congruência porque 3 / .
 61

(c) Tem-se que   mdc   3. Existe solução da congruência porque   . As soluções
são da forma          . Neste caso as soluções são     
(d) Tem-se que   mdc   . Não existe solução da congruência porque  / .
(e) Tem-se que   mdc   . Existe solução da congruência porque   . As
soluções são da forma          . Neste caso as soluções são     
Nota:    mod      mod       mod       mod 
(f) Tem-se que   mdc   mdc       . Existe solução da congruência
porque   . Testando alguns números encontramos a solução    porque
          
As soluções são da forma          . Neste caso a solução única é
   

16. Encontre a solução geral, bem como a solução positiva mais pequena, dos
sistemas seguintes:
    mod       mod 
(a)     mod  (b)      mod 
    mod       mod 


    mod      mod 
(c)     mod  (d) 
   mod 
    mod  
    mod 
   4 mod .
Resolução: (a)         ;         
                 
   mod       mod       mod   
                     (mod      (mod 
É solução.
(b)            ;         
                 
   mod       mod       mod   
                       (mod 
     (mod      (mod 
Tendo em conta que os  deste exercício são os simétricos dos  da alínea anterior seria
de esperar (por aplicação do teorema chinês dos restos) que     (mod .
(c) Por inspecção,    é solução. Logo a solução geral é da forma    mod 
(d)            ;            
                           
 62

   mod       mod       mod       mod   

                             (mod  É solução. 

17. Num cesto com muitos ovos sobrou sempre um quando estes foram retirados em
grupos de      e  Sabendo que no cesto não cabiam mais do que ,
quantos ovos lá havia?
Resolução: Queremos resolver o sistema
    mod 
    mod 
    mod 

Note-se que as condições suplementares    mod     mod     mod 
são superflúas. Aplicando o teorema chinês dos restos obtém-se   1 ou   . É a
segunda resposta porque o cesto contém muitos (isto é, mais do que um) ovos. 

18. Sejam  e  números naturais tais que, para quaisquer    se tem

      

Mostre que   
Resolução: Seja  um primo maior que  e . Então mdc   mdc   
Como mdc     , pelo teorema chinês dos restos, existe algum natural  que é
solução de

   
 mod   
mod 

A primeira congruência diz que        Pelo teorema de Fermat sabe-se que
   mod  donde    mod . Vem então que    mod  e daqui vem
que     mod        mod . Tem-se que          (relação
justificada pela hipótese) donde      mod .
Mas        mod  donde      mod . Mas      implica que
     e portanto    

19. Resolva as congruências:

(a)        mod   (b)        mod  
(c)      mod   (d)          mod  
Resolução: (a) Queremos resolver a equação      mod  .
Escrevemos         e daqui vem que        . Uma qualquer
solução de        mod   será da forma      onde       
 63

mod . Testando todos os casos verifica-se que    (mod  é solução. Note-se que
  mod  Resolvendo a equação
     
  
      mod       mod 
 
    mod      mod 

Então      mod       mod  .

Agora uma solução de      mod   será da forma        , onde
 
    mod 


Resolvendo esta equação, e tendo em conta que    ,       mod 
vem que


    mod        mod      mod 


Então    mod  e         .

As soluções da equação são os números que verificam    mod  
(b) Queremos resolver a equação        mod  .
Escrevemos         e daqui vem que       .
Uma qualquer solução de        mod   será da forma      onde
       mod . Testando todas os casos verifica-se que    (mod  é solução.
Note-se que      
  mod  Resolvendo a equação
  
      mod       mod 
 
    mod      mod 

Então      mod       mod  .

Agora uma solução de        mod   será da forma        , onde

 
    mod 


Resolvendo esta equação, e tendo em conta que          vem que


    mod        mod      mod 


Então    mod  e    mod  .

As soluções da equação são os números que verificam    mod  .
 64

(c) A congruência      mod  tem as soluções     mod . Consideremos a

primeira das soluções,    mod . Sabe-se que            e    
    mod  Aplicando o método de Hensel obtém-se
   
         mod  ,
    
 
       mod  ,
 
 
         mod  
 
Portanto    mod   é solução da congruência      mod  . Partindo da
outra solução obtemos também que     mod   é solução da congruência
     mod  .
(d) Queremos resolver a equação          mod  
Escrevemos             e daqui vem que           .
Uma qualquer solução de            mod   será da forma
     onde            mod . Testando todas os casos verifica-
se que    (mod  e    (mod  são solução.
Note-se que        
  mod  e        
  mod . Portanto o lema
de Hensel pode ser aplicado tanto a    como a   .
Apliquemos a   . Tem-se     e     . Resolvendo a equação
  
      mod       mod 
 
    mod     1 mod 

Então      mod       mod  .

Tem-se        mod . Agora uma solução de            mod  
será da forma        , onde
 
    mod 


Resolvendo esta equação, e tendo em conta que     vem que


    mod        mod      mod 


Então    mod  e    mod  .

Apliquemos este método a   4. Contas análogas mostram que    mod  .
Portanto as soluções da equação inicial são os números que verificam    mod   e
   mod   
 65

20. Resolva a congruência

       mod 

(Sugestão: use a alínea (b) do exercício anterior).

Resolução: (a) Tendo em conta que      a equação        mod 
pode ser escrita na forma

        mod 
       mod  

Pelo exercício 19(b) a primeira equação tem por solução    mod   Examinando
todos os casos possíveis a segunda equação tem por solução    mod . Então o
sistema é equivalente a

    mod 
   mod  .

e pode ser resolvido usando o teorema chinês dos restos. Tem-se

          mod      mod         

A solução é dada por

             (mod ,

isto é,

   mod    mod 

Alternativamente como se tem

    mod  
   mod      mod  
   mod 

vem de novo que    mod . 

 66

Secção 8

1. Calcule os seguintes símbolos de Legendre

(a)   (b)   (c)  

   
  

(d)   (e)   (f)  

    
  

(g)   (h)   (i)  .

  
  

Resolução: (a)    pois

 
    mod . Este último é igual a
 

          
 2  

 

(b)      pois     mod  Este último é igual a    

   
  

(c)       Ora    mod  donde     

     
   
(d) Tem-se

               .
             

      

Como        vem que         

 


(e)   e    se e só se     mod . Ora    (mod 8.

  
  

Então    .



(f)      pois          

  1  
   

Sabe-se que         mod . Ora    mod  donde     

 1
 
Pela lei da reciprocidade quadrática vem que

          , e
   
 
  

             
   
   
   

Então                
1      
      
 67

         . Como    (mod 8 vem que     e portanto

    
  

    
 


(g)              
   
   
   

     
            
    

                
      
    

Como          mod  vem que         

  
  

(h)    
  
  

Como    mod  vem que    . Então




       

        
      

Como    mod  vem que    . Então




                    
        
       
              
 
 

(i)        
  
  
  

2. Prove:

(a)         mod  (b)            mod .

 
 

(c)              mod .




Resolução: (a) Tem-se    . Suponhamos que    mod . Então

  
  
     , para algum   .
Caso 1. Seja  par. Então vem que    e portanto     ; daqui se conclui que

        . Por outro lado, por II.6.22.    . Portanto    

   
  
 68

Caso 2. Seja  ímpar. Então vem que      e portanto       ; daqui se

conclui que           
 

  . Por outro lado, vem que    mod

, donde por II.6.22.     . Portanto    
 
 
Suponhamos agora que    mod . Então      , para algum   .
Caso 1. Seja  par. Então vem que    e portanto        daqui se conclui que

        . Por outro lado, por II.6.22.     . Portanto     

   
  
Caso 2. Seja  ímpar. Então vem que      e portanto       ; daqui se
conclui que           
 

  . Por outro lado, vem que   

mod , donde por II.6.22.    . Portanto    
 
 
(b)       mod         mod .
Comecemos por supor que  é de alguma destas formas.

Se    mod  então    mod  e    mod  Então         e

 
 

       .
  
  

Se    mod  então    mod  e    mod  Então           e

 
 

             .
  
  

Se    mod  então         mod  donde     ; se    mod 



então      mod  donde     . Vem então que       
   
   
      .

Se    mod  então         mod  donde    ; se    mod 



então       mod  donde    . Vem que            .
   
   

Reciprocamente se     conclui-se que      donde        ou

    
    
       
 
 

Sabe-se que          mod           mod  e vem que:

 
 
 69

1º caso.    mod      mod              

mmc        donde    mod  (ex.4(i) da secção 4).
2º caso.    mod       mod      mod       mod .
Subtraindo vem     mod 
3º caso.     mod       mod       mod      mod .
Subtraindo vem    mod .
4º caso.    mod       mod             
 mmc             mod  (ex.4(i) da secção 4).

(c) Comecemos por supor que    .




Caso 1. Suponhamos que    mod . Então     . Por II.6.12 (c) tem-se
 
 
     (mod ) isto é,       (mod ). Os únicos  que verificam esta relação
   
 
verificam também      mod . Ora
   mod      mod      mod 
   mod      mod      mod 
  1 mod      mod      mod 

Caso 2. Suponhamos que   3 mod . Então      . Por II.6.112 (c) tem-se
 
 
     (mod ) isto é,        (mod ). Os únicos  que verificam esta relação
   
 
verificam também      mod . Ora
   mod      mod      mod 
   mod      mod      mod 
   mod      mod      mod  

3. Se  e  são primos que verificam a relação      para algum , verifique

que      e, em particular, que     
   
   

(Sugestão: note que      e use a lei da reciprocidade quadrática.)

 
 
Resolução: Tem-se que

     

       

    
 70

Se    mod  vem que     , para algum    e

            
       

   

                
      
    

notando que     se    mod .



Se    mod  vem que                      mod . Então:

                   
          

    

                         ,
        
    

como pretendido. 

4. Sejam   primos tais que    mod  e    mod . Se a congruência   

mod  não tem soluções, que se pode dizer da congruência    mod ?

Resolução: Se    mod  não tem soluções então     . Mas




                    
      

  

       
 
 

Conclui-se que     , isto é, a congruência    mod  também não tem



soluções. 

5. Quais das seguintes congruências admitem solução?

(a)    mod  (b)    mod 
(c)     mod  (d)    mod 
Resolução: Tendo em conta que    e  são primos só é necessário determinar o
valor do símbolo de Legendre.
(a) Tem-se

                             
         
       
E em extra: tem-se    mod  e    mod . Então por 4, como a equação
  mod  não admite solução então   mod  também não tem solução.
 71

(b) Tem-se                      
         
       

Notar que         mod  Portanto    mod  não admite solução.
 


(c) Tem-se        Portanto a equação     mod  admite solução.

   
 
As soluções são (trivialmente)    mod  e    mod 
(d) Tem-se

                           
        
      
Portanto a equação    mod  não admite solução. 

6. Prove que  é resíduo não-quadrático de todos os primos da forma

(a)         (b)      onde  é primo ímpar.

Resolução: (a) Pretende-se provar que  


  . Pelo teorema da reciprocidade

quadrática é imediato pois:

     
          
          
    

        
      
  

Alternativamente: em primeiro lugar verifique-se que 4   mod , por indução. Para
   é evidente. Assumindo que é válido para  vejamos que também é para   .
Tem-se             mod .
De seguida verifiquemos que      mod      mod .

Sabe-se que          mod . Ora      


   mod .

(b) Se  é um primo ímpar então      e         . Temos que
                (mod 

Sabe-se que          mod . Ora        


   mod . 


7. (a) Mostre que se  é um divisor primo de        então    .



Conclua que  é primo. (Sugestão: considere apenas os primos inferiores a ).
(b) Mostre que      e        são primos.
 72

Resolução: (a) Suponhamos que        . Então      mod , isto é,  é
solução da equação      mod . Então         
   
 

Só temos de testar os números primos que verificam     e que são inferiores a



   . Sabe-se que           mod  portanto só é preciso testar os

primos  e . Nenhum dos dois divide  que portanto é primo.
Alternativamente, se    dividisse  então dividiria      , o que não se
passa; se    dividisse  então dividiria    , o que não é o caso.
(b) Suponhamos que     . Então    mod , isto é,  é solução da equação
   mod . Então    , o que só ocorre se     mod 


Consideramos os primos inferiores a    , tais que     mod  São eles
 e  Mas nenhum destes números divide 
Suponhamos agora que        . Então      mod , isto é,  é uma
solução da equação      mod . Então       , o que só ocorre se
   
 
    mod 
Consideramos os primos inferiores a    , tais que     mod  São eles
,  e  Mas nenhum destes números divide  

8. (a) Verifique que os divisores primos    do número natural      são da

forma    ou   
(b) Verifique que os divisores primos  do número natural      são da
forma   .
(c) Verifique que os divisores primos    do número natural      são da
forma   .
Resolução: (a) Se        então              donde se deduz
que      mod . Note-se também que se    então mdc(    e   está


definido. Portanto se    vem que    . Por II.6.22(c) vem que     mod .


(b) Temos que            e se        então
            
 73

donde se deduz que       mod  e portanto    . Mas já sabemos



que         mod  e portanto     , para algum k  .


(c) Tem-se        mod  donde
       mod         mod 

Portanto   é residuo quadrático mod  (note-se que mdc   ). Vem então que

                        
        
     

e esta última expressão é igual a   se    mod  e   se    mod 

Acrescente-se que a primeira condição corresponde a    mod  pois se se tivesse
   mod ,  seria par e consequentemente não seria primo.

Alternativamente, pelo exercício 2(a)     se e só se    mod .





9. (a) Sendo    prove que todo o divisor primo  de      é da forma

     
(b) Mostre que todos os divisores primos de      são da forma      
Resolução: (a)  Tem-se que            . Se        então
       (mod         (mod 

     (mod 
   

       (mod .
 


Alternativamente de       (mod  basta estudar o símbolo de Legendre

       (note-se que  não divide   para chegar ao

     
   
mesmo resultado.

Tendo em conta que         mod  o primo tem de ser    mod .




 Tem-se que            . Se        então
 74

       (mod        (mod 

    (mod 
   

      (mod 
 


Alternativamente de      (mod  basta estudar o símbolo de Legendre

         (note-se que  não divide   para obter o mesmo resultado.

    
   

Visto que          mod  o primo  tem de verificar     mod .



Tendo em conta  e  temos de ter     mod .
(b) Podemos escrever
               .

Se
          

então

         (mod       (mod 

     
  

Visto que          mod  o primo  tem de verificar     mod . Mas



por outro lado       , com    donde     mod  (ver alínea anterior).
Conjugando estas duas condições vem que     mod  

10. Mostre que para primos    existem sempre resíduos quadráticos mod 
consecutivos.
Resolução: Comecemos por reparar que para    só há dois resíduos quadráticos  e
, que não são consecutivos. Se    temos os resíduos quadráticos   , dois dos
quais são consecutivos.
Seja agora   , isto é,   . Notemos que    são resíduos quadráticos. Basta ver,
agora, que pelo menos um de entre   e  também é. Se  for, o resultado está
provado. Se  for, o resultado também está provado. Mas se não forem vamos ver que
 é residuo quadrático. Basta notar que

               
  

  
 75

11. Seja  um primo ímpar. Mostre que se     mod  tem solução então   1
(mod 
Resolução: Sabe-se que "II.4.6. Corolário. Seja  um primo. A congruência    mod 
  , tem solução se e só se

 mdc(   mod ."

Neste caso isto significa que     mod  tem solução se e só se

 

   mdc(   mod    
é par.
mdc    mdc 
 

Usou-se            
   
no denominador.
  
Já se sabe que "    mod  admite solução se e só se    mod " Como
    mod  tem solução então    mod  donde    mod  ou    mod 
  
Se      então 
mdc( 
 
mdc(  

 
mdc( 
 
mdc(    .
    
 1 
Se     1 então 
mdc( 
 
mdc( 1 
 
mdc( 
 
mdc(   
   

12. Usando o símbolo de Legendre determine se alguma das congruências admite

solução:
(a)    mod  (b)        mod 
(c)        mod .
Resolução: (a)  é primo. Consideremos a equação     mod , onde    .
Vamos calcular    
  
  

Recordemos que          mod  e que          mod .

 
 

Sabe-se que    mod  donde    . Por seu lado




             
         
  
     

tendo em conta que    mod  e    mod  As soluções são  e .
Temos ainda de ver se alguma das equações     mod  e     mod 
tem solução. Ora
 76

       

      
      

               ,
   
   

tendo em conta que          mod 



Por outro lado

        
    
    

                 
   
   

Portanto    mod  tem apenas duas soluções, que são    mod  e
   mod .
(b)        mod            mod 
        mod        mod .

Vamos calcular     . É igual a   porque    mod 

 
 
(c)      mod                   mod 
      mod . Notar que      mod 

Vamos calcular  . Como se tem           

      

   

existe solução. As soluções são    
Alternativamente, usando a fórmula resolvente,

               
 
 

e há solução se         .
   
 
   

Tendo em conta que         mod  e    mod , há solução.





13. Sejam     tais que   .

(a) Mostre que

   

  


 77

(b) Mostre que

    

    



Resolução: (a) Em primeiro lugar note-se que os números    formam um
SRC (mod ) e portanto

                
   
      

 
  
 


Esta soma é nula porque metade dos números entre  e    são resíduos quadráticos e
a outra metade são não-quadráticos.

(b) Tem-se    
          mod 

 

   
     mod     mod 

 
Se  varia de      o número  mod varia de      e    mod varia de
 a   . Portanto

        
  
        mod  


 
 


Mas

                    
   
    


 
  
 


14. Prove que se  e  são raizes primitivas mod   primo ímpar) então  não é
raiz primitiva mod .
Resolução: (Já foi resolvido na secção anterior, com um método diferente) Se  for uma
raiz primitiva mod  então      (mod    . De forma análoga     
  
 
Então        , o que implica que não pode ser raiz primitiva.
  

  

15 Usando o critério de Euler para resíduos quadráticos e o símbolo de Legendre

determine se   e  são raizes primitivas de 
 78

Resolução: Os divisores de      correspondem às possíveis ordens de um

qualquer elemento mod . Esses divisores são    e  Claramente as
ordens de   e  não podem ser  ou .
Sabe-se que      (mod 
 


Seja   . Então     (mod . Mas     pois    mod ;
 
 
logo  não é raiz primitiva (mod 

Seja    Então     (mod . Mas         ;

   
   
logo  é raiz primitiva (mod 

Seja   . Então            ; logo 

   
(mod  . Mas  
   
não é raiz primitiva (mod  

16. Seja  um primo verificando    mod . Mostre que a soma dos resíduos
  
quadráticos (mod  é igual a 

Resolução: Se     vamos ver que    . Sabe-se que      (mod .
   

  
Ora
                      (mod 

       (mod         (mod         (mod   

     


Portanto se  é resíduo quadrático mod  então    também é.
Consideremos agora      os residuos quadráticos mod  inferiores a  Então
         são os resíduos quadráticos mod  maiores que  São todos
incongruentes mod  por serem todos inferiores a 
Então a soma dos resíduos quadráticos é                   .
Só é necessário determinar . Mas note-se que existem    resíduos quadráticos no
intervalo de  a , e que no intervalo de  a  há , assim como no intervalo de  a 
Então            e vem o resultado. 

17. Prove que existe uma infinidade de primos da forma   

Resolução: Assumamos, por absurdo, que não existe uma infinidade de primos desta
forma. Designemo-los por       e assumamos, sem perda de generalidade, que
        Considere-se o número natural     . Se    vem que
 é ímpar pois  contém sempre o factor .
 79

Note-se ainda que se  é um (qualquer) divisor primo ímpar de  então   , pois de

contrário ter-se-ia    o que implicaria que    e portanto   . Mas então viria
que        , o que é absurdo.
Seja agora o número       ( é o "maior" primo da forma   ) Um
divisor primo ímpar  de  tem de verificar    e, por hipótese de absurdo,  não
pode ser da forma   
Como  divide  tem-se que     mod       mod .
Note-se ainda que         , para   , que é o menor primo dessa forma;
isto implica que mdc   .

De     mod       mod  conclui-se que    . Por II.6.22(c)


sabe-se que     mod  o que implica, em particular, que se tem    mod  ou
   (mod .
(i) Se    mod , isto é,     mod  vem que      para algum . Mas isso é
absurdo porque    e  é suposto ser o maior primo dessa forma. Vem então que:
(ii)    mod , isto é,      para algum   .
Recordemos que  é um qualquer divisor primo ímpar de  (que é ímpar) e portanto
 tem de ser da forma
      s  s 

Mas como se tem

                

conclui-se que  tem de ser da forma   , para algum    Recordemos que
     . Então
                    

donde se conclui que      , e portanto    mod , o que é absurdo.
Portanto existe uma infinidade de primos da forma    
 80

Secção 9

1. a) Escreva em bases  e  os números    

(b) Escreva em base  os números      
Resolução: (a)              . Portanto    
             . Portanto    
             . Portanto    
                  Portanto    
Alternativamente,
      
      
      


e lendo os restos, a contar do fim, vem 

Em base  temos os números            
          Portanto    
              Portanto    
             .  . Portanto    
                Portanto    
Alternativamente,
      
      
      

e lendo os restos, a contar do fim, vem  (note que   )

(b) Tem-se que
                                      
                          
Em base  temos os números                 
                        
                     
                
 81

2. (a) As representações decimais

    e    

correspondem a que fracções?


(b) Calcule o comprimento do período da expansão decimal de para cada um dos

naturais  tais que      e mdc   mdc   .

(c) Calcule a expansão decimal de para cada um dos naturais  tais que

     e mdc   mdc   .

(d) Calcule o comprimento do período da expansão decimal de para cada primo

   excluindo    e   
(e) Verifique o teorema de Midy para os períodos de comprimento par obtidos na
alínea anterior.
Resolução: (a) Tem-se
              



     
        
     

       


e de forma análoga     

(b) e (c) 
    comprimento 1 
    comprimento 

    comprimento  
    comprimento 

    comprimento  
    comprimento 

    comprimento .
(d)    comprimento         comprimento     
   comprimento         comprimento     
   comprimento         comprimento     
   comprimento     
(e) 
   04347826086 95652173913 e 04347826086  95652173913  99999999999

  0 03448275862068 965517241379310 e 03448275862068  965517241379310  99999999999999

   02127659574468085106382 97872340425531914893617 
 82

 
3. Calcule e em base , assumindo que os seus algarismos nessa base são
 
             

Resolução: Para obter em base  faz-se

1
        
        
        
        
        
 
 
e portanto     Para obter em base  faz-se
 

      
        
        
        
 


e portanto      


4. Consideremos      ,  um primo ímpar,     para algum   , e tome-


se      mdc   . Seja      Então      mod 

Resolução: É preciso mostrar que      . Visto que mdc    é necessário mostrar
que     , isto é,     mod  Mas isto é imediato pois    .

Sejam         . Então    e portanto    Tem-se       . Então

  
             mod .
  

Sejam          Então    e portanto    Tem-se       . Então

  
             mod . 
  
 83


5. Seja        primo ímpar e     ,    o período de em base  e

  
  É possível mostrar que todo o número formado por  algarismos consecutivos

de      ou de alguma sua redisposição cíclica, é congruente com    mod 

Verifique esta propriedade considerando   ,    e   


Resolução: consideremos um primo ímpar  tal que     e a fracção (  ), cujo

período é           .

Vamos assumir os resultados não provados:

  
                e       .


Como    mod  então     mod  e por conseguinte      Seja

  
 ,  a primeira metade de           e  a segunda. Então:

  
                            .


Nestas condições vem que

  
                         


Mas    implica que        donde    . Como também se tem   

vem que
   
  
 
e portanto       , isto é,      ou seja      e portanto     mod .
Como  é um número formado por  algarismos consecutivos extraídos de     (ou
de alguma sua redisposição cíclica), tem-se o pretendido. 

  

Seja          Então   e tem-se


              mod .

    
Seja          Então      e    . Tem-se
  
              mod 
              mod 
 83

Secção 10

1. Sejam   ,    e para      , definem-se  e  assim:

             
      e          

Mostre que    e    ,      , onde os  são os números de Fibonacci:

      e         .
Resolução: Tendo em conta
       
      
         
         

é imediato que    e    .

Vem que        representam os números de Fibonacci  tendo em conta que
     Por outro lado os  tomam a forma      que representam os números
de Fibonacci  tendo em conta que    e   
Tem-se ainda que
  
                        
  
  
e a única raiz positiva é    


2. Sejam   ,    e para      , definem-se  e  como no exercício 4. Seja


         . Mostre que    .

Resolução: É imediato que
 
                  
        

3. Sejam   ,    e para      , definem-se  e  como no exercício 1. Mostre

que, para   ,
 
          e        .
 

Resolução: Tem-se
             
      e          .
 84

Sabemos que
         
                  
          

 
Vamos assumir, por indução, que            e queremos ver que 
 
           Ora
      
       
   

               
         
    
De forma análoga      
 
 
Vamos assumir, por indução, que         e queremos ver que 
 
            Ora
       
           
    

               
      

como pretendido. 

4. Seja    e suponha que        é a expansão de  em fracção continua. Para

   , sejam    definidos como em IV.1.3. Se    sejam

 
       
  
  
      
 
  
      
  

   ,
 
      
 
  
      
        
   
       
     
e
   
   
    
 
   
    
 
        .
    
 
   
    
   
    

   
    
    

Mostre que   det  e   det .

Resolução: Recordemos a definição de  e  : "Sejam   ,    e para      , definem-
se  e  assim:
 85

             
      e          ."

É claro que   det   det     . Suponhamos, por indução completa, que se tem
  det . Então

   
   

det        det   det         


  
   
 

Analogamente, sabemos que   det   det     . Suponhamos, por indução completa,

que se tem   det . Então

   
   

det        det   det         


  
   
 

5. Seja    e suponha que         é a expansão de  em fracção continua. Para

   , sejam    definidos como em IV.1.3. Se    mostre que

       

       
.
      

Aproveite esta igualdade:

(a) para provar que se tem          
(b) para mostrar, como visto no exercício 4, que, para   , se tem
 
          e        .
 

Resolução: Tem-se que                 

               .

Por indução. Sabe-se que 

    
   
 . Considere-se que se tem


           
       
   ;


quer-se mostrar que

           
       
   


É suficiente provar que  

       
     
  , o que é imediato pela definição de

 e de  .
 86

(a) Tem-se que

det
 
 det 
      
       
 
 
       
               
   vezes

(b) Tem-se

           
       
  


e sabe-se que
 
         e         
 

Passando para a matriz transposta

   
 
T
   
(
  

     
  
T
     
   


        
     
  ;


designando, nestas últimas igualdades,                e

        , tem-se

  
            

      
   e

 
         e          ,
 

isto é,
 
          e        . 
 


Exercícios extra. Calcule o número racional, na forma com    , mdc   .

(a)      (b)     
Resolução: (a) Basta fazer
      4
 1 2 3 4 5
  1    
      

Portanto       

 87

(b) Basta fazer

      4
 1    
      
      

Portanto       


Extra. Sendo       (  ) escreva  como número racional.

Resolução: Tem-se     
 donde se conclui que
2  
 2

         
        ,
  
        
 
que se simplifica para              
  . Então    .
Alternativamente
     
    
           
       

    
e vem    Então
  
                    

Extra. Calcule a fracção contínua correspondente aos números seguintes:

   
(a)       (b) .

Resolução: (a)   2,23... donde      . Vem que
 

       Então            . Portanto

    


    

     


    donde      . Vem que   

   .

  

 

Então     
 


  


Tem-se que      ... donde             

 . Vem então que
  
 88

    
  
  

( )  

 
   




        
  
  


    donde      .


 
Vem       e tem-se ;
  
   

  



Vem que     e tem-se
  
  
 

 
 . Vem que   

   
 

 
e tem-se   
 

 


  
 


Vem que 
 1,15... e tem-se
    
 
   

  

Vem que      ... e tem-se

 

            
 
 . Portanto




       

     
     
  

    


 
            
     
  
  
 

   



  

b)       donde      .
  
Vem       e tem-se ;
  

   

   


  

Vem que    e tem-se   
 

;

   


  

Vem que    e tem-se   
 

.

   



Vem que     e tem-se
  
   
 

.

   


Então

     

    

  


 


 89

 
           
     


   
  
  


Teorema. Seja   ,  não-quadrado. Suponha que          é a fracção continua de . Então a
equação de Pell      admite a solução     se  for ímpar, e a solução     se  for par.

Corolário. Seja   ,  não-quadrado. Suponha que   é solução da equação de Pell     .
Seja    e definem-se      por

        

Então     também é solução. Em particular, a equação admite um número infinito de soluções distintas.

6. Encontre a solução fundamental e mais duas soluções de cada uma das equações seguintes:
(a)      (b)     
(c)      (d)     
(e)      (f)     
(g)      (h)     
(i)      (j)     .
Resolução: (a) Sabemos que    . Tem-se

Como    é par        é solução da equação; com efeito           

Outras soluções:   2           
Notar que                 
e                     .
Notar que                 
(b) Sabemos que     . Tem-se
 90

Como   1 é ímpar 1  1     é solução da equação; com efeito           

Outras soluções:   2           
Notar que                  e          
   Note-se que                 
(c) Sabemos que    . Tem-se

Como    é par        é solução da equação; com efeito           

Outras soluções:   2           

Notar que            e          
   Note-se que             

(d) Sabemos que     . Tem-se

Como   1 é ímpar 1  1     é solução da equação; com efeito           

Outras soluções:   2      Notar que             

e             .

Notar que             

(e) Sabemos que        Tem-se

Como    é ímpar        é solução da equação; com efeito           

Outras soluções:       ; tem-se que       

e       ; tem-se que       

 91

(f) Sabemos que     . Tem-se

Como   1 é ímpar 1  1     é solução da equação; com efeito           

Outras soluções:       ; tem-se           
e       ; tem-se           
(g) Sabemos que    . Tem-se

Como    é par        é solução da equação; com efeito           
Outras soluções:        e       
(h) Sabemos que     . Tem-se

Como   1 é ímpar 1  1     é solução da equação; com efeito           
Outras soluções: (       e (      
(i) Sabemos que     . Tem-se

Como   1 é ímpar 1  1     é solução da equação; com efeito           

Outras soluções:        e   3    
(j) Sabemos que        . Tem-se
 92

Como    é par        é solução da equação; com efeito      
    
Outras soluções:        e
       

7. Existe uma solução   da equação      com     ?

Resolução: Sabemos que       . Tem-se

Como    é ímpar        é solução da equação; mas este  não está no intervalo
pretendido. A seguinte é (      ; também este  não está no intervalo. Logo
não existe tal solução. 

8. Determine os primeiros três números triangulares que também são quadrados perfeitos.
  
Resolução: O -ésimo número triangular é    Igualemos a   Vem então que

  
                     


e obtemos a equação de Pell      fazendo      e    Pelo 6(a) as primeiras

soluções são          Então         
Obtemos os números triangulares            e       
 93

Secção 11

1. Prove, exibindo bijecções adequadas, que são equipotentes

(a) os intervalos    e  ;
(b) os intervalos de números reais    e   ;
(c) os intervalos    e  , com       ;
(e) o intervalo     e .
 
(d) o intervalo ilimitado     e ;
 
Resolução: (a) Notemos que

           e que            ,

     
     

em que                    Consideremos a aplicação

     
     
        definida por





 

se     

   



se   







se      


Como é imediato que se trata de uma bijecção os dois intervalos são equipotentes.
(b) Notemos que

           e que            ,

     
     

em que                  Consideremos a aplicação

     
     
         definida por

  
se  
     
  




se      

Como é imediato que se trata de uma bijecção os dois intervalos são equipotentes.
(c) Tomemos a aplicação         definida por        Como é imediato que
se trata de uma bijecção os dois intervalos são equipotentes.
(d) Tomemos a aplicação         definida por   log. Como é imediato que se
trata de uma bijecção os dois intervalos são equipotentes.
(e) Tomemos a aplicação         definida por   . Como é imediato que se
 
 
trata de uma bijecção os dois intervalos são equipotentes. 

2. Prove que a função  definida por           é uma bijecção entre    e .
 94

Resolução: Temos de ver que é injectiva e sobrejctiva.

Comecemos por ver que é injectiva:
                      .

Suponhamos que   . Então        , mas     é par enquanto que    é
ímpar. Como a hipótese    conduz ao mesmo absurdo deduz-se que   . Mas então
                    

Vejamos agora que é sobrejectiva: sendo   , pelo algoritmo da divisão existe    e    
tal que     
• Se   , isto é, se  é par então        Tomando    e    temos que
           
• Agora, se   , isto é, se  é ímpar vem que      Daqui vem que    
       é par. Sendo   max             temos       com 
necessariamente ímpar, ou seja        , para algum   . Daqui vem que
           , como pretendido. 

3. Construa uma bijecção entre o intervalo aberto    e  que aplique racionais em racionais e
irracionais em irracionais.
Resolução: Tomemos a aplicação         definida por

   
     



     



que transforma racionais em racionais e irracionais em irracionais. 

4. Mostre que  
   
Resolução: A maneira mais simples de se provar este resultado é usar o argumento da diagonal de
Cantor. Suponhamos que existia uma bijecção        Pode ser, por exemplo, a seguinte (em
que escrevemos todos os números em notação binária, para simplificar):
            
            
            
            
            
            
            
            
            
            

            

De seguida construímos um número  que é diferente de  na primeira casa, diferente de  na

 95

segunda casa, etc. Este número está em     mas não está em  que era suposto ser igual a
 , o que é absurdo. 

5. Dê exemplos de conjuntos    e  tais que    e    mas

(a)    
   ; (b)    
   .
Resolução: (a) Por exemplo, tomando                  é imediato que
          
       
(b) Com os mesmos conjuntos temos que      
        

6. Supondo que    e    e       , tem-se necessariamente       ?

Resolução: Sejam       
       É imediato que se tem    e    e
           No entanto tem-se que      
     . Portanto a resposta é
negativa. 

7. Supondo    e   , prove que

(a) se          então       ;
(b)       .
Resolução: De    e    vem que existem bijecções      e      Considerando a
aplicação

  
  
 

vem que  é injectiva porque  e  o são, e         . De maneira análoga  é

sobrejectiva porque  e  o são. Assim sendo tem-se       .
(b) Consideremos a aplicação          definida por       Tem-se
                             , logo  é injectiva.
Vamos agora ver que é sobrejectiva. Tomando       existem  tal que     , e  tal
que   , devido à sobrejctividade de  e  Logo      e h é sobrejectiva. 

8. Mostre que           .

Resolução: Qualquer    se pode exprimir de forma única por       , com
      não existindo nenhuma ordem a partir da qual se tenha   
Podemos agora definir a função              que ao número     faz
corresponder o par        .
Vamos ver que é injectiva e sobrejectiva.
Injectividade:                        
                              
Sobrejectividade: Seja         . Então existem               tais que
              .
 96

Tomando         tal que            vem que     
Assim  é uma bijecção e           . 

9. Supondo Card    e definindo   Card  é uma bijecção de  em , mostre que

    Card   Card 
Resolução: Seja      uma bijecção e mostremos que existe bijecção de   é uma bijecção de
 em  em   é uma bijecção de  em . Sendo      uma bijecção vem que
         é uma aplicação de  em 
É injectiva pois
                        ,

designando     Como  é arbitrário em  (pois  é bijecção) vem que   

É sobrejectiva: tomemos uma bijecção      . Então      é uma bijecção de  sobre 
por ser composição de bijecções. Vem então que
                 

Portanto é uma bijecção e tem-se que Card   Card  

10. Sejam        ,                     e seja  um

conjunto tal que      . Prove que    .
Resolução: Seja                     com      fixos e   ,
consideremos                e tomemos      definida por

     
 

 

Para cada    ,  está bem definida pois        

    
  
Trata-se de uma bijecção. É injectiva pois

           

        
 
   
e é sobrejectiva pois se     então tomando          vem que

        
                 
  
   

Portanto   
Considere-se agora a aplicação       definida por    cos  sin ; é uma bijecção de
  sobre  . Vem então que           donde    
De      temos      e como    concluímos por CSB que    

11. Prove que    (Sugestão: use aritmética dos cardinais).

Resolução: Já se sabe que     e portanto     Então
 97

Card(   Card()Card()  Card( )Card()           Card()



Portanto    

12. (a) Prove que      , e conclua a partir daqui que   .

(b) Prove que   
Resolução: (a) Já foi visto que     Como     vem que     e portanto
   . Por outro lado também se tem que    pois    Como no exercício 11 se provou
que    vem, pelo teorema CSB que   .
(b) Por aritmética de cardinais    . Como, por (a) se sabe que    vem que    

13. Seja    o conjunto das funções reais definidas e contínuas em . Prove que   . Note
que uma função real contínua é determinada pelos seus valores em .
Resolução: Vamos ver que   , isto é, que card   .
Sejam        arbitrárias tais que   , isto é, existe    tal que         Mas
então, por continuidade, existe    tal que    e    vem que       e, em
particular      ,     .
Daqui vem que a aplicação    que a  faz corresponder  é injectiva e portanto    .
Pelo exercício 3 e usando aritmética de cardinais vem que   .
Notando agora que a aplicação    que a  faz corresponder a função constante     é
injectiva vem que    . Então pelo teorema CSB vem que    

14. Prove que um conjunto  de conjuntos finitos admite um selector se e só se toda a parte
finita de  admite um selector.
Resolução: Seja  um conjunto de conjuntos finitos. Se  admite um selector  então para qualquer
    ,   
Seja    finito. Se    então o único selector admitido por  é a aplicação vazia.
Suponhamos então que   . Então a restrição de  a  \{} é um selector para  .
Reciprocamente, suponhamos agora que toda a parte finita de  admite um selector. Vejamos que
 admite um selector. Para qualquer      temos que  é uma parte finita de  e
portanto, por hipótese, existe um selector  para  tal que    .
Consideremos a família
     é um selector para     

Por (AC) existe um selector  tal que   é um selector para ) é um selector para  o qual
designaremos por  . Então , de domínio  definida por       é um selector
para . 
 98

15. (a) Seja  um conjunto infinito de círculos (bolas limitadas e fechadas) do plano euclidiano
 , disjuntos dois a dois, cujas coordenadas do centro e o raio são racionais. Prove que  é
numerável.
(b) Prove que uma qualquer colecção  infinita de intervalos disjuntos (não reduzidos a um
ponto) é numerável.
Resolução: (a) Um círculo  é unicamente determinado pelo seu centro     e raio  . Seja  o
conjunto de todos os círculos cujas coordenadas do centro e o raio são racionais. Então temos uma
aplicação      definida por          Sabemos que     por existir uma
quantidade infinita de círculos disjuntos dois a dois. Por outro lado       e daqui vem
o resultado.
(b) Podemos usar (AC) e tomando o intervalo  escolher nele um ponto racional  . Então a
aplicação      é uma injecção. Como  é numerável também  vai ser. 

16. Prove que se    é infinito numerável então  é infinito numerável ou  é infinito

numerável.
Resolução: Comecemos por notar que não se pode ter  ou    pois então     
  , o que é absurdo. Logo tem-se  e    .
Tem-se               . Supondo, por absurdo, que     vem
que          , logo    não pode ser infinito numerável. 

17. Mostre que o conjunto dos números algébricos é numerável e o dos transcendentes é não-
numerável.
Resolução: Se um número  é algébrico, é raiz de um polinómio com coeficientes inteiros. Como só
há uma quantidade numerável de polinómios deste tipo (cada um com um número finito de
raízes), então só há uma quantidade numerável destes . Como existe uma quantidade não-
numerável de números reais (ou complexos) e só uma quantidade numerável deles são algébricos,
existe uma quantidade não-numerável de números transcendentes. 