|
Problems & Puzzles:
Conjectures
Conjecture 95.
Pascal triangle (2,1), two Conjectures
On Jan 14, 2023, Davide Rotondo
sent these nice Conjectures:
1
2. 1.
2. 3. 1.
2. 5. 4. 1.
2. 7. 9. 5. 1.
2. 9. 16. 14. 6. 1.
2. 11. 25. 30. 20. 7. 1.
2. 13. 36. 55. 50. 27. 8. 1
...
First conjecture.
If the second coefficient starting from the
right of a row is a prime number, then also the
other coefficients in the same row will be divisible
by the second coefficient. To do this, the
coefficients must be properly corrected as follows:
3rd coefficient +1
4th coefficient -2
5th coefficient +3
6th coefficient -4
...
where +1,-2,+3,-4, ... are the natural
numbers with alternating signs.
For example
the coefficients in the fifth row have
2. 7. 9. 5. 1.
(9+1)/5 = 2
(7-2)/5 = 1
(2+3)/5 = 1
5 is a prime number
Second
conjecture
If the second coefficient from the right is
prime, then also the other coefficients taken
diagonally to find the Lucas numbers excluding 1
are divisible by the second coefficient.
For example in the seventh row we have 7 as the
second coefficient and on its diagonal 1. 7.
14. 7. that are all divisible by 7.
7 is a prime number
Q1. prove that the two conjectures are true
or false.
During the week 21-27 Jan 2923, contributions from
Mauro Fiorentini, Jan van Delden, Emmanuel Vantieghem,Giorgos
Kalogeropoulos
***
Mauro wrote:
Both conjectures are true.
First one.
The k-th term of row n is the absolute values of
the (n – k)-th
coefficient of the Dickson polynomials of first
kind (
http://www.bitman.name/math/article/1279)
D2n – k – 1(α, x) and the
next to last number of row n (numbering from 1)
is n.
The k-th coefficient of Dn(α, x) is n / (n – k) *
C(n – k, k), thus the
k-th term of row n is P(n, k) = (2n – k – 1) / (n
– 1) * (n – 1)! / ((n
– k)! * (k – 1)!) ≡ –(k + 1) * (n – 2)! / ((n –
k)! * (k – 1)!) mod n.
Now if n is prime, from wilson's theorem (n – 2)!
≡ 1 mod n and ((n –
k)! * (k – 1)!) ≡ (–1)^k mod n, so P(n, k) ≡
(–1)^(k + 1) * (k + 1) mod
n.
Second one.
The diagonals are the absolute values of the
coefficients of a single
Dickson polynomials of first kind.
For example D7(α, x) = x7 – 7αx5 + 14α2x3 – 7α3x.
They are D(n, k) = n / (n – k) * C(n – k, k); as
C(n – k, k) is an
integer, if n is prime, all of them, except the
first one, are
multiples of n so all numbers of the diagonal,
except 1, are multiples
of n.
***
Jan wrote:
My contribution in the form of a
pdf, this way the typesetting
is nicer, I think.
***
Emmanuel wrote:
First of all, let us denote
the rows of the triangle by
T(0), T(1), T(2), ...
and let the elements of the
row T(n) be denoted as
T(n,0), T(n,1), T(n,2),
..., T(n,n).
Proof of conjecture 1 :
We know (following the given link) that T(n) is the
coefficient list of the polynomial
(2 + x)(1 + x)^(n-1) = (1 + (1 + x))(1 + x)^(n-1) = (1 +
x)^(n-1) + (1 + x)^n
(the powers of x must being in ascending order).
Thus,we have :
T(n,k) = B(n-1,k) + B(n,k) (*)
where B(m,u) is the binomial coefficient m(m-1)...(m-i+1)
/ u! ( and 0 when u > m).
Let p, the second element of T(p-1) counted from the
right be an odd prime.
For k = 1 to p - 2 we then have
B(p - 2, k) = (p - 2)(p - 3) ...(p - k - 1) / k! ===
(-2)(-3)...(-k-1) / k! === (k+1)*(-1)^k (mod p)
and
B(p - 1, k) = (p - 1)(p - 2) ...(p - k) / k! ===
(-1)(-2)...(-k) / k! === (-1)^k (mod p).
Thus :
T(p - 1,k) === (k + 2)*(-1)^k (mod p).
(*)
Since T(p - 1,0) = 2, this congruence holds for k = 0, 1,
..., p - 1.
To make this result match with the formulation of the
conjecture we sometimes must replace (*) by
T(p - 1,k) === +or -p + (k + 2)*(-1)^k (mod p), for k =
0 to p - 1,
which is precisely the formulation of the conjecture 1.
Proof of conjecture 2 :
For n > k >= 1 we have :
T(n,k) = [(n-1)(n-2)...(n-k) + n(n-1)...(n-k+1)] / k! =
(n-1)(n-2)...(n-k)*[n - k +n] / k!.
If we take k and n such that 2n - k = p, an odd prime,
then T(n,k) will be divisible by p.
The smallest n for which this is the case is (p + 1) / 2
= u. The next cases are then T(u+1, 3), T(u+2, 5), ...,
T(p-1, p-2) = p.
These are precisely the elements on the "diagonal" as
formulated in conjecture 2.
***
Giorgos wrote:
The first conjecture
is true.
For binomial(n,k) we will use the notation b(n,k).We can
express our starting triangle in the form:
T(n,k) = b(n, k+1) - b(n-2, k-1) for n>1 and -1<= k <= p-2
If we adjust the coefficients with +1,-2,+3,-4,+5... then we
get
T(n,k) = b(n, k+1) - b(n-2, k-1) + (-1)^(k+1)*k for n>1
and -1<= k <= p-2.
We want b(n, k+1) - b(n-2, k-1) + (-1)^(k+1)*k ≡ 0 mod n
for any n prime.
If p is prime we know that b(p,k) ≡ 0 mod p for 0<k<p
So, in our case b(n, k+1) ≡ 0 mod n if n is prime for
-1<k<p-1.
Now, we have to show that - b(n-2, k-1) + (-1)^(k+1)*k ≡ 0
mod n for any n prime.
Let's assume that it is true
b(n-2, k-1) ≡ (-1)^(k+1)*k mod n for any n prime.
(n-2)! / ((n-1-k)! (k-1)!) ≡ (-1)^(k+1)*k mod n for any n
prime.
(n-2)! / ((n-1-k)! (k-1)! * k) ≡ (-1)^(k+1) mod n for any
n prime because gcd(k,n)=1
(n-2)! / ((n-1-k)! k!) ≡ (-1)^(k+1) mod n for any n
prime
(n-1)*(n-2)! / ((n-1-k)! k!) ≡ (n-1) (-1)^(k+1) mod n
for any n prime
b(n-1, k) ≡ (n-1) (-1)^(k+1) mod n for any n prime
We know from Lucas that b(p-1, k) ≡ (-1)^k mod p for p
prime and 0<k<p-1
So, (-1)^k ≡ (n-1) (-1)^(k+1) mod n for any n prime
1 ≡ - (n - 1) mod n for any n prime
n ≡ 0 mod n for any n prime
***
|
