On Ubuntu 17.10 and php 7.1:
sudo apt install libtidy-dev libtidy5 php-tidy
This extension is bundled with PHP 5 and greater, and is installed using the --with-tidy configure option.
On Ubuntu 17.10 and php 7.1:
sudo apt install libtidy-dev libtidy5 php-tidy
On Redhat-ish linux, you must install both libtidy and libtidy-devel (PHP 5.x):
sudo yum install libtidy libtidy-devel