Proofs of Primes and Logs (Deep Dive)
Q: If x is between 0 and 1, what is the probability that the greatest integer ≤ log n (1/x) is odd, in terms of n. Definition of log n (1/x) = y is n y = 1/x. S: For the greatest integer ≤ log n (1/x) to equal 1, we must have a value between 1/n and 1/n 2 . Then for the greatest integer ≤ log n (1/x) to equal 3, we must have a value between 1/n 3 and 1/n 4 . This process continues and we are left with a geometric sequence: (n-1)/n 2 + (n-1)/n 4 + (n-1)/n 6 + (n-1)/n 8 ….. = (n-1)/n 2 (n 2 -1)/n 2 = __ (n-1)__ (n+1)(n-1) = _ 1 _ (n+1) Q: What is the remainder when (1)(1+2)(1+2+3)(1+2+3+4)...(1+2+3..+58+59) is divided by 61? S: We can rewrite this as: 1*2*2*3*3*4*4*5*5*6*...*58*59*59*60 2^59 We can then change this to: 59!*60! 2^59 By Wilson's formula, for any prime p , (p-1)! + 1 ≡ 0 (mod p) We can then ...