Past exam of the analytic number theory and elliptic curves course of the University of Oxford / 2009 / B / 4 / c / Solution

In the elliptic curve method, addition is attempted modulo the composite number. A denominator that is not a unit in a ring supplies a factor through its greatest common divisor with that number.

First double $P$ using the elliptic-curve addition formula. Its tangent slope isThese calculations are valid modulo $221$ since the only initial denominator is two, which is invertible. Thus $2P=(14,-53)$, equivalently $(14,168)$ modulo $221$.

To form $3P=P+2P$, the chord slope would requireThe denominator hasIt cannot be inverted, and thirteen is the requested proper factor. The failure has a geometric explanation: modulo thirteen, $2P=(1,-1)=-P$, so $3P$ is the point at infinity. Modulo seventeen that chord denominator remains nonzero. The differing behavior at the two primes is exactly what the elliptic curve method detects.