Mathematical Induction
A page of uncommon problems, most closely connected with number theory.
Some properties may be proved in different ways.For more exercises, problems,
puzzles, games, math riddles, brain teasers, etc. to see the site :
Art of Problem Solving
New Problems
- Let p be an odd prime and let d be a divisor of p-1, it is known that the congruence ad ≡ 1 ( mod p) has exactly d distinct solutions.
Let a1,a2,...,ad those solutions.
Prove that ∑ i=1d ain ≡ cn d ( mod p) where cn=1 if n
is divisible by d and 0 otherwise.
See solution
Comment:Another solution is using the
following property:the number of integers between 1 and p-1 which have
order d is phi(d).
- Prove or disprove the following property: given the statement of Problem 23 and
let f(n) be:
a(p-1)n+4+b(p-1)n+4+(a+b)(p-1)n+4 . Then:
12f(n)≡ ((n-3)(n-4)f(0)) ( mod p3) for all integers n ≥0 .
See Naoki Sato's solution (Problem 32)
Comment: Using Naoki Sato's formula for gk(x) I can to prove that the propery is true for n=0 , n=6
and n=12.Hence using the result of Problem 27 , the
property is true for all n ≥ 0. An alternative for the
final part of Naoki Sato's proof.
-
Let p > 3 be a prime dividing x2+x+1 (1,x relatively prime).
Let f(n) be (1+x){(p-1)n+1}-x{(p-1)n+1}-1 then:
6f(n)≡n(n-1)x(x+1)((x2+x+1)2)mod p3 for all n ≥ 0.
Hint:Let gk(x) be (1+x)(6k+1)-x(6k+1)-1 then
gk(x) = Qk(x)x(x+1)(x2+x+1)3 + k(6k+1)x(x+1)(x2+x+1)2
where Qk(x) is a polynomial
with integer coefficients.
Link of interest:
Sums of Powers in Terms of Symmetric Functions
Interactive Induction
See PHP Script for Problem 21.
Contact
Email Form
