Problem 4 Number Theory

Problem 4: Number Theory

AIME 1983 #6

Problem: Let an equal 6n + 8n . Determine the remainder upon dividing a83 by 49. Definition: The function ϕ(n) gives the number of integers less than n that are relatively prime to n. It can be computed by  Y 1 1− ϕ(n) = n p p|n

where p ranges over all prime divisors of n. Theorem: If n is a positive integer and a is relatively prime to n, then aϕ(n) ≡ 1 (mod n). (Euler’s Theorem) Theorem: To find the inverse of a (written a−1 ) in some mod b, solve the Diophantine equation ax + by = 1. The value of x will be the inverse. (See Euclidean Algorithm). Solution: First we calculate ϕ(49) = 42. So: 683 + 883 ≡ 641 + 841 ≡ 6−1 + 8−1

(mod 49)

Solving the Diophantine equations: 6x + 49y = 1 gives us x = −8 and y = 1. 8x + 49y = 1 gives us x = −6 and y = 1. 6−1 + 8−1 ≡ −8 + −6 ≡ 35

(mod 49)

Solution was written by Sean Soni and compiled from Art of Problem Solving Forums.