“Impossível localizar o pacote”

Question

Quando executo sudo apt install bc (assim como outros pacotes), obtenho:

$ sudo apt install bc
Reading package lists... Done
Building dependency tree
Reading state information... Done
E: Unable to locate package bc

Esta é uma nova instalação limpa do 16.04, servidor xenial