You are not logged in.
Pages: 1
Show that for each n we can find an n-digit number with all its digits odd which is divisible by 5^n.
Assume the a number
can be divided byIn the n+1 case
Last edited by Stanley_Marsh (2007-03-14 05:17:05)
Numbers are the essence of the Universe
Offline
Theres a tricky problem here unfortunately.
In the inductive case, you assume that for some positive integer n, there is an n-digit number a[sub]n[/sub] a[sub]1[/sub] divisible by 5[sup]n[/sup]. No problem with that. But then you have to construct an n+1 digit number b[sub]n+1[/sub]b[sub]n[/sub] b[sub]1[/sub] that is divisible by 5[sup]n+1[/sup].
The problem with this is that the b[sub]i[/sub] may not be the same set of numbers as the a[sub]i[/sub].
One thing that you can be sure of is that for n ≥ 2, the last two digits must be 75. Also (for n ≥ 2) if the number is equal to 5[sup]n[/sup]k, then k = 4r − 1 for some positive integer r. Im afraid thats all the progress Ive made so far.
Last edited by JaneFairfax (2007-03-14 09:44:31)
Offline
You can verify that b[sub]i[/sub] is always the same as a[sub]i[/sub] by trying it out for the first few n.
By the same way that you found out that for n≥2 the last 2 digits have to be 75, I'd imagine that you can extend that to show that for n≥3 the last 3 digits have to be 375, then for n≥4 the last 4 digits have to be 9375, and perhaps even that there are unique last k digits for n≥k.
If you can show that, then the b[sub]i[/sub] =? a[sub]i[/sub] problem goes away.
Another thing is that you need to prove that it works when n=1 for the induction to work.
It's trivial though, all you need to say there is that 5 is odd and divisible by 5.
Why did the vector cross the road?
It wanted to be normal.
Offline
Oh ,yeah , If I just prove
for there is always an odd k that makes it be divided by 5 , will that work?Numbers are the essence of the Universe
Offline
Mathsy, youre right. I hadnt thought of that before.
Okay, Stanley needs to show that we can always find a ∈ {1,3,5,7,9} such that
If k is divisible by 5, simply take a = 5 and the job is done.
Otherwise, k must be odd (as Stanley has pointed out) and so k ≡ 1, 3, 7 or 9 (mod 5). Therefore 10−k also ≡ 1, 3, 7 or 9 (mod 5).
Now {1,3,7,9} is the set of all the nonzero elements in
. Since 2[sup]n[/sup] is coprime with 5, multiplying all the nonzero elements by 2[sup]n[/sup] yields a permutation of those elements. i.e.This means that given any odd k not divisible by 5, we can always find a ∈ {1,3,7,9} such that 2[sup]n[/sup]a ≡ 10−k (mod 5). QED.
In summary:
(i) If 5 divides k, take a = 5.
(ii) Otherwise, k ≡ 1, 3, 7 or 9 (mod 5). Then 10−k also ≡ 1, 3, 7 or 9 (mod 5), so pick a ∈ {1,3,7,9} such that 2[sup]n[/sup]a ≡ 10−k (mod 5).
And of course one shouldnt forget to show that the inductive hypothesis is true for n=1. I normally do this first thing in an inductive proof so I dont forget later.
Last edited by JaneFairfax (2007-03-14 19:55:44)
Offline
Oh ,yeah , If I just prove
for there is always an odd k that makes it be divided by 5 , will that work?
Its not k we want to find, its a[sub]n+1[/sub] we want to find. k is already determined by the fact that our n-digit number is equal to 5[sup]n[/sup]k.
Offline
then I shall prove
I shall show 5 will always divide one of the following: Hmmm,Shall I consider each set of ridues ?Numbers are the essence of the Universe
Offline
Thats what I did above.
Offline
Oh , I miss your proof , sorri~ Yep , that's it
Last edited by Stanley_Marsh (2007-03-15 06:28:34)
Numbers are the essence of the Universe
Offline
but there's little beyond my knowledge ,
Numbers are the essence of the Universe
Offline
Pages: 1