Maths Olympiad Prep

Library / /372 of 520

Number theory Difficulty 6.4 National olympiad Find the answer

4. Solve the following congruences
(1) 8x7(mod43)8 x \equiv 7(\bmod 43),
(2) x817(mod43)x^{8} \equiv 17(\bmod 43),
(3) 8x4(mod43)8^{x} \equiv 4(\bmod 43)

A number or a short expression. Spacing and $ signs are ignored.

Solution

4. Solution: From the 13th table attached at the end of this chapter, we know that g=3g=3 is a primitive root of p=43p=43.
(1) From the table, we know ind 8=398=39, ind 7=357=35, and let ind x=yx=y. Then, from the given congruence, we derive
39+y35(modφ(43))39+y \equiv 35(\bmod \varphi(43))

Since ind x=y=438(mod42)x=y=-4 \equiv 38(\bmod 42), hence ind x=38x=38. Checking the 13th table again, we get x17(mod43)x \equiv 17(\bmod 43).
(2) Checking the table, we find ind 17=3817=38. Let ind x=yx=y, then we have 8y38(mod42)8 y \equiv 38(\bmod 42),
which simplifies to
4y1940(mod21)4 y \equiv 19 \equiv 40(\bmod 21)

Solving this, we get
y10(mod21)y \equiv 10(\bmod 21)

Thus,
y1=10,y2=31y_{1}=10, y_{2}=31

Checking the table, we get the two solutions x110,x233(mod43)x_{1} \equiv 10, x_{2} \equiv 33(\bmod 43).
(3) Checking the table, we find ind 8=398=39, ind 4=124=12, hence we get
39x12(mod42)39 x \equiv 12(\bmod 42)

Thus,
13x4(mod14)13 x \equiv 4(\bmod 14)

Since 24,2142|4,2| 14, it must be that 213x2 \mid 13 x, i.e., x=2yx=2 y, so
13y2(mod7)13 y \equiv 2(\bmod 7)

Hence,
y2(mod7)y \equiv-2(\bmod 7)

Thus,
x=2y43(mod7)x=2 y \equiv-4 \equiv 3(\bmod 7)

To ensure 2x2 \mid x, we get x10,24,38(mod42)x \equiv 10,24,38(\bmod 42).

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.