Math Is Fun Forum

[EDIT: No, I got it wrong. Forget what I said previously.]

Anyway …

I suspect that the analytical proof would make use of the following useful result:

If a[sup]m[/sup] = e, it is enough to know that the order of <a> is less than or equal to m. That is enough to answer this particular question.

(And of course since a is not the identity, the order of <a> must be greater than 1.)

#3.

EDIT: Making proof a bit simpler …

I’ll work on #4 and #7 later.

That’s what I did above.

For the first part

it depends on the number. If the number is a perfect square, you divide by 1; if the number has no repeated factors, divide the number by itself (so the quotient is 1 = 1²). If the number is not a perfect square and has repeated factors, pair off all the repeated factors and divide it by the remaining (non-repeated) factors. (For example, for 96 = (2×2)×(2×2)×2×3, divide it by 2×3 = 6.)

Oh, I forgot. I’ve done a course on Mandarin too, so I know a bit of Chinese as well.

However I’m more interested in learning things all by myself; that’s why I’m much more interested in the languages I listed above – because I have learnt / am learning them on my own.

You’re welcome.

Yeah, proofs of even simple results can sometimes be a bit a messy.

Two proofs are given on the Wikipedia page. The first proof looks short and tidy, but I have doubts about its validity. It uses the result that if p and q are coprime (in other words their highest common factor is 1) and pr ≡ ps (mod q), then the p can be cancelled from both sides, leaving r ≡ s (mod q). This is equivalent to saying that if q divides pk and q and p are coprime, then q divides k. But this is a result which may possibly have to be proved using Bézout’s identity – which is what is to be proved!! I mean, there may be more than one way of proving the last result, but I can only do it using Bézout’s identity. If there’s no other way, then the proof would be totally circular.

Yes. It’s called Bézout’s identity.

http://en.wikipedia.org/wiki/B%C3%A9zout%27s_identity

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.

Bingo! You got it at last.

lightning dropped a great big hint with his wild guess, didn’t he?

My next puzzle will be a logic one … watch this space.

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.