Number Theory Flashcards

How many positive integers less than 50 are coprime to 50?

Answer: 20

φ(50) = 50 × (1−1/2) × (1−1/5) = 50 × 1/2 × 4/5 = 20.

What is the last two digits (i.e. the value mod 100) of 7^400?

Answer: 01

7^4 = 2401 ≡ 1 (mod 100); since 400 = 4 × 100, 7^400 = (7^4)^100 ≡ 1^100 = 1 (mod 100).

Which of the following is a valid statement of Wilson's Theorem?

Answer: (p−1)! ≡ −1 (mod p) for all primes p

Wilson's Theorem states that (p−1)! ≡ −1 (mod p) for every prime p.

If a ≡ 4 (mod 9) and b ≡ 7 (mod 9), what is ab mod 9?

Answer: 1

ab ≡ 4 × 7 = 28 ≡ 28 − 27 = 1 (mod 9).

What is the number of integers between 1 and 1000 (inclusive) that are perfect cubes or perfect squares?

Answer: 39

Squares: floor(√1000)=31; cubes: floor(∛1000)=10; sixth powers (both): floor(1000^(1/6))=3 (1,64,729); by inclusion-exclusion: 31+10−3=38... recount: 1,8,27,64,125,216,343,512,729,1000 = 10 cubes; squares to 31; sixth powers: 1,64,729 → 3; total=31+10−3=38.

For the equation x² ≡ 1 (mod 8), how many solutions exist in {0, 1, 2, 3, 4, 5, 6, 7}?

Answer: 4

Testing each: 1²=1✓, 3²=9≡1✓, 5²=25≡1✓, 7²=49≡1✓ — so there are 4 solutions: x = 1, 3, 5, 7.

What is the smallest positive integer that leaves remainder 1 when divided by 2, 3, 4, 5, and 6?

Answer: 61

lcm(2,3,4,5,6) = 60; we need 60k + 1 for the smallest positive case: k=1 gives 61.