Re: Wrong-but-not-incorrect code

From: Richard Harter (cri_at_tiac.net)
Date: 03/21/05 

Date: Mon, 21 Mar 2005 04:43:55 GMT

On Sun, 20 Mar 2005 22:36:50 +0000, Chris Croughton
<chris@keristor.net> wrote:

>On 20 Mar 2005 18:11:55 GMT, Michael Wojcik
> <mwojcik@newsguy.com> wrote:
>
>>
>> In article <423d513a.298652081@news.sbtc.net>, cri@tiac.net (Richard Harter) writes:
>>>
>>> more simply 10a+b=0%7 => 10a-20b%7 => a-2b=0%7
>>
>> Thanks, Richard - that's a lot simpler than my version (though you
>> accidentally left out the "=0" in the second step). Still, I'm happy
>> to have puzzled it out on my own.
>
>I understood yours!
>
>> If anyone doesn't understand the second step, note that -20 is
>> congruent to 1 mod 7. (-20 plus 21 = 1.) That means multiplying by
>> -20 is the same as multiplying by 1, as far as congruence modulo 7
>> goes, so we can freely multiply b by -20. And we choose -20 because
>> it's the closest multiple of 10 that's 1 mod 7, so that we can divide
>> out the common factor 10 and simplify the LHS of the equation.
>
>Ah, thanks, I wondered where the 20 came from. I'm not happy about
>factoring out the 10 in the last step, though, is that valid in modulo
>arithmetic? 14 % 7 == 0, but 1.4 % 7 == 1.4, no?

Good question. In this instance, yes. 10 and 7 are relatively prime,
so 10 has an inverse modulo 7. (The inverse is 5) We can multiply
both sides by the inverse, which is equivalent to dividing both sides
by 10.

For an example where you can't cancel, take

2x = 0 %6

Cancelling gives us x=0, but x=3 is also a valid solution.

1.4 isn't an integer. The rules for modular arithmetic don't all
apply to non integers.
>
>> (Clearly I should have started with the modular algebra and not with
>> drawing up tables of congruences, then working backward from those...)
>
>Doing it multiple ways confirms the correctness...
>
>Chris C

Richard Harter, cri@tiac.net
http://home.tiac.net/~cri, http://www.varinoma.com
All my life I wanted to be someone;
I guess I should have been more specific.

Relevant Pages

  • Help me solve some equations please.
    ... I know that k=b/a but you see I want it in terms of the mentioned variables only (other values should simplify and cancel each other out). ... Please help me solve this problem Using MATLAB. ...
    (comp.soft-sys.matlab)
  • Hadamard inequality and lagrange multipliers
    ... prove the Hadamard inequality using the previous problem: ... ^beta)] ^which can be ... simplify it any further..how can you obtain A? ... everything must cancel out but I am not able to cancel out terms. ...
    (sci.math)
  • Re: Help me solve some equations please.
    ... David Almond wrote: ... (other values should simplify and cancel each other out). ... d and e cannot be permitted to be 0, as you explicitly divide by them. ...
    (comp.soft-sys.matlab)