Competition problem — Number theory

Library / /25 of 520

Number theory Difficulty 5.3 AIME, harder Find the answer

Example 8 Try to solve the congruence equation
$x^{2} \equiv 33(\bmod 128)$

Your answer

A number or a short expression. Fractions can be typed as 3/2, and spacing doesn't matter.

Solution

We have $1^{2}-33=-32$ . So 1 is a root modulo 32, therefore, $1+16=17$ is a root modulo 64, because
$17^{2}-33=289-33=256,$

Hence 17 is also a root modulo 128, and the other root modulo 128 is
$17+64=81 \equiv-47(\bmod 128)$

Thus, the roots of the original congruence equation are
$x \equiv \pm 17, \pm 47(\bmod 128)$

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: NuminaMath-1.5, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.