Porque você tem que usar sudo para executar esses comandos que estão localizados em /sbin . Pode ser possível que o comando gem não esteja localizado no diretório /sbin . Execute este comando para conhecer as entradas de gem :
sudo dpkg -L gem