Show that for every integeranot divisible by 11 there is another integerbwith

a*b == 1 (mod 11).

This problem has me stumped...

Printable View

- Sep 22nd 2010, 01:46 PMpaulrbExistence proof
Show that for every integer

*a*not divisible by 11 there is another integer*b*with

a*b == 1 (mod 11).

This problem has me stumped... - Sep 22nd 2010, 01:55 PMundefined
- Sep 22nd 2010, 02:29 PMpaulrb
Thanks...I should have specified though, I've only been in this number theory class for 3 weeks and we have only covered basic theorems about congruence / number theory. Nothing with fermat's little theorem / euler's theorem so I don't think it would be acceptable for me to use that in a proof.

- Sep 22nd 2010, 03:05 PMundefined
I think we can do as follows. It will be a stronger result than what you need to prove.

Let p be any prime, and let a be an integer not divisible by p.

Consider the set . Claim: each element of S is distinct modulo p.

Proof: Suppose the opposite. Then there exist integers x, y such that and . The latter implies . So we have a product of two non-multiples of p being divisible by p; contradiction.

Now consider that there are p distinct equivalence classes in S modulo p, thus it is the set of all equivalence classes modulo p, and . - Sep 22nd 2010, 03:44 PMpaulrb
That's a great proof, thank you!

- Sep 23rd 2010, 10:12 AMroninpro
I'd just like to point out that a more standard approach would be to use Bezout's identity.

If 11 does not divide , then . By Bezout's identity, there exist integers such that . Taking everything modulo 11, , and . The term is what we are looking for. - Sep 23rd 2010, 10:18 AMundefined