NF杯2023(B)

以降,合同式のmodは具体的な言及がない限り$M=2^{130}+1$とする.

$$(2^{65}+1)^{2024}=(2^{130}+2^{66}+1)^{1012}\equiv 2^{66\times 1012}$$

ここで,

$$2^{66\times 1012}+2^n\equiv 0$$

つまり,

$$2^{66\times 1012}\equiv -2^n$$

であるためには,2と$M$は互いに素なので,

$$2^{66\times 1012-n}\equiv -1$$

であることが必要十分である.

ここで,$\mod{M}$における$2$の位数は260であるため,

$$66\times 1012-n\equiv 130\pmod{260}$$

であることが問の必要十分条件である.

よって,

$$n\equiv 66\times 1012-130\equiv 102\pmod{260}$$

である.

つまり,条件を満たす$n$の最小値は102である.