Problem
NT-B2-M09-P010 Find All Four Solutions
#10
★★★☆☆ Level 3 of 5
Find all solutions of \(x^2\equiv 1\pmod {35}\) modulo \(35\).
Combine \(x\equiv \pm 1\pmod 5\) and \(x\equiv \pm 1\pmod 7\).
There are four systems. \((1,1)\) gives \(x\equiv 1\). \((-1,-1)\) gives \(x\equiv -1\equiv 34\). For \(x\equiv 1\pmod 5\), \(x\equiv -1\pmod 7\), checking \(1,6,11,16,21,26,31\) gives \(6\). For \(x\equiv -1\pmod 5\), \(x\equiv 1\pmod 7\), we get \(29\). The answer is \(1,6,29,34\pmod {35}\).
Shows clearly that a composite modulus can have more than two solutions.