Fermat's theorem about prime numbers

I could also prove the fermat's theorem about prime numbers,

(2^p - 1) == 1 (mod p) for any prime number. The proof uses binomial expansion.

sum of all nCr, r from 0 to n is 2^n. If we keep a prime number p for n,

pCr, r from 0 to p is 2^p.
In these co-efficients, except pC0, and pCp, everything else must have p as a factor, since, p is a prime.

So, finally, pC0 + pCp + pK = 2^p.
pK + 1 = 2^p - 1.

So, (2^p - 1) == 1 (mod p).

I was pleasantly surprised about this, although.
(This is called Fermat's little theorem)

The statement is more generic. If p is a prime, for any integer a, a^p == a (mod p).
This can be proved using induction, on a.

1^p == 1 (mod p) trivial, we have also seen 2^p == 2 (mod p) incidentally.
Also assume that n^p == n (mod p).
(n + 1)^p = Sum from 0 to p (pCr * n^r)

All terms except pC0 and pCp have p as the factor. So,

pC0 + pCp * n^p + pK = (n + 1)^p
n^p == n (mod p)
So,
pK + (n + 1) = (n + 1) ^p
So, (n + 1) ^p == (n + 1) mod p

Puzzle for guessing by not knowing

I came across this puzzle sometime back. There are two guys A and B. And there are two numbers x and y, which are between 2 and 9 (digits, 2 <= x <= y <= 9). A knows their sum, and B knows their product. And the dialogue between them goes as follows:

A: I don't know what the numbers are.
B: I don't know the numbers as well.
A: I still don't know what the numbers are.
B: Same, I don't know the numbers.
A: I still don't know the numbers.
B: I know the numbers now

What is the value of x + y?

I also got some interest in the problem of finding, a number between 1 and n^2, which has the highest number of factors (including 1 and itself). One can easily prove that such a number is not divisible by any prime number >= n, for n > 4. Try it.

Of course, this problem can be formalized as optimization problem.
Given that,

k1*log(2) + k2*log(3) + k3*log(5) + .... all prime logs with co-efficients < log(n)
(or, equivalently, 2^k1*3^k2*5^k3*7^k4*..... < n)

maximize (k1 + 1)*(k2 + 1)*(k3 + 1)*(k4 + 1)*....

Finally the number, with most factors is given by 2^k1*3^k2*5^k3*7^k4*.....

Also, I believe n! is not a square number, for any n > 1. Can you prove it? I think it involves the proven conjecture that between any 2n and 3n, there exists a prime number. Can you prove using that statement? Can we do without it?

In fact, I think n! is not any power of any number, not k^2, k^3, k^4 etc... Can you prove this also?

Ok, I give up. I tried doing 101-200 numbers, but, could not get satisfying stuff. Please fill in the gaps.

4!*4 + sqrt(4)/.4
4^4*.4 - .4
103
4!*4 + 4 + 4
(44 - sqrt(4))/.4
4!*4 + 4/.4
107
4!*4 + 4!/sqrt(4)
(44 - .4)/.4
44/.4
(44 + .4)/.4
44/.4 + sqrt(4)
113
44/.4 + 4
(44 + sqrt(4))/.4
4!*sqrt(4)/.4 - 4
117
4!*sqrt(4)/.4 - sqrt(4)
(4!*sqrt(4) - .4)/.4
4!*sqrt(4)/.4
(4!*sqrt(4) + .4)/.4
4!*sqrt(4)/.4 + sqrt(4)
123
4!*sqrt(4)/.4 + 4
(4!*sqrt(4) + sqrt(4))/.4
4^4/sqrt(4) - sqrt(4)
(4^4 - sqrt(4))/sqrt(4)
4^4/sqrt(4)
(4^4 + sqrt(4))/sqrt(4)
4^4/sqrt(4) + sqrt(4)
131
4^4/sqrt(4) + 4
133
44/.4 + 4!
135
4*(4! + 4/.4)
137
(4! - .4)/.4 * sqrt(4)
139
(4^4 + 4!)/sqrt(4)
141
(4! + .4)/.4 * sqrt(4)
143
((4!)^sqrt(4))/4
(4!/.4 - sqrt(4))/.4
4!/.4/.4 - 4
147
4!/.4/.4 - sqrt(4)
(4!/.4 - .4)/.4
4!/.4/.4
(4!/.4 + .4)/.4
4!/.4/.4 + sqrt(4)
153
4!/.4/.4 + 4
(4!/.4 + sqrt(4))/.4
(4!/4)!/4 - 4!
157
158
159
(4!/.4 + 4)/.4
161
162
163
164
165
166
167
4!*(4 + sqrt(4)) + 4!
((4! + sqrt(4))^sqrt(4))/4
(44 + 4!)/.4
171
44*4 - 4
173
((4!/4)! - 4!)/4
(4! + 4)/.4/.4
(4!/4)!/4 - 4
177
(4!/4)!/4 - sqrt(4)
((4!/4)! - 4)/4
(4!/4)!/4
((4!/4)! + 4)/4
(4!/4)!/4 + sqrt(4)
183
(4!/4)!/4 + 4
185
((4!/4)! + 4!)/4
187
4!*(4 + 4) - 4
189
4!*(4 + 4) - sqrt(4)
191
4!*(4 + 4)
193
4!*(4 + 4) + sqrt(4)
195
4!*(4 + 4) + 4
197
198
199
(4!*4 + 4)*sqrt(4)

Do you know, every prime number p > 3, satisfies the following:

p^2 = 24*k + 1, for some number k.
Also, every prime p > 30,
p^4 = 240*k + 1, for some number k.

Try proving them. Also, an extension of Eratoshenes sieve method gives the following approximation of ratio of first n numbers to primes in them:

Number of primes ~= n*(1 - 1/2)(1 - 1/3)(1 - 1/5)(1 - 1/7)(1 - 1/11).....(1 - 1/pk) where pk is the largest prime < sqrt(n).

Ratio is thus, approximately, (1 - 1/2)(1 - 1/3)(1 - 1/5)(1 - 1/7)(1 - 1/11).....(1 - 1/pk)

Also, a composite number (n) definitely has a prime factor <= sqrt(n). Do you know? Try proving it.

Reverted the look back to original one, retro look is gone now.