Paginação + url amigaveis

Boa noite pessoal.

Estou a algum tempo tentando resolver uma paginação sem sucesso.

Uma parte da paginação

echo "<a href='categoria.php?pag=".$paginas."'>ÚLTIMA PÁGINA</a>";

.htacess

RewriteRule ^categoria/(.+)/(.+)$ categoria.php?idCategoria=$1/$2
Gostaria que ficasse algo assim, igual as demais pagina do site.

site.com.br/categoria/cultura

com paginação, algo como:

site.com.br/categoria/cultura/2 ou site.com.br/categoria/2/cultura