You can replace your Link with a relative one:
echo "<li><a href='../$page'>$page</a></li>";
This assumes that the page is the last part of the URL and will need special handling if there's no page specified (and 1 is assumed).
Possible ways to handle that are
using an
if
to see if a page was specified (if yes, use a relative link, if not simply append the next page number like you did until now).simply linking to the first page explicitly by appending
/1
when searching.