Bestimmen Sie nun p und q , und zwar ohne n direkt zu faktorisieren, sondern mittels Bestimmung der Nullstellen …

Question

Gegeben sei \( n=1349 \). Zudem sei bekannt, dass \( n \) das Produkt zweier Primzahlen \( p \) und \( q \) mit \( p<q \) ist, sowie \( \phi(n)=1260 \). Bestimmen Sie nun \( p \) und \( q \), und zwar ohne \( n \) direkt zu faktorisieren, sondern mittels Bestimmung der Nullstellen eines geeigneten quadratischen Polynoms.

Answer 1

Sei p*q=n also

φ(n)=φ(p)*φ(q) = (p-1)(q-1) .  Und p=1349/q

==>  1260 = (p-1)(q-1) = (1349/q - 1 )(q-1)    |*q

      1260q = (1349 - q )(q-1)

     q^2 - 90q + 1349 = 0

     q=71 oder q=19

Wegen p<q also p=19 und q=71