A question that should use pigeon hole principle.

In summary, the question asks to prove that for any n where gcd(n,10)=1, there exists a k>=1 such that 10^k-1 is divisible by n. The set of remainders of division by 10 is {1,3,9,7} for n and 10 where the only common factor is 1. It is suggested to look at powers of 10 mod n, which form a periodic sequence. Using the pigeon hole principle, it can be shown that there must exist a k where 10^k=1 mod n. Therefore, 10^k-1 is divisible by n.
  • #1
MathematicalPhysicist
Gold Member
4,699
371
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?
 
Physics news on Phys.org
  • #2
So, if you choose [itex] k = \log_{10}(mn+1) [/itex] where [itex]m[/itex] is an integer, then [itex] 10^k -1 [/itex] is divisible by [itex]n[/itex] right?

If, however, you wanted to prove that [itex]10^{k-1}[/itex] is divisible by [itex]n[/itex] you should take [itex] k = \log_{10}(mn) + 1[/itex].
 
Last edited:
  • #3
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'.
 
  • #4
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?
 
  • #5
NeoDevin said:
So, if you choose [itex] k = \log_{10}(mn+1) [/itex] where [itex]m[/itex] is an integer, then [itex] 10^k -1 [/itex] is divisible by [itex]n[/itex] right?

If, however, you wanted to prove that [itex]10^{k-1}[/itex] is divisible by [itex]n[/itex] you should take [itex] k = \log_{10}(mn) + 1[/itex].
to clear it out i mean: (10^k)-1 divisible by n.
 
  • #6
loop quantum gravity said:
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...

loop quantum gravity said:
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.
 
  • #7
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.
 
  • #8
loop quantum gravity said:
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?
 
  • #9
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.
 
  • #10
ok, my mistake i found a suitable k, anyway, back to the original question.
 
  • #11
loop quantum gravity said:
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.
 
  • #12
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... )-:
 
  • #13
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.
 
  • #14
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.
 
Last edited:
  • #15
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.
 
  • #16
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.
 

1. What is the pigeon hole principle?

The pigeon hole principle is a mathematical concept that states that if there are more pigeons than pigeon holes, at least one pigeon hole must contain more than one pigeon. It is also known as the Dirichlet principle or the box principle.

2. How is the pigeon hole principle used in mathematics?

The pigeon hole principle is often used in combinatorics, which is the branch of mathematics that studies counting and combinations. It is also used in other areas of mathematics, such as number theory and graph theory.

3. Can you give an example of the pigeon hole principle in action?

One example of the pigeon hole principle is the "birthday problem," which asks how many people need to be in a room for there to be at least a 50% chance that two people have the same birthday. The answer is only 23 people, because there are 365 possible birthdays but more than 23 people will likely result in two people sharing a birthday.

4. What are the applications of the pigeon hole principle?

The pigeon hole principle has many applications in various fields such as computer science, physics, economics, and biology. It can be used to solve problems involving scheduling, data analysis, and optimization.

5. Are there any limitations to the pigeon hole principle?

While the pigeon hole principle is a useful tool in mathematics, it does have its limitations. It can only be applied to finite sets and cannot be used to prove the existence of a solution, only the possibility of one. Additionally, it may not always provide the most efficient solution to a problem.

Similar threads

  • Linear and Abstract Algebra
Replies
8
Views
854
  • Introductory Physics Homework Help
Replies
1
Views
859
  • Programming and Computer Science
Replies
2
Views
839
  • Linear and Abstract Algebra
Replies
3
Views
1K
Replies
9
Views
1K
  • Math Proof Training and Practice
Replies
5
Views
919
  • Introductory Physics Homework Help
Replies
12
Views
684
  • Engineering and Comp Sci Homework Help
Replies
32
Views
3K
Replies
7
Views
758
  • Special and General Relativity
2
Replies
67
Views
2K
Back
Top