Problem 13 - Entrance Test

The product P of numbers ≤100 coprime to 100 is ∏_{gcd(n,100)=1} n. 100=2²·5², so P is the product of units mod 100. By group theory, the product of all units mod m is −1 if m=4, p^k, or 2p^k, else +1. Here m=100, so P≡1 mod 100, but we need v_3(P). The units mod 100 form a group of order φ(100)=40. The product of all elements in a finite abelian group is the product of elements of order 2. There are 3 such elements: 1, 49, 51, 99, so P≡1·49·51·99 mod 100, but we need exponent of 3. Instead, count how many units are divisible by 3: the units are numbers coprime to 100, so not divisible by 2 or 5. Among 1..100, numbers coprime to 100 are 40 numbers. The ones divisible by 3 are those ≡3,9,21,27,33,39,51,57,63,69,81,87,93,99 mod 100, but skip multiples of 2 or 5. The valid ones are 3,9,21,27,33,39,51,57,63,69,81,87,93,99, but remove even and multiples of 5: 3,9,21,27,33,39,51,57,63,69,81,87,93,99, all are odd and not multiples of 5, so 14 numbers. Each contributes at least one 3, and some more: v_3(9)=2, v_3(27)=3, v_3(33)=1, v_3(39)=1, v_3(51)=1, v_3(57)=1, v_3(63)=2, v_3(69)=1, v_3(81)=4, v_3(87)=1, v_3(93)=1, v_3(99)=2. Sum: 2+3+1+1+1+1+2+1+4+1+1+2=20. Thus k=20.