Math Is Fun Forum

Stanley_Marsh

Member

Registered: 2006-12-13

Posts: 345

Check my proof guys

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 by

In the n+1 case

Now we have to prove

because all digits have to be odd , then k must be odd, and

,

Let m be odd , then there will always be solution to k and

Last edited by Stanley_Marsh (2007-03-14 05:17:05)

---

Numbers are the essence of the Universe

JaneFairfax

Member

Registered: 2007-02-23

Posts: 6,868

Re: Check my proof guys

There’s 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. I’m afraid that’s all the progress I’ve made so far.

Last edited by JaneFairfax (2007-03-14 09:44:31)

mathsyperson

Moderator

Registered: 2005-06-22

Posts: 4,900

Re: Check my proof guys

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.

Stanley_Marsh

Member

Registered: 2006-12-13

Posts: 345

Re: Check my proof guys

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

JaneFairfax

Member

Registered: 2007-02-23

Posts: 6,868

Re: Check my proof guys

Mathsy, you’re right. I hadn’t 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 shouldn’t forget to show that the inductive hypothesis is true for n=1. I normally do this first thing in an inductive proof so I don’t forget later.

Last edited by JaneFairfax (2007-03-14 19:55:44)

JaneFairfax

Member

Registered: 2007-02-23

Posts: 6,868

Re: Check my proof guys

Oh ,yeah , If I just prove

for

there is always an odd k that makes it be divided by 5 , will that work?

It’s not k we want to find, it’s 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.
­

Stanley_Marsh

Member

Registered: 2006-12-13

Posts: 345

Re: Check my proof guys

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

JaneFairfax

Member

Registered: 2007-02-23

Posts: 6,868

Re: Check my proof guys

That’s what I did above.

Stanley_Marsh

Member

Registered: 2006-12-13

Posts: 345

Re: Check my proof guys

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

Stanley_Marsh

Member

Registered: 2006-12-13

Posts: 345

Re: Check my proof guys

but there's little beyond my knowledge ,

---

Numbers are the essence of the Universe