WAIT!

arbMul doesn't even have to be a multiple does it? How about arbNum2 instead? (arbNum2 > arbNum * 2)

(I think multiples just increase the frequency)

Quote: Original post by anothrguitarist
EDIT: Hmm, I think the set in your example is supposed to contain {80/1, 80/2, 80/4, 80/5} = {80, 40, 20, 16}

Then:
90 % 80 = 10
90 % 40 = 10
90 % 20 = 10
90 % 16 = 10

Right.

Let's reformule the problem a bit.

1. Let a be a positive integer.
2. Let b be a positive integer greater or equal to 2.
3. Let x = ab - a.
4. Let S = {x/n : n is a positive integer}
5. For every q in S such that q is an integer, we claim that ab = a (mod q).

(See 'a' as 'arbNum' and the product 'ab' as 'arbMul', then 'x' is 'resultNaught' and so on).

Proof of the claim :

Let q be in S such that q is an integer. Let n be the integer such that q = x/n. So qn = x. But x = ab - a. So, qn = ab - a. Then, taking modulo q on both sides gives (ab - a) = 0 (mod q). This implies that ab = a (mod q).

Note that this problem is a bit different from yours, because ab = a (mod q) is not exactly the same as ab % q = a. In the former, "ab = a (mod q)" means that both sides of the equation are reduced modulo q. Whereas in "ab % q = a", only the left hand side is reduced modulo q.

To prove your original claim, it works to add the restriction on the set S that "x/n > a", that is S = {x/n : n is a positive integer and x/n > a}. Then q is always greater than a, so a % q = a, and the proof is complete.

Quote: Original post by anothrguitarist
WAIT!

arbMul doesn't even have to be a multiple does it? How about arbNum2 instead? (arbNum2 > arbNum * 2)

(I think multiples just increase the frequency)

Let's try this problem then:

1. Let a be a positive integer.
2. Let b be a positive integer.
3. Let x = b - a.
4. Let S = {x/n : n is a positive integer}
5. For every q in S such that q is an integer, we claim that b = a (mod q).

Proof of the claim:

Let q be in S such that q is an integer and let n be the integer such that q = x/n. Then qn = x. But x = b - a, so qn = b - a. Taking modulo q on both sides, we have b - a = 0 (mod q), so b = a (mod q).

So, you don't even need to assume anything about b. Of course the problem is really trivial when you think about it. We start with a = b + x, so if we reduce that expression modulo any divisor of x, of course x dissapears.

Quote: Original post by Hedos

Quote: Original post by anothrguitarist
EDIT: Hmm, I think the set in your example is supposed to contain {80/1, 80/2, 80/4, 80/5} = {80, 40, 20, 16}

Then:
90 % 80 = 10
90 % 40 = 10
90 % 20 = 10
90 % 16 = 10

Right.

Let's reformule the problem a bit.

1. Let a be a positive integer.
2. Let b be a positive integer greater or equal to 2.
3. Let x = ab - a.
4. Let S = {x/n : n is a positive integer}
5. For every q in S such that q is an integer, we claim that ab = a (mod q).

(See 'a' as 'arbNum' and the product 'ab' as 'arbMul', then 'x' is 'resultNaught' and so on).

Proof of the claim :

Let q be in S such that q is an integer. Let n be the integer such that q = x/n. So qn = x. But x = ab - a. So, qn = ab - a. Then, taking modulo q on both sides gives (ab - a) = 0 (mod q). This implies that ab = a (mod q).

Note that this problem is a bit different from yours, because ab = a (mod q) is not exactly the same as ab % q = a. In the former, "ab = a (mod q)" means that both sides of the equation are reduced modulo q. Whereas in "ab % q = a", only the left hand side is reduced modulo q.

To prove your original claim, it works to add the restriction on the set S that "x/n > a", that is S = {x/n : n is a positive integer and x/n > a}. Then q is always greater than a, so a % q = a, and the proof is complete.

Nice work rewriting it, Hedos. It's a lot easier to read this way.