求最小的正整数a,使得存在正整数n,满足2001|55的n次方+a*32n次方

Question

求最小的正整数a,使得存在正整数n,满足2001|55的n次方+a*32n次方

Answer 1

2001 = 3·23·29,故2001 | 55^n+a·32^n等价于:
55^n+a·32^n ≡ 0 (mod 3),55^n+a·32^n ≡ 0 (mod 23),55^n+a·32^n ≡ 0 (mod 29).
分别得0 ≡ 55^n+a·32^n ≡ 1^n+a·(-1)^n = (a-(-1)^(n+1))·(-1)^n (mod 3),即a ≡ (-1)^(n+1) (mod 3);
0 ≡ 55^n+a·32^n ≡ 9^n+a·9^n = (1+a)·9^n (mod 23),即a ≡ -1 (mod 23);
0 ≡ 55^n+a·32^n ≡ (-3)^n+a·3^n = (a-(-1)^(n+1))·3^n (mod 29),即a ≡ (-1)^(n+1) (mod 29).
当n为偶数,得同余方程组a ≡ -1 (mod 3),a ≡ -1 (mod 23),a ≡ -1 (mod 29).
易得解为a ≡ -1 (mod 2001),最小正整数解为2001-1 = 2000.
当n为奇数,得同余方程组a ≡ 1 (mod 3),a ≡ -1 (mod 23),a ≡ 1 (mod 29).
解得a ≡ 436 (mod 2001) (过程略),最小正整数解为436.
于是使n存在的最小正整数为436,相应n可取任意正奇数.