The phpmd/phpmd
package is at packagist (https://packagist.org/packages/phpmd/phpmd), the default repository for composer to search for packages. Not being able to locate phpmd sounds like you either have an offline system, a problem with your network or packagist.org had a timeout.
/edit:
I see you have a typo. Don't write phpmd/phpmd:
but phpmd/phpmd
(without the trailing colon).