The production of very high energy muons inside an extensive air shower is observable at $\nu$ telescopes and sensitive to the composition of the primary cosmic ray. Here we discuss five different sources of these muons: pion and kaon decays; charmed hadron decays; rare decays of unflavored mesons; photon conversion into a muon pair; and photon conversion into a $J/\psi$ vector meson decaying into muons. We solve the cascade equations for a $10^{10.5}$ GeV proton primary and find that unflavored mesons and gamma conversions are the two main sources of $E\ge 10^{8.5}$ GeV muons, while charm decays dominate at $10^{5.5}\,{\rm GeV}< E< 10^{8.5}\,{\rm GeV}$. In inclined events one of these muons may deposite a large fraction of its energy near the surface, implying fluctuations in the longitudinal profile of the shower and in the muon to electron count at the ground level. In particular, we show that 1 out of 6 proton showers of $10^{10.5}$ GeV include an $E>10^6$ GeV deposition within 500 g/cm$^2$, while only in 1 out of 330 showers it is above $10^7$ GeV. We also show that the production of high energy muons is very different in proton, iron or photon showers ({e.g., conversions $\gamma\to \mu^+ \mu^-$ are the main source of $E\ge 10^4$ GeV muons in photon showers). Finally, we use Monte Carlo simulations to discuss the validity of our results.