Php5-mysql не имеет кандидата на установку

Ubuntu 16.04 comes with PHP7 as the standard, so there are no PHP5 packages

However if you like you can add a PPA to get those packages anyways:

Remove all the stock php packages

List installed php packages with dpkg -l | grep php| awk '{print $2}' |tr "\n" " " 
then remove unneeded packages with sudo aptitude purge your_packages_here
or if you want to directly remove them all use :

sudo aptitude purge `dpkg -l | grep php| awk '{print $2}' |tr "\n" " "`

Add the PPA

sudo add-apt-repository ppa:ondrej/php
Install your PHP Version

sudo apt-get update
sudo apt-get install php5.6
You can install php5.6 modules too ..

Verify your version

sudo php -v
Xabos