Not really PHP

This is not really PHP related but I know you're all smart and someone will be able to help. :) It's to do with .htaccess and rewrite rules and stuff..

I've got a website with a page structure like this:
/page.php?p=page_name_here

I want the urls to be this:
/page/page_name_here

It has a category structure like this:
/cat.php?c=1

I want the urls to be this:
/category/1

A friend suggested:
RewriteEngine on
RewriteRule ^page/([A-z0-9-_]*)/$ page.php?p=$1 [QSA,L]
RewriteRule ^category/([0-9]*)/?$ cat.php?c=$1 [QSA,L]
..but it's just giving me Internal Server Errors. Any suggestions? I've googled like mad but can't see what's wrong.

Resolved. Used this:
RewriteEngine on
RewriteRule ^page/(.*)$ page.php?p=$1 [QSA,L]
RewriteRule ^category/(.*)$ cat.php?c=$1 [QSA,L]