[lxa85]

jonikster, во первых посмотрите, на какие репозитории вы смотрите.
Возможно там нет php 5.6
----
Как выяснилось да, устаревшие версии убраны из официальных репозиториев, поэтому вам надо будет подключить другие.
install-php5-on-ubuntu/
php-5-6-v-ubuntu-16-04/