A tribute to 743
- I like the number 743.
- Why on earth would that be?
- It is a prime number whose sum of the last two digits equals the first.
- There must be thousands of such numbers!
- Maybe. I also like it because 7n – 4n – 3n is always divisible by 12 no matter what n is.
- That can’t be true! Give me time and I will find a counter example.
November 9th, 2009 at 3:30 am
Multipart proof
First parts by induction:
7**n – 1 is always divisible by 3.
for n=1, 7**1 – 1 = 6; true
for n->n+1, define x as an integer such that 7**n -1 = 3x
7**n = 3x+1
7**(n+1) = 7*7**n = 7*(3x+1) = 21x+7 = 3(7x+2)+1
7**(n+1) – 1 = 3(7x+2)
Partial QED
Similarly,
4**n – 1 is divisible by 3
7**n + 1 is divisible by 4
3**n + 1 is divisible by 4
Of course,
3**n is divisible by 3
4**n is divisible by 4
So
(7**n-1)-(4**n-1)-3**n is a sum of terms divisible by 3
(7**n-1)-(4**n-1)-3**n is divisible by 3
7**n-4**n-3**n is divisible by 3
(7**n+1)-4**n-(3**n+1) is a sum of terms divisible by 4
(7**n+1)-4**n-(3**n+1) is divisible by 4
7**n-4**n-3**n is divisible by 4
7**n-4**n-3**n is divisible by 3*4=12
November 9th, 2009 at 4:32 pm
There’s something wrong in Alan’s proof, because for n=2,
7**n + 1 = 50 which is not divisible by 4.
3**n + 1 = 10 which is not divisible by 4.
What’s more, if n=0, 7^n – 4^n – 3^n = 1 – 1 – 1 = -1 which is not divisible by 12. So let’s suppose n>0.
Lemma 1. If b<c and a^b = a^c mod m, then for all positive integer k, a^(b+k)=a^(c+k) mod m.
Proof: Working modulo m throughout:
a^c – a^b = 0 by supposition ___ [1]
a^(c+k) = a^c * a^k
= (a^c – a^b) * a^k + a^b * a^k
= a^b * a^k by equation [1]
= a^(b+k)
QED.
Modulo 12,
7^1 = 7,
7^2 = 7*7 = 49 = 1
7^3 = 1*7 = 7
therefore, putting m=12, a=7, b=1, c=3 in lemma 1,
7^n = 7 (n odd, at least 1), 1 (n even, at least 2)
4^1 = 4,
4^2 = 4*4 = 16 = 4
therefore, putting m=12, a=4, b=1, c=2 in lemma 1,
4^n = 4 (n at least 1)
3^1 = 3,
3^2 = 2*2 = 9
3^3 = 9*3 = 27 = 3
therefore, putting m=12, a=3, b=1, c=3 in lemma 1,
3^n = 3 (n odd, at least 1), 9 (n even, at least 2)
therefore
7^n – 4^n – 3^n = 7-4-3=0 (n odd, at least 1), 1-4-9=0 (n even, at least 2)
= 0 (n at least 1).
November 9th, 2009 at 6:17 pm
Here is my attempt to prove it by mathematical induction.
Base:
7^1 – 4^1 – 3^1 = 0 which is divisible by 12.
Step:
Assume that 7^k – 4^k – 3^k = 12n for a natural number n.
Want to show that 7^(k+1) – 4^(k+1) – 3^(k+1) = 12m for a natural number m.
Now, let’s find that m.
7^k = 12n + 4^k + 3^k
so
7^(k+1) – 4^(k+1) – 3^(k+1) =
7(12n + 4^k + 3^k) – 4^(k+1) – 3^(k+1) =
7*12n + 4^k(7-4) + 3^k(7-3) =
7*12n + 3*4^k + 4*3^k =
7*12n + 12*4^(k-1) + 12*3(k-1) =
(since k>= 1)
12(7n + 4^(k-1) + 3(k-1))
so m = 7n + 4^(k-1) + 3(k-1)
November 10th, 2009 at 3:26 pm
Lol, I certainly was sloppy. Yes, n>0, a^b is better than a**b, 7^n-1 & 3^n-1 are both divisible by 4, and Jan’s induction is much more elegant than mine.
But I like my approach because it impelled me to think of 321, 532, 954, and even 0xB65.
I’d tell y’all what x is in 743:12=954:x, but I’d hate to get sloppy again *winkwinknudgenudge*.