Proofs of Primes and Logs (Deep Dive)

Q: If x is between 0 and 1, what is the probability that the greatest 
integer ≤ logn(1/x) is odd, in terms of n.
Definition of logn(1/x) = y is ny = 1/x.

S: For the greatest integer ≤ logn(1/x) to equal 1, we must have a value 
between 1/n and 1/n2 . Then for the greatest integer ≤ logn(1/x) to equal 3, we
must have a value between 1/n3 and 1/n4 . This process continues and we 
are left with a geometric sequence:

   (n-1)/n2 + (n-1)/n4 + (n-1)/n6 + (n-1)/n8 …..
= (n-1)/n2
   (n2-1)/n2
= __(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 change it to
59!*-1 (mod 61)
        2^59

We can also convert 59! --> 1(mod p) because:

60!=60*59!
-1 mod 61≡ -1 mod 61* x mod 61
x must be 1 to satisfy this equation.

Then, this equation becomes:
-1 (mod 61) = 61a+N
    2^59
Where N is our answer.

Next, we need to find 2^59 mod 61
To do that, we can make a list.
2^10 --> 48
2^20 --> 47
2^40 --> 13
2^9 --> 24
2^50 --> 14
2^59 --> 31

We can then reformat our equation since the 61a is unnecessary.
-1 mod 61 ≡ N * 31 mod 61
When N=2,
-1 mod 61 ≡ 1 mod 61
Since -1 mod 61 is the inverse of 1 mod 61, we need to find the inverse of 2 mod 61 which is 59.
Therefore, our answer is 59.

I tried this problem with divided by 59 and 67 and they both got 57 and 65.

General problem: Remainder when 1*(1+2)(1+2+3)...(1+2+3+...+p-3+p-2) is divided by p.
This seems to work for all prime numbers p and always gives a result of p-2. 

Generalized:
(p-2)!*(p-1)! = -1 mod p
    2^p-2            2^p-2

Using Fermat's little theorem, a^p-1 ≡ 1 mod p
We can then plug in 2 and a prime to get:
 2^p-1 ≡ 1 mod p because 2 and the prime are relatively prime.

Then, we will divide both sides by 2, to get:
2^p-2 ≡ -2 mod p because since we divided, it is the inverse
-2 mod p= p-2 mod p, so p-2 is our answer for all primes.

Comments

Post a Comment

Popular posts from this blog

Math Formulas + Facts

Sum of cubes and Difference of Cubes a 3  + b 3  = (a + b) (a 2  − a b + b 2  ) a 3  - b 3  = (a - b) (a 2  + a b + b 2  ) Powers to know 5 7  = 78125 5 6  = 15625 5 5  = 3125 Compound Interest A = P(1+r/n) nt Harmonic Series 1+1/2+1/3+1/4+1/5+1/6...+1/n To estimate sum, take the 2 0  term for 1, then take the next 2 1  terms for 2, then take the next  2 2  terms for 3.... Sums: 2 - up to 1/4 2.5 - up to 1/7 3 - up to 1/11 3.5 - up to 1/19 4 - up to 1/31 4.5 - up to 1/51 5 - up to 1/83 Area of Octogon A = 2(1+√2) a 2 Finding the number sides of a regular polygon when you know the interior angle in degrees 180-x° = 360/n Finding total number of diagonals in a polygon n(n-3)/2
Read more

Discovered New Theorem while solving Chinese Remainder Theorem

I was working through some Chinese Remainder Theorem (CRT) problems today (9/24/22), using a new technique introduced in the UKMT Introduction to Number Theory Book. And I noticed a pattern: 9a \equiv 1 \pmod 7 \rightarrow a = 4 7b \equiv 1 \pmod 9 \rightarrow b = 4 Which is cool. But it continues: 7c \equiv 1 \pmod 5 \rightarrow c = 3 5d \equiv 1 \pmod 7 \rightarrow d = 3 And: 35e \equiv 1 \pmod 33 \rightarrow e = 17 33f \equiv 1 \pmod 35 \rightarrow f = 17 Each modular inverse for these pairs were the same! I formed a conjecture, and proved it as a new theorem: Theorem : The solutions a, b to the modular equivalences (n-1)a \equiv 1 \pmod {n+1} (n+1)b \equiv 1 \pmod {n-1} for positive even integers n satisfy a = b = \frac{n}{2}. Update  (12/25/23): More intuitive understanding of Chinese Remainder Theorem (CRT) process. I was looking back at this post, and realized that I had forgotten how the Chinese Remainder Theorem process ...
Read more

Cyclic Quattrocento (Fall 2021 AMC 12B #24)

Image
Fall 2021 AMC 12B #24 Problem:  Triangle ABC has side lengths AB = 11, BC=24, and CA = 20. The bisector of \angle{BAC} intersects \overline{BC} in point D, and intersects the circumcircle of \triangle{ABC} in point E \ne A. The circumcircle of \triangle{BED} intersects the line AB in points B and F \ne B. What is CF? Solution:  We can create a diagram to try to find unique relationships in this problem. By angle chasing in the cyclic quadrilateral ABEC given that AE is the angle bisector of \angle{BAC} we can find that \angle{BAE} = \angle{CAE} = \angle{BCE} = \angle{CBE}. This means that triangle BCE is isosceles and BE = CE, which may be useful later on. Now, we can focus on CF , which is the length we want to find. We can see that ACF has a cevian CB, so we can use Stewart's Theorem (we will "derive" it with the law of cosines here) to solve for CF in terms of other side lengths. We can let \angle{ABC} = \theta which means...
Read more