Base 8 Logic Puzzle: Finding Solutions to Divisibility Rules

[PhotonSSBM]

Homework Statement

We call a seven digit number in base eight X, whose digits are given by

$abcdefg$

No digits are zero, and none of them are the same. The following divisibility rules are true:

(I)The number $ab$ is divisible by 2
(II) The number $abc$ is divisible by 3
(III)The number $abcd$ is divisible by 4
(IV)The number $abcde$ is divisible by 5
(V)The number $abcdef$ is divisible by 6
(VI)X is divisible by 7

Find all solutions that satisfy these constraints. No credit will be given to brute force or computational solutions.

Hint: Start from proposition one and carefully reason your way through the digits.

Homework Equations

Divisibility of a number in base n by n-1 requires that the sum of the digits also be divisible by n-1

There's probably some other rules I'm not privy to, and google hasn't produced.

The Attempt at a Solution

So I started from the beginning saying that a solution to $ab$ is just an even number with no zero or repeats. So:

a can be (1,2,3,4,5,6,7) and b has to be (2,4,6)

Similarly:

c, e, and g can also be (1,2,3,4,5,6,7) as long as there are no repeats

and

f has to be an even number as well so f is (2,4,6)

and

d has to be 4, similarly to how being divisible by 5 in base 10 means it ends in 5 or 0

and

This means a, c, e, and g can only be (1,3,5,7)

Also, the order of what a, c, e, and g, as well as b, and f are is irrelevant to proposition 6, since any order will be divisible by 7.

I cannot figure out how to reduce this any further.

 

[lewando]

[deleted].

 

[PhotonSSBM]

Bump, no takers?

 

[lewando]

Perhaps it is time to do some numerical work. For abc you will have less than 32 possibilities. How many of those are divisible by 3? Etc.

 

[SammyS]

Homework Statement

We call a seven digit number in base eight X, whose digits are given by

$abcdefg$

No digits are zero, and none of them are the same. The following divisibility rules are true:

(I)The number $ab$ is divisible by 2
(II) The number $abc$ is divisible by 3
(III)The number $abcd$ is divisible by 4
(IV)The number $abcde$ is divisible by 5
(V)The number $abcdef$ is divisible by 6
(VI)X is divisible by 7

Find all solutions that satisfy these constraints. No credit will be given to brute force or computational solutions.

Hint: Start from proposition one and carefully reason your way through the digits.

Homework Equations

Divisibility of a number in base n by n-1 requires that the sum of the digits also be divisible by n-1

There's probably some other rules I'm not privy to, and google hasn't produced.
...

Actually, you are privy to some other divisibility tests. That's how you determined that b, d, and f are each even, and also deduced that f = 4.

Unfortunately, the divisibility test for (n - 1) in base n representation isn't of any help, since in this case (n - 1) = 7 which is prime. (In decimal representation (base ten), the divisibility test for 9 also gives the divisibility test for 3, because 3 divides 9.)

In base ten, there is a divisibility test for 11. There is a similar divisibility test for nine in base eight. Nine is written as 11_[eight] . In base eight, this same test works for divisibility by 3.

Do you know in general the basis for divisibility tests?

 

[PhotonSSBM]

Do you know in general the basis for divisibility tests?

I do not outside of the n-1 rule you mentioned. I know that you can derive the other divisibility rules from that one, but that's about it.

 

[SammyS]

I do not outside of the n-1 rule you mentioned. I know that you can derive the other divisibility rules from that one, but that's about it.

Use modular arithmetic. You can get pretty complicated, for a number with an arbitrary number of digits with an arbitrary base, or in this case, you can be somewhat more specific.

Example:
The number written abc in octal is equal to a×8² + b×8 +c .
You have abc is divisible by three, so that

a×8² + b×8 +c ≡ 0 mod 3​

8 ≡ 2 ≡ -1 mod 3
8² ≡ 1 mod 3
Therefore, in general, a×8² + b×8 +c ≡ (a -b + c) mod 3 .
But specifically, since abc is divisible by 3, and b = 2 or 6:

a + c - 2 = 3 m, some multiple of 3​

or

a + c - 6 = 3 m', also some multiple of 3​

It turns out that you divisibility

Similarly (V) says the 6 divides abcdef, but as you observed this means that 2 and 3 each divide abcdef.
You already have that divisibility by 2 gives f = 2 or 6.
For divisibility by 3, we can extend what we did above. 8 ≡ -1 mod 3, so 8² ≡ (-1)² = 1 mod 3, etc. Similar to taking -1 to whole number powers. 8^odd ≡ -1 mod 3 and 8^even ≡ 1 mod 3.

Use that along with the fact that you know the sum, b + d + f = 12

If 6 | abcdef, then abcdef ≡ a(-1) + b(1) + c(-1) + d(1) +e(-1) +f mod 3.

This leads to b + d + f - (a + c + e) = 3n for some integer n.

Rearranging gives a + c + e = 3n' , a different integer.

That might not look all that helpful, but a, c, e, and g is each a different odd integer, their sum is 16. Only two of the four possible sums of three are divisible by 3. Therefore, you know a, c, and e must come from {1,3,5} or from {3,5,7) .

Division of abcde by 5 is the complicated one.

8 ≡ 3 ≡ -2 mod 5
8² ≡ 3² ≡ -1 mod 5
8³ ≡3³ ≡ 2 mod 5
8⁴ ≡(-1)² ≡ 1 mod 5​

You know that d = 4 and b = either 2 or 6. These are the only two digits multiplied by 2 or -2. That's helpful.

Narrow the possibilities down, then include the division of abc by 3 .I get that there are 3 such seven digit base eight numbers.
.

 

[SammyS]

@PhotonSSBM ,

Have you found any solutions to this?

 

[PhotonSSBM]

Yes! They're turned in though. I can post them when I get the assignment back.

Edit: too busy to reproduce them now.

 

[SammyS]

Yes! They're turned in though. I can post them when I get the assignment back.

Edit: too busy to reproduce them now.

Looking forward to that.

I won't post anything more on details until we see a post with your results. However, I do have some comments I'll make now.

If I were to give this exercise, I would be inclined to use slightly different numbering for the divisibility requirements. I would have:

i) The octal number $\ a\$ is divisible by 1 .
ii) The octal number $\ ab\$ is divisible by 2 .
iii) The octal number $\ abc\$ is divisible by 3 .

etc .​

vi) The octal number $\ abcdef\$ is divisible by 6 .
vii) The octal number $\ abcdefg\$ is divisible by 7 .​

This simply gives a short-cut way to state the requirements. " The base eight number formed using the first n digits is divisible by n. " This has no significance in regard to obtaining a solution.

Requirement i) is obviously true no mater which digit is used for $\ a\ .$
Requirement vii) is true because the seven digits are all different and 1+ 6 = 2 + 5 = 3 + 4 = 7, so that 1+ 2+ 3+ 4+ 5+ 6+ 7 is a multiple of 7 .

Those two divisibility requirements are no help whatsoever in solving the problem