Você marcou 16.04. Supondo que você esteja executando o 16.04, o php no repositório é v7.
Tente isso em vez disso.
sudo apt-get -y build-dep php7.0 php7-mcrypt
quando tento fazer "apt-get -y build-dep php5 php5-mcrypt"
o resgate é:
Reading package lists... Done
Picking 'php-mcrypt' as source package instead of 'php5-mcrypt'
Reading package lists... Done
Building dependency tree
Reading state information... Done
Some packages could not be installed. This may mean that you have
requested an impossible situation or if you are using the unstable
distribution that some required packages have not yet been created
or been moved out of Incoming.
The following information may help to resolve the situation:
The following packages have unmet dependencies:
builddeps:php-mcrypt : Depends: debhelper (>= 5) but it is not going to be installed
Depends: php5-dev (>= 5.3.3) but it is not going to be installed
builddeps:php5 : Depends: apache2-prefork-dev but it is not going to be installed
Depends: debhelper (>= 5) but it is not going to be installed
Depends: libapr1-dev (>= 1.2.7-8) but it is not going to be installed
Depends: libcurl4-openssl-dev but it is not going to be installed
Depends: libenchant-dev but it is not going to be installed
Depends: libevent-dev (>= 1.4.11) but it is not going to be installed
Depends: libfreetype6-dev but it is not going to be installed
Depends: libgcrypt11-dev but it is not going to be installed
Depends: libgd2-xpm-dev but it is not going to be installed
Depends: libglib2.0-dev but it is not going to be installed
Depends: libgmp3-dev but it is not going to be installed
Depends: libkrb5-dev but it is not going to be installed
Depends: libldap2-dev but it is not going to be installed
Depends: libmagic-dev but it is not going to be installed
Depends: libmysqlclient-dev but it is not going to be installed
Depends: libpam0g-dev but it is not going to be installed
Depends: libpng12-dev but it is not going to be installed
Depends: libpq-dev but it is not going to be installed
Depends: libpspell-dev but it is not going to be installed
Depends: libsasl2-dev but it is not going to be installed
Depends: libsnmp-dev but it is not going to be installed
Depends: libssl-dev but it is not going to be installed
Depends: libt1-dev but it is not going to be installed
Depends: libwrap0-dev but it is not going to be installed
Depends: libxml2-dev but it is not going to be installed
Depends: libxslt1-dev (>= 1.0.18) but it is not going to be installed
Depends: mysql-client-5.5 but it is not going to be installed
Depends: locales-all but it is not installable or
language-pack-de but it is not going to be installed
Depends: zlib1g-dev but it is not going to be installed
Depends: libedit-dev but it is not going to be installed
E: Unable to correct problems, you have held broken packages.
qual é a solução
Você marcou 16.04. Supondo que você esteja executando o 16.04, o php no repositório é v7.
Tente isso em vez disso.
sudo apt-get -y build-dep php7.0 php7-mcrypt