Universidade do Minho L.E.M., L.M.C.C. - 4$^\circ$ ano

Departamento de Matemática Mat. (Esp. Ensino), L.C.C. - 3$^\circ$ ano

Teoria de Números Computacional

folha v $2^\circ$ semestre, 2006/2007

1. Mostre que 91 é um pseudoprimo de base 3.

2. Mostre que 45 é um pseudoprimo de bases 17 e 19.

3. Mostre que $n=161038=2\cdot 73 \cdot 1103$ satisfaz a congruêncoa $2^n\equiv 2 \mod n$. O inteiro $n$ é de facto o menor pseudoprimo par de base 2.

4. Mostre que se $n$ é um pseudoprimo ímpar de base $a$ então $n$ é um pseudoprimo de base $n-a$.

5. Mostre que se $n$ é um pseudoprimo de bases $a$ e $b$ então é um pseudoprimo de base $ab$.

6. Mostre que se $n$ é um pseudoprimo de $a$ mas não o é de base $b$, com $(a,n)=(b,n)=1$, então $n$ não é pseudoprimo de base $ab$.

7. Mostre que 25 é um pseudoprimo forte de base 7.

8. Mostre, usando o gp, que 1397 é um pseudoprimo de base 2 mas que não é um pseudoprimo forte de base 2.

9. Usando o gp, mostre que 1373653 é um pseudoprimo forte de bases 2 e 3.

10. Usando o gp, mostre que 25326001 é um pseudoprimo forte de bases 2, 3 e 5.