Can a Sequence of 1's and 0's Be a Multiple of Any Integer?

In summary: ,99,98,97,96,95,94,93,92,91,...,90,89,88,87,86,85,84,83,...,82,81,80,79,78,77,76,75,74,73,72,71,...,70,69,68,67,66,65,64,63,62,61,60,59,58,57,56,55,54,53,52,51,50,49,48,47,46,45,44,43,42,41,40,39,38,37,36,35,34,33,32,31,30,29,28,27,
  • #1
Kummer
297
0
Show that for any n>1 we can construct a positive integer consisting of only 1's and 0's such that this integer is a multiple of n.
 
Physics news on Phys.org
  • #2
Interesting variation: show that if n is no divisbible by 2 or 5, then there you can choose this multiple to have precisely two 1s and the rest of the digits 0.
 
  • #3
matt grime said:
Interesting variation: show that if n is no divisbible by 2 or 5, then there you can choose this multiple to have precisely two 1s and the rest of the digits 0.

Can you show example answers for, say, n=3 or n=9?

I do wonder how interesting a 'minimal' condition would make this though.
 
  • #4
A Big Hint

Given (n+1) integers show that there exists two whose difference is a divisible by n.
 
  • #5
The problem is fairily easy...

[tex]k=\sum_{i=1}^{n} 10^{i\phi(n)}[/tex]
where [itex]\phi(n)[/itex] is the Euler Totient function.

Is divisible by [itex]n[/itex].

Alternatively, if we take [itex]n^2-n+1[/itex] integers then at least [itex]n[/itex] of them must have the same residue mod [itex]n[/itex], so their sum is equal to zero mod [itex]n[/itex], so if we take the first [itex]n^2-n+1[/itex] powers of 10, some sum will be equal to zero mod n, and that sum will clearly be zeros and ones.
 
  • #6
My special case was: if 10 and n are coprime, let r be the order of 10 in the units mod n, then 10^r-1 is divisble by n.
 
  • #7
matt grime said:
My special case was: if 10 and n are coprime, let r be the order of 10 in the units mod n, then 10^r-1 is divisble by n.

But that's all 9's. Of course, this leads to a marginally more challenging version:

Show that every number has a (non-trivial) multiple which is some number of ones, followed by some number of zeros.
 
  • #8
Duh. Some times I even surprise myself with my idiocy - we need -1 =some power of n. So if n=p is prime, then we need that 10 has even order mod p - for then 1 has two square roots, 1 and -1
 
  • #9
My version is the easiest if you used my hint.

Theorem: If there are (n+1) distinct integers then there exists two who difference is divisible by n.

Proof: Each of these integers leaves a remainder between 0 and n-1 inclusive upon division by n. Since there are n possible remainders and (n+1) integers that means there exist two which have the same remainder by the PigeonHole Principle. So their difference is divisible by n.

Theorem: Given any positive integer n we can find a positive number consisting of only 1's and 0's which is divisible by n.

Proof: Construct the sequence of (n+1) integers:
1,11,111,...,111...1
By the first theorem two of these when subtracted are divisible by n. But when we subtract them we end up with a number consisting of only 1's and 0's. In fact, the 1's and 0's are groupped together which answers the more difficult question stated by NateTG
 
  • #10
Kummer: How about showing that any number not divisible by 2 or 5 has a multiple that is all 1s?
 
  • #11
Kummer, I think you're under the mistake apprehension that we found your question hard...
 
  • #12
matt grime said:
Kummer, I think you're under the mistake apprehension that we found your question hard...

The question is not hard. It is fun and I wanted to show it to you.
 
  • #13
Here's another (but very similar) way of showing it:

consider the sequence 10^m mod n. This is periodic, by the pigeon hole principle. There for there are s,r integers with 10^s=10^{s+kr} mod n for k natural numbers k. Just add up any n different such powers of 10.
 
  • #14
Hmm, I wonder if there's some way to find the minimum such multiple, or the average minimum multiple.
 
  • #15
I should have been more pedantic: the sequence is eventually periodic. It need not be periodic. The idea being that at some point you must have a repeated residue, and then it becomes periodic - if 10 were invertible, then you could guarantee to run it backwards too. Eg. say n=100, the sequence goes 10,0,0,0,0,0,...
 

What is a Fun Divisibility Problem?

A Fun Divisibility Problem is a mathematical puzzle that involves finding a number that is divisible by a specific set of numbers. These types of problems are often used as brain teasers and can vary in difficulty.

How do I solve a Fun Divisibility Problem?

The key to solving a Fun Divisibility Problem is to find a number that is divisible by all the given numbers. This can be done by finding the common factors of the numbers and then finding the smallest number that contains all those factors. Another approach is to use divisibility rules for each number in the set.

What is the importance of Fun Divisibility Problems?

Fun Divisibility Problems help improve mathematical skills such as problem-solving, critical thinking, and pattern recognition. They also help develop patience and perseverance when faced with challenging problems.

Are there any strategies for solving Fun Divisibility Problems?

Yes, there are several strategies that can be used to solve Fun Divisibility Problems. These include prime factorization, divisibility rules, and finding the LCM (least common multiple) of the numbers. It is also helpful to break down the problem into smaller parts and work through them systematically.

Can Fun Divisibility Problems have real-life applications?

While Fun Divisibility Problems may seem like purely abstract mathematical puzzles, they can have real-life applications. For example, they can be used in coding and programming to optimize algorithms or in cryptography to secure data. They can also be used in designing puzzles and games.

Similar threads

  • Linear and Abstract Algebra
2
Replies
39
Views
2K
  • Linear and Abstract Algebra
Replies
33
Views
3K
  • Linear and Abstract Algebra
Replies
8
Views
663
  • Precalculus Mathematics Homework Help
Replies
5
Views
936
  • Calculus and Beyond Homework Help
Replies
5
Views
1K
Replies
3
Views
2K
  • Linear and Abstract Algebra
Replies
8
Views
1K
  • Precalculus Mathematics Homework Help
Replies
3
Views
1K
  • Linear and Abstract Algebra
Replies
11
Views
1K
  • Precalculus Mathematics Homework Help
Replies
5
Views
753
Back
Top