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 iii $2^\circ$ semestre, 2006/2007

1. Pretende-se determinar $$\frac{\pi(x)}{\frac{x}{\log x}}$$, para alguns valores de $x$.
   1. Escreva uma função que tenha como argumento $n$ e devolva $\pi(n), \frac{x}{\log x}$ e $$\frac{\pi(x)}{\frac{x}{\log x}}$$.
   2. Use o comando intnum para aproximar $\pi(x)$ à custa de $\int_2 ^x \frac{dt}{\log t}.$
   3. Use o comando ploth para esboçar os gráficos de $\pi(x),Li(x)$ e de $\frac{x}{\log x}$.

2. Use a factorização de Fermat para encontrar uma factorização de
   1. 143
   2. 43
   3. 2279
   4. 11413
   5. 8051
   6. 11021
   7. 73
   8. 46009
   9. 3200399
   10. 24681023

3. Implemente uma função que factorize um número segundo o método de Fermat.

4. Escreva uma função que resolva a equação diofantina $ax+by=c$.

5. Mostre que
   1. se $a$ é um inteiro par então $a^2\equiv 0 \mod 4$;
   2. se $a$ é um inteiro ímpar então $a^2\equiv 1 \mod 4$.

6. Mostre que se $a$ é um inteiro ímpar então $a^2 \equiv 1 \mod 8$.

7. O que pode concluir se $a^2\equiv b^2\mod p$, onde $a,b\in {\mathbb{Z}}$ e $p$ é primo?

8. Encontre as soluções de:
   1. $123456789x\equiv 9876543210 \mod 10000000001$
   2. $333333333x\equiv 87543211376 \mod 967454302211$
   3. $734342499999 x\equiv 1 \mod 1533331$
   4. $499999x\equiv 1 \mod 1533331$
   5. $1000001x\equiv 1 \mod 1533331$
9. Use $\rho$-Pollard, com $x_0=2$ e $f(x)=x^2+1$ para encontrar a factorização de
   1. 133
   2. 1189
   3. 1927
   4. 8131
   5. 36287
   6. 48227

10. Use $\rho$-Pollard para factorizar 1387, fazendo uso de
    1. $x_0=2 ;f(x)=x^2+1$
    2. $x_0=3 ;f(x)=x^2+1$
    3. $x_0=2 ;f(x)=x^2-1$
    4. $x_0=2 ;f(x)=x^3+x+1$