apt-get update &&
apt-get install -y language-pack-en-base &&
export LC_ALL=en_US.UTF-8 &&
export LANG=en_US.UTF-8 &&
apt-get install -y software-properties-common &&
add-apt-repository -y ppa:ondrej/php5-5.6 &&
add-apt-repository -y ppa:ondrej/mariadb-10.0 && 
apt-get update && 
apt-get -y upgrade


apt install php5.6

Results

root@ubuntu:~# php -v
PHP 5.6.29-1+deb.sury.org~xenial+1 (cli) 
Copyright (c) 1997-2016 The PHP Group
Zend Engine v2.6.0, Copyright (c) 1998-2016 Zend Technologies
    with Zend OPcache v7.0.6-dev, Copyright (c) 1999-2016, by Zend Technologies

• https://github.com/oerdnj/deb.sury.org/issues/56
• http://geekdecoder.com/ubuntu-16-04-xenial-downgrade-php-7-php-5-6/