A question that should use pigeon hole principle.

[MathematicalPhysicist]

the question is as follows:
gcd(n,10)=1, i need to prove that there exists a k>=1 such that 10^k-1 is divisible by n.

now i thought to look at the set of the remainders of division by 10, i got from what is given that this set is {1,3,9,7} cause n and 10 don't have other common factors besides one. now i thought to look first at n=7, and I am not sure there exists an appropiate k such that 10^k-1 is divisble by 7.

i think that this question the way it's satated isn't valid am i correct or wrong here?

 

[NeoDevin]

So, if you choose k = \log_{10}(mn+1) where m is an integer, then 10^k -1 is divisible by n right?

If, however, you wanted to prove that 10^{k-1} is divisible by n you should take k = \log_{10}(mn) + 1.

 

[matt grime]

I don't see why logs would help, or the pigeon hole principle.

It is far easier than that. 10 is a unit in Z_n, i.e. in (Z_n)^*, which is a finite group under multiplication. So all it is asking is 'show an element in a finite group has finite order'.

 

[MathematicalPhysicist]

no groups should be used in this question, haven't yet taken a course in groups.
anyway you didn't replied to me to the other question, which k makes 10^k-1|7, i don't seem to find one.

and if it is correct then how to prove it without using groups?

 

[MathematicalPhysicist]

So, if you choose k = \log_{10}(mn+1) where m is an integer, then 10^k -1 is divisible by n right?

If, however, you wanted to prove that 10^{k-1} is divisible by n you should take k = \log_{10}(mn) + 1.

to clear it out i mean: (10^k)-1 divisible by n.

 

[shmoe]

anyway you didn't replied to me to the other question, which k makes 10^k-1|7, i don't seem to find one.

There isn't one, but that's irrelevant to this question...

to clear it out i mean: (10^k)-1 divisible by n.

you're mixing up what is supposed to divide what.

the log thing won't help, you should be able to say why.

You may already have the notion of order that matt is talking about without ever looking at groups. Elementary number theory courses do contain (special cases of) group theory even if they don't explicitly mention it, have you seen any notion of "order" yet?

Finally, you can do it without the idea of order using the pigeon hole principle. I'll leave it to you to figure out how now that you're going to try to make 10^k-1 divisible by n and not the other way around.

 

[MathematicalPhysicist]

why is this irrelavent to this question, if n=7 and gcd(10,7)=1, then i need to show that there exists such a k>=1 such that (10^k)-1 divisible by 7.

this question is from a course in combinatorics, this is why i need to use the pigeon hole principle.

perhaps i wrote it the other way around, so it should be 7|(10^k)-1.

 

[shmoe]

why is this irrelavent to this question, if n=7 and gcd(10,7)=1, then i need to show that there exists such a k>=1 such that (10^k)-1 divisible by 7.

this question is from a course in combinatorics, this is why i need to use the pigeon hole principle.

perhaps i wrote it the other way around, so it should be 7|(10^k)-1.

You wrote it the other way around. You can't have looked very far if you haven't been able to find a k where 7 divides (10^k)-1, what values of k did you try?

 

[MathematicalPhysicist]

anyway, if (10,n)=1, (10^k)-1=(10-1)(1+10+...+10^(k-1))
n isn't divisble by 2 nor 5, so 10b+na=1 for a,b in Z, we get that, 10b-1 is divisble by n now i need to show that there exists k>=1 such that b=10^(k-1). now, n=10c+d such that d is smaller than 10. now d cannot be:
one of the next {0,2,4,6,8,5} it can only be: {+-1,+-3,+-7,+-9},
now i don't see how to proceed from here.

 

[MathematicalPhysicist]

ok, my mistake i found a suitable k, anyway, back to the original question.

 

[shmoe]

anyway, if (10,n)=1, (10^k)-1=(10-1)(1+10+...+10^(k-1))
n isn't divisble by 2 nor 5, so 10b+na=1 for a,b in Z, we get that, 10b-1 is divisble by n now i need to show that there exists k>=1 such that b=10^(k-1).

How you've picked your b, such a k may not exist.

You seem hung up on looking at n mod 10. You want to find a k where 10^k=1 mod n, this should strongly suggest looking at powers of 10 mod n.

 

[MathematicalPhysicist]

now if (10,n)=1 then 10 mod n, for n<10 we have either {1,3,7,9}...
really don't know what to do next... )-:

 

[matt grime]

Even if you've not done groups, you should surely realize that the remainders

10^k mod n for k=1,2,3,4,...

is a periodic sequence (a trivial application of the pigeon hole principle, in fact - there are infinitely many pigeons and only 5 holes - the 5th, so the 6th remainder must have been seen before ). That is a BIG hint.

 

[LukeD]

wow... I just did this proof yesterday and I already forget it...
I remember how Fermat's Little Theorem works... but not this one

Edit: Nevermind, the proof is pretty much exactly the same.

 

[MathematicalPhysicist]

well, here's what I've done so far:
let m1 be the remainder of 10 mod n, i.e, m1=10 mod n, 10m1=100 mod n,...,10^(k-1)m1=10^k mod n, m2=10^(k+1)mod n,...,10^(k-1)m2=10^(2k) mod n, etc.
we have m1,m2=10m1,m3=100m1, and so on so we have a sequence of:
m1,...,(10^(k-1))m1,10m1,...,10^km1,100m1,...,10^(k+1)m1,...
now I am kind of stuck, matt you say we have a periodic sequence which as you can see iv'e showed it, and i know that m_{j+1}=m_{j+k} for j=1,...,k, now there exist s and r which are different indexes then by the pigeon hole principle we have that m_s=m_r, which means that m_r=10^(k+r-1)mod n and m_s=10^(k+s-1) mod n suppose r>s, then we have:
10^(k+s-1)-m_s=nq and 10^(k+r-1)-m_r=np so: 10^(k-1)(10^r-10^s)=n(p-q) r=s+t for some t>=1, so we get that 10^(k-1)*10^s(10^t-1) which is divisible by n, by (10,n)=1 so we must have that 10^t-1 divisible by n, correct?

well it is as you said a standrad pigeon hole principle, foolish me... (-:

thanks.

 

[MathematicalPhysicist]

a follow up question, i need to prove that:
1. by using the previous question, prove that if (n,10)=1 then 1/n has a periodic decimal expansion. (i did it).
2. show that a number is rational iff its decimal expansion is periodic from some point onwards.

basically for 2, if r=p/q and (p,q)=1 so if (10,q)=1, we get that from 1, that 1/q has a periodic deicmal expansion, and if (10,q) is different than 1, then we have that 1/q=1/(2^r*5^s)*1/t where (t,10)=1 and r and s are postiive integers, now the question is back in the firs place that 1/t is periodic, is this a valid proof for the first part of the statement.
for the second part,i could use some help, ofcourse if I am wrong in the first if, then i can use your help also there.

thanks in advance.