PEN D Problems

Part of PEN Problems

Subcontests

(23)

1

D 23

p

be an odd prime of the form

p=4n+1

. [*] Show that

n

is a quadratic residue

\pmod{p}

. [*] Calculate the value

n^{n}

\pmod{p}

1

D 22

1980^{1981^{1982}} + 1982^{1981^{1980}}

is divisible by

1981^{1981}

1

D 21

Determine the last three digits of

2003^{2002^{2001}}.

1

D 20

1994

10^{900}-2^{1000}

1

D 19

a_{1}

\cdots

a_{k}

m_{1}

\cdots

m_{k}

be integers with

2 \le m_{1}

2m_{i}\le m_{i+1}

1 \le i \le k-1

. Show that there are infinitely many integers

x

which do not satisfy any of congruences

x \equiv a_{1}\; \pmod{m_{1}}, x \equiv a_{2}\; \pmod{m_{2}}, \cdots, x \equiv a_{k}\; \pmod{m_{k}}.

1

D 18

p

be a prime number. Determine the maximal degree of a polynomial

T(x)

whose coefficients belong to

\{ 0,1,\cdots,p-1 \}

, whose degree is less than

p

, and which satisfies

T(n)=T(m) \; \pmod{p}\Longrightarrow n=m \; \pmod{p}

for all integers

n, m

1

D 17

Determine all positive integers

n

xy+1 \equiv 0 \; \pmod{n}

x+y \equiv 0 \; \pmod{n}

1

D 16

Determine all positive integers

n \ge 2

that satisfy the following condition; For all integers

a, b

relatively prime to

n

a \equiv b \; \pmod{n}\Longleftrightarrow ab \equiv 1 \; \pmod{n}.

1

D 15

n_{1}, \cdots, n_{k}

a

be positive integers which satify the following conditions:[*] for any

i \neq j

(n_{i}, n_{j})=1

i

a^{n_{i}} \equiv 1 \pmod{n_i}

i

n_{i}

does not divide

a-1

. Show that there exist at least

2^{k+1}-2

x>1

a^{x} \equiv 1 \pmod{x}

1

D 14

Determine the number of integers

n \ge 2

for which the congruence

x^{25}\equiv x \; \pmod{n}

is true for all integers

x

1

D 13

\Gamma

consist of all polynomials in

x

with integer coefficients. For

f

g

\Gamma

m

a positive integer, let

f \equiv g \pmod{m}

mean that every coefficient of

f-g

is an integral multiple of

m

n

p

be positive integers with

p

prime. Given that

f,g,h,r

s

\Gamma

rf+sg\equiv 1 \pmod{p}

fg \equiv h \pmod{p}

, prove that there exist

F

G

\Gamma

F \equiv f \pmod{p}

G \equiv g \pmod{p}

FG \equiv h \pmod{p^n}

1

D 12

m>2

P

be the product of the positive integers less than

m

that are relatively prime to

m

P \equiv -1 \pmod{m}

m=4

p^n

2p^{n}

p

is an odd prime, and

P \equiv 1 \pmod{m}

1

D 11

During a break,

n

children at school sit in a circle around their teacher to play a game. The teacher walks clockwise close to the children and hands out candies to some of them according to the following rule. He selects one child and gives him a candy, then he skips the next child and gives a candy to the next one, then he skips 2 and gives a candy to the next one, then he skips 3, and so on. Determine the values of

n

for which eventually, perhaps after many rounds, all children will have at least one candy each.

1

D 10

p

be a prime number of the form

4k+1

2p+1

is prime. Show that there is no

k \in \mathbb{N}

k<2p

2^k \equiv 1 \; \pmod{2p+1}

1

D 9

Show that there exists a composite number

n

a^n \equiv a \; \pmod{n}

a \in \mathbb{Z}

1

D 8

Characterize the set of positive integers

n

such that, for all integers

a

a

a^2

a^3

\cdots

is periodic modulo

n

1

D 7

Somebody incorrectly remembered Fermat's little theorem as saying that the congruence

a^{n+1} \equiv a \; \pmod{n}

a

n

is prime. Describe the set of integers

n

for which this property is in fact true.

1

D 6

Show that, for any fixed integer

\,n \geq 1,\,

2, \; 2^{2}, \; 2^{2^{2}}, \; 2^{2^{2^{2}}}, \cdots \pmod{n}

is eventually constant.

1

D 5

n\geq 2

\underbrace{2^{2^{\cdots^{2}}}}_{n\text{ terms}}\equiv \underbrace{2^{2^{\cdots^{2}}}}_{n-1\text{ terms}}\; \pmod{n}.

1

D 4

n

be a positive integer. Prove that

n

is prime if and only if

{{n-1}\choose k}\equiv (-1)^{k}\pmod{n}

k \in \{ 0, 1, \cdots, n-1 \}

1

D 3

(-1)^{\frac{p-1}{2}}{p-1 \choose{\frac{p-1}{2}}}\equiv 4^{p-1}\pmod{p^{3}}

for all prime numbers

p

p \ge 5

1

D 2

p

is an odd prime. Prove that

\sum_{j=0}^{p}\binom{p}{j}\binom{p+j}{j}\equiv 2^{p}+1\pmod{p^{2}}.

1

D 1

p

is an odd prime, prove that

{k \choose p}\equiv \left\lfloor \frac{k}{p}\right\rfloor \pmod{p}.