  Some recent experiments detecting very high energy (VHE) gamma-rays above
10-20 TeV independently reported VHE bursts for some of bright gamma-ray bursts
(GRBs). If these signals are truly from GRBs, these GRBs must emit a much
larger amount of energy as VHE gamma-rays than in the ordinary photon energy
range of GRBs (keV-MeV). We show that such extreme phenomena can be reasonably
explained by synchrotron radiation of protons accelerated to \sim 10^{20-21}
eV, which has been predicted by Totani (1998a). Protons seem to carry about
(m_p/m_e) times larger energy than electrons, and hence the total energy
liberated by one GRB becomes as large as \sim 10^{56} (\Delta \Omega / 4 \pi)
ergs. Therefore a strong beaming of GRB emission is highly likely. Extension of
the VHE spectrum beyond 20 TeV gives a nearly model-independent lower limit of
the Lorentz factor of GRBs, as $\gamma \gtilde 500$. Furthermore, our model
gives the correct energy range and time variability of ordinary keV-MeV
gamma-rays of GRBs by synchrotron radiation of electrons. Therefore the VHE
bursts of GRBs strongly support the hypothesis that ultra high energy cosmic
rays observed on the Earth are produced by GRBs.
