2.4.10 Corolário. Sejam 7 − ™, 7  !, + − ™7 tal que . ³ mdcÐ+ß 7Ñ.
Se B" − ™7 é uma solução da equação
+ B œ ,,
então o conjunto das soluções desta equação tem . elementos:
ÖB"  Ð7Î.Ñ5 À ! Ÿ 5  .×.
2.4.11 Corolário. Sejam 7 − ™, 7  !, + − ™7 . A equação
+B œ "
tem solução em ™7 se e só se mdcÐ+ß 7Ñ œ ".
Se mdcÐ+ß 7Ñ œ " então, para qualquer , − ™7 , a equação
+B œ ,
tem uma única solução.
À solução (única) da equação + B œ " chama-se inverso de + , denotado por + -" Þ
Em ™7 há tantos elementos com inverso quantos os números naturais +  7 e
coprimos com 7Þ
Fazendo corresponder a cada 7 −  o número de elementos de ™7 que têm
inverso, obtemos uma aplicação 9 À  Ä  chamada função de Euler.
8
coprimos com 8
9Ð8Ñ
"
"
9Ð"Ñ œ "
#
"
9Ð#Ñ œ "
$
"ß #
9Ð$Ñ œ #
%
"ß $
9Ð%Ñ œ #
&
"ß #ß $ß %
9Ð&Ñ œ %
'
"ß &
9Ð'Ñ œ #
(
"ß #ß $ß %ß &ß '
9 Ð7Ñ œ '
)
"ß $ß &ß (
9Ð)Ñ œ %
*
"ß #ß %ß &ß (ß )
9Ð*Ñ œ '
"!
"ß $ß (ß *
9Ð"!Ñ œ %
Exemplos
1. A equação $B œ , Ðmod &Ñ tem apenas uma soluçãoÞ
$B œ " Ðmod &Ñ, solução B œ # inverso de $.
$B œ 2 Ðmod &Ñ, solução B œ 4.
$B œ 3 Ðmod &Ñ, solução B œ 1.
$B œ 4 Ðmod &Ñ solução B œ 3.
$B œ 0 Ðmod &Ñ solução B œ ! .
2. Qualquer equação 'B œ ,Ðmod #(Ñ, com mdcÐ'ß #(Ñ œ $ l ,, tem $ soluções.
'B œ ! Ðmod #(Ñ, soluções: !ß *ß ");
'B œ $ Ðmod #(Ñ, soluções: &ß "4ß 23;
'B œ 6 Ðmod #(Ñ, soluções: "ß "!ß "*; 'B œ * Ðmod #(Ñ, soluções: 'ß "&ß #%;
'B œ "# Ðmod #(Ñ, soluções: #ß ""ß #!; 'B œ "& Ðmod #(Ñ, soluções: (ß "'ß #&;
'B œ ") Ðmod #(Ñ, soluções: $ß "#ß #"; 'B œ #" Ðmod #(Ñ, soluções: )ß "(ß #';
'B œ #% Ðmod #(Ñ, soluções: %ß "$ß ##Þ
II. Contagens
A segunda parte deste curso diz respeito às questões básicas da Combinatória.
1. Tecnicas básicas de contagem
Neste capítulo são apresentadas algumas técnicas de contagem de conjuntos
finitos. São essenciais as noções e os resultados sobre o sistema  dos números
naturais, dados na parte I. Para os primeiros resultados são indispensáveis as
noções de aplicação injectiva e bijectiva, assim como certos resultados básicos
sobre estas aplicações, como por exemplo: a composição de aplicações injectivas
[ou bijectivas] é uma aplicação injectiva [bijectiva]; a aplicação inversa de uma
bijecção é uma bijecção.
1.1 Conjuntos finitos e infinitos
1.1.1 Definição. Dois conjuntos E e F dizem-se equipotentes ou equicardinais
ou que têm igual cardinalidade se existe uma aplicação bijectiva de E para
F (ou de F para E). Escreve-se #E œ #F .
A relação de equicardinalidade entre conjuntos é reflexiva, simétrica e transitiva.
Dado o conjunto  dos números naturais e 8 − , seja
8 ³ ÖB −  À B Ÿ 8× œ Ö"ß #ß á ß 8×Þ
Para quaisquer 8ß 7 − , é óbvio que: 8 Ÿ 7 Ê 8 © 7 . Assim, se 8 Ÿ 7
existe uma aplicação injectiva 8 ä 7 e existe uma aplicação sobrejectiva
Ä 8 . Valem também as implicações inversas.
7 Ä
1.1.2 Teorema. Para quaisquer 8ß 7 − , se existe uma aplicação injectiva de
8 para 7 , então 8 Ÿ 7.
D. Prova-se por indução sobre 8.
Para 8 œ ", a afirmação é verdadeira, pois " Ÿ 7, para todo 7 − Þ
HI: Admita-se que para 8 œ 5 − , a existência de uma aplicação injectiva
5 ä 7 implica que 5 Ÿ 7Þ
Deduz-se então que: a existência de uma aplicação injectiva 5" ä 7 implica
que 5  " Ÿ 7Þ
Como 5" tem pelo menos os elementos " e #, a existência de uma aplicação
injectiva 5" ä 7 implica que 7 Á ", ou seja "  7. Então, 7 œ =  ",
para algum = − . Prova-se que dada uma aplicação injectiva 5" ä ="
podemos construir uma aplicação injectiva 5 ä = Þ Então, pela HI, obtemos
5 Ÿ =, donde 5  " Ÿ =  " œ 7, como queríamos.
Seja : À 5" ä =" uma aplicação injectivaÞ
• Se :(3Ñ Á =  "ß a3 − 5" , então temos que a restrição de : a 5 © 5" é
uma aplicação injectiva :l5 À 5 ä = Þ
• Se :(5  "Ñ Á =  " e b3 − 5 œ 5" ÏÖ5  "× tal que :Ð3Ñ œ =  ",
obtemos uma aplicação injectiva :* À 5 ä = , definindo
:Ð4Ñ se 4 − 5" ÏÖ3ß 5  "×
:*Ð4Ñ œ š
:Ð5  "Ñ se 4 œ 3.
O contra-recíproco deste teorema é conhecido por princípio dos cacífos ou
princípio do pombal (Pigeonhole principle)
1.1.3 Princípio dos cacífosÞ Para quaisquer 8ß 7 − , se 8  7 então não
existe nenhuma aplicação injectiva de 8 para 7 .
1.1.4 Corolário. Para quaisquer 8ß 7 − , se existe uma aplicação injectiva de
8 para 7 e se existe uma aplicação injectiva de 7 para 8 , então
8 œ 7.
1.1.5 Corolário. Para quaisquer 8ß 7 − , se 8 Á 7ß então não existe
nenhuma aplicação ,ijectiva de 8 para 7 .
Se um conjunto E é equipotente a 8 , então não pode ser equipotente a 7 , se
7 Á 8, por 1.1.4. De facto, se 0 À 8 Ä E e 1 À 7 Ä E fossem bijecções,
então 1-1 ‰ 0 À 8 Ä 7 seria uma bijecção.
1.1.6 Definição. Um conjunto E diz-se finito se é vazio ou é equipotente a 8 . Se
é equipotente a 8 diz-se que E tem cardinalidade 8; # g œ !Þ
Um conjunto é infinito se não é equipotente a nenhum 8 .
Se #E œ 8, podemos representar os elementos de E como imagens dos elementos
de 8 por uma bijecção 8 Ä E:
E œ ÖB" ß B# ß á ß B8 ×Þ
1.1.7 Proposição. Um conjunto finito não pode ser equipotente a um
subconjunto próprio.