Angenommen: p teilt nicht a, aber p teilt a²
Dann muss es Zahlen 1,p_1,..p_m Geben, sodass 1,p_1,..p_j a teilen und die anderen das "andere" a teilen , und 1*p_1*..*p_k=p ist (Das folgt aus der Primfaktorzerlegung)
(Du schreibst dir p zerteilt hin, und a^2 zerteilt hin, und teilst dann einfach auf.)
Da aber p prim, muss k=1 sein, und p_1 = p. qed
Und schöner:
Sei a kein vielfaches von p, wg p prim => a,p teilerfremd.
Nach Euklid: Es Ex n,m: np+ma =1
=>m²a²=1-2np+n²p²
Da p sicherlich nicht 1 teilt, aber 2np und n²p² kann p m²a² nicht teilen.
Also teilt p nicht a²
Nach Kontraposition das gewünschte!