Formula for the n-th prime. (1 Viewer)

seanieg89 · Jul 9, 2013

Lies your teachers have told you Vol1: There is no "formula" for prime numbers.

A roughly MX2 level question attached.

PS, quicker ways to derive such formulae certainly exist. As an easier side exercise which involves no modular arithmetic, try to construct a formulae for the n-th prime number that works by "testing primality by checking divisibility by all smaller numbers".

Sy123 · Jul 9, 2013

seanieg89 said:
Lies your teachers have told you Vol1: There is no "formula" for prime numbers.

A roughly MX2 level question attached.

(1): $\frac{a-a}{m} = 0 = n \ \ n \in \mathbb{Z}$

(2): $\frac{a-b}{m} = n \ \ n \in \mathbb{Z} \ \ \ \fbox{1}$

$-1 \times \fbox{1} \Rightarrow \frac{b-a}{m} = -n = k \ \ k \in \mathbb{Z}$

$\therefore \ b \equiv a \ \mod{m} \ \ $if$ \ \ a \equiv b \ \mod{m}$

n, k, r are all integers

(3): $\frac{a-b}{m} = n \ \ \fbox{1} \ \ \frac{b-c}{m} = k \ \ \fbox{2}$

$\fbox{1} + \fbox{2} \rightarrow \frac{a-c}{m} = (n+k) = r \ \ \therefore \ a \equiv c \ \mod{m}$

n, k, r, s are integers

(4): $a-c = mn \ \ \fbox{1} \ \ b-d = mk \ \ \fbox{2}$

$\fbox{1} + \fbox{2} \Rightarrow \ (a+b) - (c+d) = m(n+k) = mr \ \ \therefore \ a+b \equiv c+d \ \mod{m}$

$b \times \fbox{1} + c \times \fbox{2} \Rightarrow \ ab - cd = m(nb + kc) = m(s) \ \ \therefore ab \equiv cd \ \mod{m}$

====

Just one question, for the next part, is it a proof for all primes below m-1 or at least 1 prime, satisfies ab equiv 1 ?
I'll have a go at the next parts later, I probably won't get it though.

seanieg89 · Jul 9, 2013

Sy123 said:
(1): $\frac{a-a}{m} = 0 = n \ \ n \in \mathbb{Z}$

(2): $\frac{a-b}{m} = n \ \ n \in \mathbb{Z} \ \ \ \fbox{1}$

$-1 \times \fbox{1} \Rightarrow \frac{b-a}{m} = -n = k \ \ k \in \mathbb{Z}$

$\therefore \ b \equiv a \ \mod{m} \ \ $if$ \ \ a \equiv b \ \mod{m}$

n, k, r are all integers

(3): $\frac{a-b}{m} = n \ \ \fbox{1} \ \ \frac{b-c}{m} = k \ \ \fbox{2}$

$\fbox{1} + \fbox{2} \rightarrow \frac{a-c}{m} = (n+k) = r \ \ \therefore \ a \equiv c \ \mod{m}$

n, k, r, s are integers

(4): $a-c = mn \ \ \fbox{1} \ \ b-d = mk \ \ \fbox{2}$

$\fbox{1} + \fbox{2} \Rightarrow \ (a+b) - (c+d) = m(n+k) = mr \ \ \therefore \ a+b \equiv c+d \ \mod{m}$

$b \times \fbox{1} + c \times \fbox{2} \Rightarrow \ ab - cd = m(nb + kc) = m(s) \ \ \therefore ab \equiv cd \ \mod{m}$

====

Just one question, for the next part, is it a proof for all primes below m-1 or at least 1 prime, satisfies ab equiv 1 ?
I'll have a go at the next parts later, I probably won't get it though.

Whoops, typo.

a,b should be chosen from {1,2,...,p-1}, and we are proving that these "inverses" exist for any prime p. Ie we are just specialising to the case where m=p is prime.

PDF is fixed.

Formula for the n-th prime. (1 Viewer)

seanieg89

Well-Known Member

Attachments

Sy123

This too shall pass

seanieg89

Well-Known Member

Users Who Are Viewing This Thread (Users: 0, Guests: 1)