6*n-1

можно попробовать доказать обратное:

для любого k существутет n такое, что (kn - 1) -- составное.

в смысле противоположное утверждение (:

Конечно обратное верно. Детский сад прямо (или трава забористая).
Курите Китайскую Теорему об Остатках:
http://mathworld.wolfram.com/ChineseRemainderTheorem.html

Дальше в развитии метода идет решето Эратосфена, если я имя не попутал.

И кстати k*k - 1 = (k-1)(k+1) :)))

кстати, да (:

че-т я не подумав сказал (: