Existence proof

**paulrb** · September 22nd 2010, 12:46 PM

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...

**undefined** · September 22nd 2010, 12:55 PM

Originally Posted by paulrb

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...

Actually there are infinite. The problem stated another way: show that if $a \not \equiv 0\pmod{11}$ then a has a multiplicative inverse mod 11. It follows immediately from fermat's little theorem / euler's theorem.

**paulrb** · September 22nd 2010, 01:29 PM

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.

**undefined** · September 22nd 2010, 02:05 PM

Originally Posted by paulrb

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.

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 $S=\{0,a,2a,\,\ldots\,,(p-1)a\}$ . Claim: each element of S is distinct modulo p.

Proof: Suppose the opposite. Then there exist integers x, y such that $x\not\equiv y\pmod{p}$ and $ax\equiv ay\pmod{p}$ . The latter implies $a(x-y)\equiv 0\pmod{p}$ . 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 $\overline{1}\in S$ .

**paulrb** · September 22nd 2010, 02:44 PM

That's a great proof, thank you!

**roninpro** · September 23rd 2010, 09:12 AM

I'd just like to point out that a more standard approach would be to use Bezout's identity.

If 11 does not divide $a$ , then $\gcd(a,11)=1$ . By Bezout's identity, there exist integers $x,y$ such that $ax+11y=1$ . Taking everything modulo 11, $ax+11y\equiv 1\pmod{11}$ , and $ax\equiv 1\pmod{11}$ . The term $x$ is what we are looking for.

**undefined** · September 23rd 2010, 09:18 AM

Originally Posted by roninpro

I'd just like to point out that a more standard approach would be to use Bezout's identity.

If 11 does not divide $a$ , then $\gcd(a,11)=1$ . By Bezout's identity, there exist integers $x,y$ such that $ax+11y=1$ . Taking everything modulo 11, $ax+11y\equiv 1\pmod{11}$ , and $ax\equiv 1\pmod{11}$ . The term $x$ is what we are looking for.

Thanks, I wasn't sure if Bezout's identity was available after 3 weeks of intro number theory, I should study standard progression of theorems from axioms.

Thread: Existence proof

LinkBack

Thread Tools

Display

Existence proof

Similar Math Help Forum Discussions

Proof of the existence of a function f such the f(x)=f'(x)

Proof theory: example of an existence proof of a proof?

existence proof, how to start?

proof of existence of z in x < z < y

existence of proof in connection to x^2 = y^2 mod n