Como saber se um CPF é Válido?

Sabe-se que o CPF tem 11 números.
Vamos criar um número qualquer: 555.444.333-59
Primeiramente pegaremos os 9 primeiros números e faremos a seguinte conta:

5 X 10 = 50
5 X 9 = 45
5 X 8 = 40
4 X 7 = 28
4 X 6 = 24
4 X 5 = 20
3 X 4 = 12
3 X 3 = 9
3 X 2 = 6
TOTAL = 234

No total deve-se adicionar um zero ao final do número, isso é muito fácil, é só multiplicar este número por 10.
Então fica 234 X 10 = 2340

Agora deve se dividir este número pela quantidade de números que tem no CPF (11).
Então fica:

2340 /11
213 – este foi o resultado
8– Está é a sobra

O que deve-se levar em consideração neste caso é a sobra que deveria ser igual ao primeiro número do dígito, ou seja, o décimo número do CPF, que neste exemplo é representado pelo número 5. Podemos perceber que neste caso o CPF já é inválido, e com certeza essa foi a minha intenção.

Mas se até aqui deu certo, então este CPF já tem algumas chances de ser válido, mais ainda tem outro procedimento que nos diria se realmente é válido ou não.

Segunda parte, pegaremos a partir do segundo número do CPF e iremos até o décimo:

5 X 10 = 50
5 X 9 = 45
4 X 8 = 32
4 X 7 = 28
4 X 6 = 24
3 X 5 = 15
3 X 4 = 12
3 X 3 = 9
8 X 2 = 16
TOTAL = 231

Neste ponto faremos a mesma coisa e multiplicaremos por 10, então se obtem o número 2310.
E então dividiremos da mesma forma exemplificada acima:
Utilizando o mesmo processo anterior, onde dividimos pelo número de dígitos do CPF.

2310 / 11
210 <- resultado
0 <-  resto

0 <- Este é o resto, então o último número do digito teria que ser “0”, para que este fosse um CPF verdadeiro.

Fiz um programa em java que testa se o CPF é válido: http://elzobrito.wordpress.com/2009/08/15/algoritmo-de-validao-de-cpf/