| Posted on Sunday, 22 December, 2002 - 09:39 pm: |
It is actually not precisely a riddle because I don't know the answer.
Let N be an integer that is not a power of 10 and composed of only 1s and 0s.
Can N be a square number? If so, are there infinitely many square numbers of this kind?
I managed to prove that if N is a sequence of 1s then N is not a square number.
Any Suggestions?
If anybody knows the answer please post only a tip so it wont spoil it for me and the others.
Thanks,
Yatir
| Posted on Monday, 23 December, 2002 - 12:53 am: |
It's easy to show that if there is one such N, then there is an infinite number of such N. Too tired to think about the rest of it now though.
Richard.
| Posted on Monday, 23 December, 2002 - 07:08 am: |
Why is that?
| Posted on Monday, 23 December, 2002 - 09:50 am: |
yatir,
what Richard is trying to say i think is,
if N is a perfect square,then 100N,10000N,... are all perfect squares ..
Now,as far as the problem is concerned,it is quite clear that,
if M2 =N,then either M=10k+1 or 10k+9 where k is any integer....
however,i don't see any immediate way to find a contradiction(or a way to prove the existence of M)!!!!
love arun
| Posted on Monday, 23 December, 2002 - 10:03 am: |
Thanks Arun,
OR M=10k
| Posted on Monday, 23 December, 2002 - 10:27 am: |
Yatir,
if M=10k,then k=10p+1 or 10p+9
if k=10p then p=10q+1 or 10q+9
and so on...
so the base cases are nothing but
M=10k+1 or 10k+9
love arun
| Posted on Monday, 23 December, 2002 - 05:05 pm: |
You're right Arun.
I think I can prove there are none!
Let N be a square number satisfying our conditions.
If N ends in a zero it must also end in 2 zeros, so lets divide it by 100, and do so until it ends in 1.
N-3 must end in either 08 or 98, both divisible by 4...So N=4k+3 meaning that it can't be a square number, hence a contradiction!
Yatir
| Posted on Monday, 23 December, 2002 - 05:19 pm: |
I think that works!!Nice proof!
love arun
| Posted on Monday, 23 December, 2002 - 05:21 pm: |
This result surprised me. I was almost sure that there must be one...
| Posted on Monday, 23 December, 2002 - 06:12 pm: |
Yatir, how is 98 divisible by 4?
| Posted on Monday, 23 December, 2002 - 06:15 pm: |
You are right Angelina...I just saw that...I have no idea where my mistake came from...
Yatir
| Posted on Monday, 23 December, 2002 - 07:18 pm: |
ok we are back to square 1.
love arun
| Posted on Monday, 23 December, 2002 - 07:33 pm: |
Not quite, we proved the case when N = 100k+11 will never be a square.
Now we just need to consider the case when N = 100k+1
| Posted on Monday, 23 December, 2002 - 07:53 pm: |
yes angelina
i was thinking of that myself a minute after i posted that message.
as for the other case,
i think N=4k+5 gives us an equation..
i think only for k=5,N becomes a perfect square.Only thing remaining is to prove that k=5 is the only solution.
love arun
| Posted on Monday, 23 December, 2002 - 08:04 pm: |
Arun N=4k+5 is identical to N=4j+1
think of 81 and 121
and there are many more.
| Posted on Monday, 23 December, 2002 - 08:08 pm: |
Yatir,
now that you mention ... err .. my brain thought of it too
ok so we are back to square 51.
love arun
| Posted on Monday, 23 December, 2002 - 09:55 pm: |
Does anyone know how to prove no multiple of 3 can consist solely of 1s and 0s? I've been trying to solve this riddle using a different method, but can't see how to prove this (I'm not even sure if it's true!).
| Posted on Monday, 23 December, 2002 - 10:14 pm: |
Philip, it can be proved that every integer has a multiple that consists entirely of 0s and 1s.
Paul
| Posted on Monday, 23 December, 2002 - 10:26 pm: |
Okay, thanks... I thought that this was a bit dubious, but couldn't elicit a counterexample from small multiples. Could you give me this proof please?
| Posted on Monday, 23 December, 2002 - 10:47 pm: |
This is a procedure for generating a multiple of any natural number N that consists entirely of 0s and 1s, written in Word (I didn't discover this myself - someone else showed me!). Notice that it doesn't necessarily generate the smallest such multiple of N, but it does nonetheless prove the existence of such a multiple.
 Proofproof.doc (33 k) |
Paul
| Posted on Tuesday, 24 December, 2002 - 07:41 am: |
Thanks for both of the methods... Paul, your proof has a number of characters that my computer can't read for some reason... I'll set to deciphering it when I get back from work!
| Posted on Tuesday, 24 December, 2002 - 09:40 am: |
Hmm ... OK (curse Microsoft!), here is a pdf version, instead.
 Proofproof.pdf (47 k) |
Paul
| Posted on Tuesday, 24 December, 2002 - 09:57 am: |
How do you convert a word document to an acrobat file?
| Posted on Tuesday, 24 December, 2002 - 11:08 am: |
Err ... I don't know! That's not what I did - I copied it into a LaTeX editor.
Paul
| Posted on Tuesday, 24 December, 2002 - 11:36 am: |
Converting Word Docs to PDF
1.install a postscript printer driver (in file mode)
2.open the doc file and "print"(remember here it is referred to as Save)it out as .ps file
3.Use acrobat distiller or ghostview to convert .ps file to .pdf
hope this is understood.
love arun
| Posted on Tuesday, 24 December, 2002 - 11:46 am: |
An alternative way to convert *.doc to *.pdf is to install OpenOffice (or to be really pedantic, OpenOffice.org), open the doc file and export as pdf.
Kerwin
| Posted on Tuesday, 24 December, 2002 - 02:43 pm: |
Excellent... that works fine, thanks very much.
| Posted on Tuesday, 24 December, 2002 - 04:50 pm: |
Thanks.
Kerwin, I installed OpenOffice (cool program BTW), and I don't have an option to export/save as PDF...
Yatir
| Posted on Tuesday, 24 December, 2002 - 09:00 pm: |
i have "SOT office".however there is no option for conversion in that too.(Also this soft seems to be very slow and sometimes gets hung up in the middle)
love arun
| Posted on Tuesday, 24 December, 2002 - 10:46 pm: |
Yatir, you will need OpenOffice.org 643C. The file is quite large (59MB for Win32).
Kerwin
| Posted on Tuesday, 24 December, 2002 - 11:13 pm: |
Lol, back to the problem!
What was the way you used, Philip?
I started off by considering the cases of n (let n2 =N) = 10a+1 and 10a+9 and find out what a can hold. Now we've proved the cases when S (S = N dividing by powers of 100 until we reach 1) ends with 11, we just need to do the same when S end with 01.
I think I might have proven it for the case n=10a+9 (still putting everything together and checking through) but not quite for 10a+1 though.
Hows everyone else doing?
| Posted on Thursday, 26 December, 2002 - 10:26 pm: |
Dunno if this is right.
As you have already mentioned if N exists it must have and even number of 0s (or no 0s) on the end. Each pair correspond to single 0s on the end of n (where n2 = N).
We can therefore ignore these 0s and consider only the case where N ends in a 1. It should be noted that this also means that if there is one solution there are infinite solutions.
A Proof by induction:
Let Ck denote the statement N = 1 (mod102k )
I wish to show that Ck is true for all k, thus showing that N = 1
1. All square numbers are either 0 or 1 (mod 4). As N ends in a 1 it must be 1 (mod 4). Notice that 100m + 11 = 3 (mod 4) N ends in .....01. So C1 is true.
2. Assume N = 1 (mod 22k ). I need to show N = 1 (mod 102(k+1) )
Part 1
As N is a perfect square, N = { 1 or 4 or 9 or ..... or (2k+1 -1)2 } (mod 22(k+1) )
The largest it could be out of these choices is (2k+1 -1)2
However 102k > (2k+1 -1)2 (providing k> 0 , which it is) and we know from the induction assumption that N = 1 (mod 10+(2k)) and so we can see N = 1 ( mod 22(k+1) )
Part 2
As N = 1 (mod 102k ) there are 4 possibilities:
N = 1 (mod 102(k+1) )
N = 102k + 1 (mod 102(k+1) )
N = 102k+1 + 1 (mod 102(k+1) )
N = 102k+1 + 102k + 1 = 11 x 102k + 1 (mod 102(k+1) )
Using the result from Part 1, that N = 1 ( mod 22(k+1) ), you can see that only the first of these possibilities is possible.
I have shown N = 1 (mod 102(k+1) ), so Ck => Ck+1 and as C1 is true Ck is true for all k. Therefore any N must consist of a 1 preceded by an infinite number of 0s and so is not possible.
| Posted on Thursday, 26 December, 2002 - 10:39 pm: |
Oh dear, when checking my "no multiples of 3 consist of solely 1s and 0s" hypothesis, I actually checked powers... obviously 111, 111111, 1011, 10101, 10100000001, etc. are all divisible by 3... perhaps I should do maths whilst more awake!
| Posted on Thursday, 26 December, 2002 - 10:43 pm: |
Maybe I'm wrong, but it seems as if 1 preceeded by any number of 0s would still be a power of 10 and so not count.
Very nice proof by the way.
Chris
| Posted on Thursday, 26 December, 2002 - 10:59 pm: |
Tom, I'm probably just being stupid, but I can't follow your proof. I don't understand your reasoning for the final line of part 1. To see if I could grasp the general idea from a few specific examples, I tried k=3, which didn't work... please could you explain
| Posted on Saturday, 28 December, 2002 - 12:33 am: |
Chris
You are right of course. I had meant to say that (but probably didn't). As N is 1 (or 1 followed by even numbers of 0s) the answer to the original question is "no". There is no N, where N is a perfect square made from 1s and 0s and not a power of 10.
Philip
It's probably my fault. The line before Part 1 should read:
2. Assume N = 1 (mod 10 2k ) (not 2 )
The formatting stuff all got a bit confusing....... Sorry (Thank you Angelina for also pointing this out)
For k = 3
From the induction assumption N = .......000001 (i)
Considering N (mod 28 ) it must be 0, 1, 4, 9, ..........225 (mod 256)
Note this is just an extension of the idea that a square number is always 1 or 0 (mod 4), which is where the idea came from
Of all of these numbers it has to be 1 because all of the others are less than 1000000 and if it were any of them then (i) wouldn't be true. So N = 1 (mod 256). (Which is all we wanted to show).
| Posted on Saturday, 28 December, 2002 - 06:58 am: |
Nice proof Tom .. (though i must admit that it took me a bit of time to get my heads around the last part,i had to largely verify it through examples)
However,i have been looking at alternatives.
we know that,
if M2 =N,then M=10k+1 or 10k+9
now,(10k+1)2 = 100k2 +20k+1 & (10k+9)2 =100k2 +180k+81
we can come up with logical deductions to show that (10k+1)2 & (10k+9)2 cannot be a sequence of 1's and 0's.However my concerns are whether that would be a concrete enough proof.
love arun
| Posted on Saturday, 28 December, 2002 - 10:09 am: |
Tom, Could you clarify a thing for me regarding your proof and that is how did you get to the 4 possibilities in part 2. (I think I know the answer to it, but I would like to hear your explanation)
Arun,
I would love to hear more.
Yatir
| Posted on Saturday, 28 December, 2002 - 01:52 pm: |
Arun, I also tried that method for M=10k+1 and came to a quite nice contradiction.
If N=100k2 +20k+1 this will end in 01
So we can take away one and divide by 10 with no problems, leaving
2k(5k+1) this is even so must end in a 0
We can therefore divide by 10 using k=10p leaving
2p(50p+1) which must also end in a 0
We can now continuely divide by 10 showing the preceding figure cannot be a 1. therefore showing N is equal to 1
QED
I haven't worked through M=10k+9 as Tom gave his great proof by then.
By the way what does QED stand for, all i know is its used to show the end of a proof.
| Posted on Saturday, 28 December, 2002 - 02:29 pm: |
Anuj, that's basically how I approached it too :) but likewise didn't do it for (10k+9)... QED stands for ''quod erat demonstrandum'' (it's Latin) and means something along the lines of ''that which was to be demonstrated'' I've heard a sort of math 'legend' that the first person to use it chose it because it looked very similar to O ED which is found in Euclid's Elements (it's greek and stands for Oper Edei Deixe which basically means something very similar to QED) Marcos
| Posted on Saturday, 28 December, 2002 - 03:44 pm: |
Arun, your method is what I have tried right at the first place. Anuj, I got what you had for M=10k+1.
For M=10k+9, all I tried to prove was that N=M2 cant end in 01 (since the case 11 has been proven that cant happen).
Now N = (10k+9)2 = 100k2 +180k+81 which must end it 01
=> N1 = N-1 = 100k2 +180k+80 must be divisible by 100
=> 10k2 +18k+8 = 2(5k2 +9k+4) mod 10 = 0
=> P = (5k2 +9k+4) mod 5 = 0
However, if k is odd then P is even, and if k is even then P is still even, i.e. P mod 5 cant be 0. QED
In fact, (thanks to Tom who put it together and I hope you dont mind I put it up for you) this method can work for both cases where M = 10k+1 or 10k+9 however it ends. It's slightly messy but you can have a go yourself
Angelina
| Posted on Saturday, 28 December, 2002 - 04:40 pm: |
Oops, think i made a mistake in my proof above - what i meant to say is not that just p(mod5)=0 (well, to just prove that N1 (mod 100)= 0, yes...) but to get only sequences of 1s and 0s P can only end with 5, which then my final line of that proof works (i think).
Correct me if I'm wrong please, ppl!
| Posted on Saturday, 28 December, 2002 - 04:47 pm: |
Doh! Still wrong!
| Posted on Saturday, 28 December, 2002 - 06:32 pm: |
Well,it seems Anuj and Angelina have got their best foot forward here!(Applauds!!)
As for the problem,i ran a thought process to make my deductions.
if M=10k+1,N=100k2 +20k+1
if the last two digits of N are to be 01,then k must be a multiple of 5.(guess how??)
if k=5,15,25,35,....
then the term 100k2 assures that atleast one of the digits of N is neither 1 nor 0.
if k=10,20,30,40,....
then the term 20k assures that atleast one of the digits of N is neither 1 nor 0.
if M=10k+9,N=100k2 +180k+81
if the last two digits of N are to be 01,then k=10p+4 or 10p+9.(guess how??)
if k=10p+4,
then the term 100k2 assures that atleast one of the digits of N is neither 1 nor 0.
if k=10p+9,
here we get two cases ....
case 1-> k2 is a sequence of 1's and 0's by our original assumption.
case 2-> k2 is not a sequence of 1's and 0's
for case 2,the term 100k2 assures that atleast one of the digits of N is neither 1 nor 0.
for case 1,the term 180k assures that atleast one of the digits of N is neither 1 nor 0.(This is odd isn't it??an assumed statement being used to disprove the same)
love arun
P.S-> i am not sure who would buy this for a good proof
| Posted on Saturday, 28 December, 2002 - 09:02 pm: |
I didn't have time (yet!) to go over all your proofs. Anuj, in your fourth line, k could also be =5p...
Yatir
| Posted on Saturday, 28 December, 2002 - 09:05 pm: |
Something about the last stage of the 10m+9 part makes me a bit uncomfortable.
How can you justify assuming that because k2 is not a sequence of 1s and 0s that N won't be? It could begin with a sequence of 1s and 0s and then have other bits which will 'interact' with the later terms. Just because the parts don't have just 1s and 0s doesn't mean the total won't eg. 9999998+3=10000001. Also how can you be sure earlier on that the same thing doesn't happen with the different terms affecting each other.
I think it would probably not take much to clear up this little point, but until it is cleared up I find myself unwilling to accept some of the assumptions you have made which are probably obvious to you but not to some of us who take a little longer to catch onto these sorts of things.
Apart from that the proof looks good.
| Posted on Saturday, 28 December, 2002 - 11:30 pm: |
Good point Yatir,
If k=5p
p(25p+1) ends in 0 or 1
Both p and 25p+1 cannot be odd therefore it will end in a 0. So using p=10q
q(250q+1) ends in 1 or 0
aqain both cannot be odd so it must end in 0.
This process can be kept going until once again we find N must be equal to 1.
QED
| Posted on Sunday, 29 December, 2002 - 10:03 am: |
Tom,
i have not assumed anything except for one thing that there exists an M such that M2 =N.
"k2 is not a sequence of 1s and 0s that N won't be?"
well i have not assumed this.Infact,i have proved that even if k2 is a sequence of 1's and 0's,N is not a sequence of 1's and 0's (which recursively proves that k2 cannot be a sequence of 1's and 0's and thus eliminating that case in its entirety.)
As for my conclusion as to how there would be atleast one digit in N which is neither 1 nor 0,well just look at N.
N=100k2 +20k+1 or N=100k2 +180k+81
both these expressions assure us that the last digit would be 1.Now i attained my conditions of k by seeing to it that the second last digit is a zero.
For N=100k2 +20k+1,k=multiple of 5
For N=100k2 +180k+81,k=10p+4 and k=10p+9
Now,one thing you have to note is that 100k2 does not play a role in determining the last two digits of N.That means,if and only if,100k2 is a sequence of 1's then N would be a sequence of 1's.
now,if 100k2 is a sequence of 1's and 0's,then the middle terms(namely 20k and 180k) assures that there will be some terms which are neither 1 nor 0.
love arun
P.S-> i don't know .. how far i have made myself clear!!if any further doubts,then feel free to write back.(of course,i don't claim that my proof is perfect or for that matter even i doubt it to be called a proof,so all the criticisms are warmly welcomed)
| Posted on Sunday, 29 December, 2002 - 02:58 pm: |
Oops i made a mistake above
q(250q+1) can be odd, with any odd numbered q.
Oh well this is a lot harder than it thought it would be.
| Posted on Saturday, 11 January, 2003 - 09:34 am: |
Tom gave a proof that there are none.
I managed to prove his last part by the theory of linear equations.
But I have a problem with part I. This part relies on the fact that if n=1 (mod 102k ) then n=1 (mod 22(k+1) ) because 102k > 22(k+1) this seemed a reasonible argument at first but then I gave it some more thought and wouldn't this be true only if n < 102k (which it isn't neccessarly true...
Comments?
Thanks,
Yatir
| Posted on Saturday, 11 January, 2003 - 05:02 pm: |
i think you got confused because of the statement "Assume N=1(mod 22k )..." . This statement should actually been "Assume N=1(mod 102k )....."(Infact i think someone noticed that and pointed it out!!)
love arun
| Posted on Saturday, 11 January, 2003 - 06:37 pm: |
No, I didn't.
Here is an example:
if n=1 (mod 10) then n is isn't neccesseraly congruent to 1 modulo 8....
Or any two example where one modulo is bigger than the other...
Yatir
| Posted on Sunday, 12 January, 2003 - 04:41 am: |
102k not equal to 10 (given that k is an integer)
love arun
| Posted on Sunday, 12 January, 2003 - 06:43 am: |
I know.
All I wanted to say is that if n=1 (mod d) and d> c then n isn't neccessarly congruent to 1 modulo c.
I think that Tom proved part I using the fact that what I said above is always true...Maybe I misunderstood is proof for Part I...
| Posted on Sunday, 12 January, 2003 - 06:35 pm: |
Yatir,
err..he actually says,
if n=1(mod a) and n = b(mod c),then if a> b then n=1(mod c).
This statement again is not true but given the nature of the N,a,b,c in the problem ... i think it is true (intuitively!!)
i must say that i got confused myself over this statement and spent a lot of time trying to prove it but every effort was in vain.
love arun
P.S-> It took me two whole days to understand that proof and i must say that my understanding was totally intuitional because some of the statements made in the proof seemed very surprising to me.
| Posted on Sunday, 12 January, 2003 - 06:39 pm: |
Arun, that is exactly what I am saying. I didn't even try to prove it because intuitively it seemed correct to me. But it isn't true. Just test some numbers to realize this.
I wish Tom could enter this discussion...
Yatir
| Posted on Sunday, 12 January, 2003 - 06:52 pm: |
Yatir,
i have verified it through examples.Hence i am in a dilemma.
Consider,
492 =1(mod 102 ) ... (k=1)
therefore,(2k+1 -1)2 = 9
and 22(k+1) = 16 = 24
hence,
492 = 1 or 4 or 9 (mod 24 )
out of these,the answer is
492 = 1 (mod 24 )
hence his statement is true.
love arun
| Posted on Sunday, 12 January, 2003 - 07:01 pm: |
I agree with you 100%, this is true whenever n < a
(and quite easily proven)
Check cases when n is bigger than a....
Yatir
| Posted on Sunday, 12 January, 2003 - 07:11 pm: |
hmm,
you are right here.
1492 = 1 (mod 102 )
1492 = 9 (mod 24 )
and as such the proof does come to a standstill here.
love arun
| Posted on Sunday, 12 January, 2003 - 07:14 pm: |
Still i must say that this statement is something very new to me and i am very much amazed by it.
Statement : if N=1 (mod 102k ) then
N=1 or 4 or .... or (2k+1 -1)2 (mod 22(k+1) )
love arun
| Posted on Sunday, 12 January, 2003 - 07:23 pm: |
Why is this new to you?
I remember you dealing with similar stuff before...
Yatir
| Posted on Sunday, 12 January, 2003 - 09:23 pm: |
me?? i did this??
whoa!! i am having serious memory lapses here.I think its bcos i had bad run of exams recently(which completes on 14th).After 14th i think i will be my normal self again.
love arun
| Posted on Monday, 13 January, 2003 - 10:22 am: |
Yeah!. Sure...Why not?
| Posted on Monday, 13 January, 2003 - 10:52 am: |
Arun, My world has now been shattered.
Even, your statement isn't true!
If N is a square number, it doesn't have to be congruent to a square residue.
Example:
(working modulo 28 )
(24 +1)2 =33
I think this is another problem with the proof...
| Posted on Monday, 13 January, 2003 - 11:30 am: |
Yatir,
i am unable to understand that.
BTW which statement are you talking about?
Are you talking about this statement?
Statement :if N=1 (mod 102k ) then
N=1 or 4 or .... or (2k+1 -1)2 (mod 22(k+1) )
If yes,then actually i find it true for nearly all cases where N=1(mod 102k ).However,i specifically don't understand the counter-example you have provided.Could you clarify on that a bit?
love arun
| Posted on Monday, 13 January, 2003 - 12:44 pm: |
Sorry. You're right, I didn't express myself right.
Here is a proper counter-example
Let N=25010001 (it is a square-number!)
We know that N=1 (mod 104 )
BUT N=17 (mod 26 )!
Yatir
| Posted on Monday, 13 January, 2003 - 04:54 pm: |
Yeap!! you are right again here !!!
Now the proof is in jeopardy,unless some rationalistic comments are added to it.
Well i am still trying to make the "thought process" i suggested in that link into a rigorous proof but so far that has eluded me entirely.So maybe we still are stuck on the question.
love arun
| Posted on Monday, 13 January, 2003 - 06:09 pm: |
There is nothing better than an unsolved problem!
| Posted on Tuesday, 14 January, 2003 - 09:57 pm: |
Sorry for not realising this conversation existed earlier.
You have to admit the proof was good while it lasted (!).
I will look at what you have said and try and work out how I went so wrong.
| Posted on Tuesday, 14 January, 2003 - 11:01 pm: |
Yes it was!
Just to let you know, I had a conversation in a hebrew forum about your proof (with the one who gave me the question) and I defended each line of it until finally I had to admit that there was a flaw!
Yatir
| Posted on Wednesday, 15 January, 2003 - 10:38 pm: |
If it is any consolation I think I can prove it in a different way. I know its sort of already been done in the conversation, but here it is anyway. I haven't put it in the right format so it might be difficult to read. I think it is more likely to be right as I tried to keep it less jumpy.
Any N written using 1s and 0s can be expressed as:
N = 10^a(10^b1 + 10^b2 +10^b3 +......etc..... +1)
Note that b2 is not b1+1. Ie the above just represents 1s dotted in random places in a sea of 0s
As already discussed in this case a is even as there are an even number of 0s on the end.
As in previous proofs I will ignore the 0s on the end and show that there is no N', where N' is a perfect square written with 1s and 0s.
Using the above notation N' = 10^b1 +10^b2 + ......... +1
As also already shown if N' = n^2, n must be of the form 10k +1 or 10k +9. We will consider these 2 cases separately.
n of form 10 k +1:
(10k +1)^2 = 10k(10k+2) +1 = 10^b1 +10^b2 + ......... +1
So 10k(10k+2) = 10^b1 +10^b2 + ......... + 10^bt
The right hand side must have at least a factor of 10 as the LHS divides by 10. We can factorise the RHS taking out a the largest factor of 10 possible (this is 10^bt).
10k(10k+2) = 10^bt (10^(b1 - bt) + 10 ^(b2 -bt) + ...... +1) (i)
Now (10k + 2) can never divide by 10 so 10k must divide by 10^bt => 10k=10^bt*q
k=10^(bt-1)*q
Substituting in and cancelling the 10^bt from each side:
q(10^bt*q +2) = 10^(b1 -bt) + 10 ^(b2 -bt) + ...... +1
LHS odd, RHS even, contradiction reached
n of form 10 k +9
Following the same procedure as before and skipping to the equivalent of (i)
10(10k^2 + 18k + 8) = 10(10k+8)(k+1) = 10^bt (10^(b1 -bt) + 10 ^(b2 -bt) + ...... +1)
So, as (10k +8) will never divide by 10: 10(k+1) = 10^bt => (k+1) = 10^(bt-1)q (ii)
Then cancelling and substituting in
(10k+8) = (10^(b1 -bt) + 10 ^(b2 -bt) + ...... +1) (iii)
LHS even, RHS odd.
The second part is very interesting. It is worth looking at what 99^2, 999^2 etc are generalising the general pattern and then looking again at lines (ii) and (iii) and seeing how this result ties in.
| Posted on Thursday, 16 January, 2003 - 06:37 am: |
Tom,
n has to be in the form of 10k+1 or 10k+9, not 10k+2....
What you've proved is that n =/= 10k+9.
Yatir
| Posted on Thursday, 16 January, 2003 - 07:26 pm: |
(10k + 1)2 = 100k2 + 20k + 1
= 10k(10k+2) + 1
Then take one from both sides and factor out the remaining highest power of 10.
I think I have proved both parts.
| Posted on Friday, 17 January, 2003 - 07:09 pm: |
"Now (10k + 2) can never divide by 10 so 10k must divide by 10^bt => 10k=10^bt*q
k=10^(bt-1)*q "
10k=25*4
10 doesn't divide 25 and it doesn't divide 4, but it does divide 25*4.
There is a lemma called: Euclid's Lemma:
if a|bc and gcd(a,b)=1 then a|c
| Posted on Sunday, 19 January, 2003 - 01:36 pm: |
I checked into it more. the last 3 digits of our number must be '001', but you can't argue about the other digits...