php is still available after running apt-get remove php

To answer the actual question: php on your system is most likely a metapackage (it's certainly a metapackage on Ubuntu - and it's most likely a metapackage on Linux Mint as well).

A metapackage is a package that basically only includes / installs dependencies. Which in a way means that the "actual" packages that are brought in by the metapackage are "hidden" behind the metapackage's generic name (in this case php).

If I was to inspect php's dependencies on Ubuntu, I would discover that sudo apt install php actually installs php8.3, as php depends on php8.3:

% apt-cache showpkg php | grep -A1 '^Dependencies:'
Dependencies: 
2:8.3+93ubuntu2 - php8.3 (0 (null))

Conversely (and this is why sudo apt remove php isn't removing PHP), sudo apt-remove php would remove nothing but the php metapackage, leaving php8.3 installed:

% sudo apt remove php
Reading package lists... Done
Building dependency tree... Done
Reading state information... Done
The following packages will be REMOVED:
  php
0 upgraded, 0 newly installed, 1 to remove and 3 not upgraded.
After this operation, 11.3 kB disk space will be freed.
Do you want to continue? [Y/n] 
(Reading database ... 229794 files and directories currently installed.)
Removing php (2:8.3+93ubuntu2) ...
% php -v
PHP 8.3.6 (cli) (built: Sep 30 2024 15:17:17) (NTS)
Copyright (c) The PHP Group
Zend Engine v4.3.6, Copyright (c) Zend Technologies
    with Zend OPcache v8.3.6, Copyright (c), by Zend Technologies

And to remove PHP 8.3, I should run sudo apt-remove php8.3 instead:

% sudo apt remove php8.3 
Reading package lists... Done
Building dependency tree... Done
Reading state information... Done
The following packages will be REMOVED:
  php8.3
0 upgraded, 0 newly installed, 1 to remove and 3 not upgraded.
After this operation, 62.5 kB disk space will be freed.
Do you want to continue? [Y/n] 
(Reading database ... 229791 files and directories currently installed.)
Removing php8.3 (8.3.6-0ubuntu0.24.04.2) ...

Right?

% php -v
PHP 8.3.6 (cli) (built: Sep 30 2024 15:17:17) (NTS)
Copyright (c) The PHP Group
Zend Engine v4.3.6, Copyright (c) Zend Technologies
    with Zend OPcache v8.3.6, Copyright (c), by Zend Technologies

Wrong! As php8.3 is also a metapackage that depends, transitively, on php8.3-cli, which is the package that actually provides the php executable.

I think you get the gist.

Every metapackage in the chain of dependencies creates a level of indirection, and makes it harder to get to "the real deal"; in this case, php8.3-cli would be the last on the chain (removing that would at least make php -v from the command line fail), however removing php8.3-cli would likely still leave some packages installed by sudo apt install php around.

Overall, sudo apt remove php8.3-cli followed by sudo apt autoremove will maybe get rid of everything (assuming nothing else depends on the leftover packages of course).

Some answers on the internet suggest running commands such as sudo apt remove 'php8.3*', which yes, essentially will remove at least most of what sudo apt install php installed.

However I've grown to dislike that method, because you need to be very careful in inspecting what packages are going to be removed as part of the removal process (anything depending on a package matched by the glob will be uninstalled), and since these days and age storage is usually not a problem, I usually play it safe and just don't bother.

Rather, if PHP 8.3 is not available on your installation, I'd just use a PPA as described in your answer and install PHP 8.3 alongside PHP 8.1. The installation process will manage alternatives and things will Just Work (mostly - the most glaring instance of what's not gonna work out of the box is PHP with Apache - if you're using PHP with Apache, Apache will need to be reconfigured to load the new version of mod_php via a2enmod / a2dismod, otherwise the older version of the module will still be loaded).