Broken links-edited .htaccess with code put out by WP-still broken

I wanted to change the default permalink structure, but it broke all my links. I contacted Pair tech support and they said ch_mod is enabled, but they couldn’t help me with third party software like WordPress. I found an article that said WP would automatically rewrite to a .htaccess file if one were there, so I created an empty one, gave it permissions of 664, and tried using WP’s Permalink Settings again. It said I needed to edit my .htaccess file, that the file wasn’t writable by WP, and it gave me the code I needed to put in .htaccess. I did that and uploaded .htaccess to my root directory. Didn’t work. Then put it in public_html. Didn’t work. Links are still broken, and I still get the same messaage on the Permalink Settings page saying to edit my .htaccess file and giving me the code to use (which is already in the file).

The text it said I need to put in .htaccess is:
<IfModule mod_rewrite.c>
RewriteEngine On
RewriteBase /
RewriteCond %{REQUEST_FILENAME} !-f
RewriteCond %{REQUEST_FILENAME} !-d
RewriteRule . /index.php [L]
</IfModule>

Do I need to put a php command before and after the code in .htaccess? Is there some other problem I’m missing? Any advice would be greatly appreciated.

Mike