Using bijectiveness to prove congruence relation

[MitsuZero]

Homework Statement

$$\forall x\in Z,$$ if x is odd, $$\exists y\in Z,$$ such that $$xy\equiv1(mod 16)$$



The attempt at a solution

I tried to prove this by using the fact that if you got a set of odd integers $$R = {1, 3, 5, ..., 15}$$, and if $$x, y, f(r) \in R$$, then $$xy\equiv f(r)(mod 16)$$. This should directly imply that $$xy\equiv 1(mod 16)$$ (since 1 is an element of R).

I'm just about entirely lost at this point. I would really appreciate any help or guidance on how to proceed.

Thanks.

 

[HallsofIvy]

Homework Statement

$$\forall x\in Z,$$ if x is odd, $$\exists y\in Z,$$ such that $$xy\equiv1(mod 16)$$



The attempt at a solution

I tried to prove this by using the fact that if you got a set of odd integers $$R = {1, 3, 5, ..., 15}$$, and if $$x, y, f(r) \in R$$, then $$xy\equiv f(r)(mod 16)$$. This should directly imply that $$xy\equiv 1(mod 16)$$ (since 1 is an element of R).

I'm just about entirely lost at this point. I would really appreciate any help or guidance on how to proceed.

Thanks.

Yes, that would work but you don't seem to have done anything with it!
You could just work through the different possible values for x:
If x= 1, then obviously y= 1 works. If x= 3 then you are looking for a y such that 3y is congruent to 1 mod 16. 17 is not divisible by 3 but 2(16)+1= 33 is: 3(11)= 1 mod 16. If x= 5, you want 5y= 1 mod 16. 17 is not divisible by 5, 2(16)+ 1= 33 is not divisible by 5, 3(16)+ 1= 49 is not divisible by 5. But 4(16)+1= 65 is: 65/5= 13 so 5(13)= 1 mod 16. That's tedious but it works.

 

[MitsuZero]

Hi Ivy (may I call you Ivy?),
first off I really appreciate your response. It would seem that sometimes we simply require a nudge. I think I understand what your getting at (that eureka moment).

I had actually noticed that bijective "symmetry" your talking about (forgive my diction). Here is what I came up with in that regards:

if
x = 1 , 3, 5, 7, 9, 11, 13, 15
then
y = 1, 11, 13, 7, 9, 3 , 5, 15

So based off these set of numbers (that map back to themselves...linear operator?), I should be able to extrapolate this symmetry to all odd numbers of the integer set Z right?

I guess my problem is the lack of understanding in how to phrase this in proper mathematical language. Here is what I would assume to be the basic outline:
1) Let there exist a set R of the form R={1,3,5...,15}, and a bijective function f that maps all elements of R back to R (I can show bijectiveness for the set R using an arrow diagram).
2) Because this is shown to be true for a finite set {1,3,5,...,15}, then this must be true for all finite sets of the form {1,3,5,...,n} where is any odd integer.
3) Hence for all values (x) or R, there exists another value (y) of R, such that xy=1(mod 16). And so it follows that for all values (x) of the odd integer set, there exists an integer (y) such that xy=1(mod 16).

How's it look so far? I'm beginning to get a cleared understanding of how this proof should be structured, though I'm still a little shaky.

Thanks again for your help.

 

[Dick]

Hi Ivy (may I call you Ivy?),
first off I really appreciate your response. It would seem that sometimes we simply require a nudge. I think I understand what your getting at (that eureka moment).

I had actually noticed that bijective "symmetry" your talking about (forgive my diction). Here is what I came up with in that regards:

if
x = 1 , 3, 5, 7, 9, 11, 13, 15
then
y = 1, 11, 13, 7, 9, 3 , 5, 15

So based off these set of numbers (that map back to themselves...linear operator?), I should be able to extrapolate this symmetry to all odd numbers of the integer set Z right?

I guess my problem is the lack of understanding in how to phrase this in proper mathematical language. Here is what I would assume to be the basic outline:
1) Let there exist a set R of the form R={1,3,5...,15}, and a bijective function f that maps all elements of R back to R (I can show bijectiveness for the set R using an arrow diagram).
2) Because this is shown to be true for a finite set {1,3,5,...,15}, then this must be true for all finite sets of the form {1,3,5,...,n} where is any odd integer.
3) Hence for all values (x) or R, there exists another value (y) of R, such that xy=1(mod 16). And so it follows that for all values (x) of the odd integer set, there exists an integer (y) such that xy=1(mod 16).

How's it look so far? I'm beginning to get a cleared understanding of how this proof should be structured, though I'm still a little shaky.

Thanks again for your help.

Sorry, but you are getting way off the beam. Basically all of that is nonsense. The problem is much more concrete than that. Halls showed a way to find the y corresponding to an x. A 'proof' would show that that can always be done. Unfortunately, that method simply consists of trying all possibilities until you find one that works. I'll give you a big hint. Any odd number x is relatively prime to 16.

 

[rs1n]

Well, I don't think that what he already has is "nonsense." MitsuZero, you have a good start, but you aren't going in quite the correct direction. Your observations about x and y are correct. Here's how to amend what you already have, rather than abandoning it completely (and if I'm not mistaken, it is essentially what Dick is hinting at)

Any positive, odd integer x can be represented as x=16n + r, where n is an appropriate integer r is a number in your set R (this follows from the Euclidean algorithm, the restriction that x is odd, and how you defined the set R). Since we are working modulo 16, it is enough to consider only the case when n = 0, which you already did. Why is this sufficient? For $$r\in R$$, let's presume you know how to find the correct y such that $$ry \equiv 1 \mod 16$$. Now, take any odd integer x and write it in the form 16n+r. Then

$$xy \equiv (16n+r)y \mod 16\equiv 16ny+ r y \mod 16 \equiv 0 + ry \mod 16 \equiv 1\mod 16$$ ***

The complaint from the previous responses is that if the modulus (in this case, 16) were larger, your approach becomes tedious as you would have to consider all value so x that are odd and smaller than the modulus. (For example, imagine if the modulus were, say, 64).

A different approach

Rather than consider every possible case, all that's really need is for you to show that given any such x, it is possible to find a y such that $$xy \equiv 1 \mod 16$$. What the precise value of y is, we really don't care (we just want to know that it is possible to find such a y value). This is what Dick is hinting at. Since 16=2^4, the only divisors of 16 are powers of 2. Thus, the GCD of any odd number and 16 must be 1. What can you say about two numbers whose GCD is 1? (Think about the Euclidean algorithm, and then use the concept in the equations marked by ***). If you don't see this right away, consider the following: GCD(7,13) = 1 and

$$2\cdot 7 - 1\cdot 13 = \gcd(7,13) = 1$$

 

[MitsuZero]

I can't thank you guys enough for your help. David, your absolutetly correct in that a lot of my previous work was...illogical. Rather it was a mish-mash of ideas with no concrete direction.
rs1n, your explanation was absolutetly invaluable. Furthermore you helped me to understand the logical structure necessary to formulate a proof. Well I have come up with two separate proofs based off the ideas you gave me. I'm happy to say that they actually do make perfect sense (as proofs should). Anyways here they are:

1. This first proof is simply addressing the set R in relation to modulo 16. As such it is limited only to modulo 16.
**********

Given a finite set R={1, 3, 5, ..., 15}, then $$\forall r\in R$$, $$\exists y\in R$$ such that $$ry\equiv 1(mod 16)$$. The proof of this statement will be shown with a table of all values of r and y that are congruent to 1, modulo 16.

Now $$\forall$$$$x\in Z$$, if x is odd, $$\exists r\in R$$, such that $$x = 16n + r$$, where $$n\in Z$$.
Now $$x = 16n + r$$ can be rewritten as $$x\equiv r(mod 16)$$. So:

$$x\equiv r(mod 16)$$
Multiplying both sides by $$y\in Z$$:
$$xy\equiv ry(mod 16)$$
Hence, due to transitivity:
$$xy\equiv 1(mod 16)$$
Therefore it follows that:
$$\forall x\in Z$$, $$\exists y\in Z$$, such that $$xy\equiv 1(mod 16)$$ . ~ Q.E.D.

2. This is a much more general (and simpler) proof. As such it allows for any modulo.
**********
Per the Euclidean Algorithm, $$\forall x, n\in Z$$ $$\exists y, m\in Z$$, such that $$xy + nm = gcd(x,n)$$. This can be rewritten as $$xy\equiv gcd(x,n)(mod n)$$. Hence if $$n = 16$$, and $$x$$ is any odd integer, then $$gcd(x, 16) = 1$$, and $$xy\equiv 1(mod 16)$$. Therefore it follows that $$\forall x\in Z$$ $$\exists y\in Z$$, such that $$xy\equiv 1(mod 16)$$. ~ Q.E.D.How does it look? I'm pretty sure I'm taking some liberties with certain statements and assumptions.

 

[rs1n]

Proof #2 looks sound.

In proof #1, I would write

$$\forall x, \text{ if } x \text{ is odd, then } \exists n\in \mathbb{Z} \text{ and } r\in R \text{ such that } x = 16 n + r$$ (by the Euclidean algorithm)

Also, just before "Multiply both sides by y," you have to choose $$y\in R$$ such that $$yr\equiv 1 (\text{mod } 16)$$, and you can do so because of your table. So I would insert:

Let $$y\in R$$ be such that $$yr\equiv 1(\text{mod } 16)$$.

You may also want to mention that since $$y\in R$$ and $$R\subset \mathbb{Z}$$, it follows that $$y\in \mathbb{Z}$$ (as needed by the claim). Otherwise, it looks good to me.

 

[Dick]

Stick with proof #2. #1 is still rubbish. Sorry to be harsh. It simply doesn't have any content. rs1n is trying to add some, but once you repair it, it's basically the same as #2. BTW, I'm not David.

 

[rs1n]

Stick with proof #2. #1 is still rubbish. Sorry to be harsh. It simply doesn't have any content. rs1n is trying to add some, but once you repair it, it's basically the same as #2. BTW, I'm not David.

Unless there is an actual flaw in the proof, I don't see the reason to dismiss it as "rubbish." And no, I wasn't trying to add any content -- I simply was trying to help him get a solution using what he already had. It may not be as aesthetically pleasing, and perhaps it does not generalize esp. without becoming tedious, but it's certainly valid as far as the original problem statement is concerned.

Don't get me wrong, though. I agree that method 2 is preferred.

 

[Dick]

You are contentious, aren't you? Look, there is no line in proof #1 that does anything to convince me that the conclusion is true. Only restatements of the conclusion, presented as evidence of the truth of the conclusion.

 

[rs1n]

You are contentious, aren't you? Look, there is no line in proof #1 that does anything to convince me that the conclusion is true. Only restatements of the conclusion, presented as evidence of the truth of the conclusion.

No, please don't misunderstand. I'm not trying to be contentious -- I simply am asking for the flaw in the proof. You're claiming that the argument is begging the question, and I honestly don't see it (which is why I'm asking for help in seeing where I've assumed the conclusion).

Here's how I'd write it. Perhaps you'll allow me to just say that I have a table of inverses modulo 16 for each $$r\in R$$. If not, I'll include the table.

Let x be an odd integer. Then gcd(x,16) = 1. By the Euclidean algorithm, x can be written in the form x = 16n + r, where $$n\in \mathbb{Z}$$ and $$r\in R$$. By our table of inverses, we can always choose y to be the value such that $$yr \equiv 1 (\text{mod } 16)$$. (I presume that this may be the line which you think is begging the question. However, I don't see how it assumes the conclusion. We can do so because we have an explicit table of inverses. See remark *** below) Clearly such a y is also in Z. All that's left is to show that our choice of y also satisfies $$xy \equiv 1 (\text{mod } 16)$$

$$xy \equiv (16n + r ) y \equiv 16ny + ry \equiv ry \equiv 1 (\text{mod } 16)$$.

Since the problem is one of existence, we've shown that we can always pick a y in R (and hence in Z) that satisfies the desired congruence. You give me an odd integer x, I simply compute the remainder of x / 16, and then look up the corresponding inverse in the table.

It seems to me you're dismissing proof #1 because it does not generalize. That's fine. But when you wrote "rubbish," I presumed that you meant there was a flaw in the logic (as your second response seemed to indicate)

Remark ***

If your point is that such a table is easily computed through trial and error for small modulus but not larger modulus, then fine -- I've already agreed that becomes tedious and that the method does not generalize. I also agree that in general, you'd essentially have to rely on proof #2 to create the table anyway. So in this respect, one may as well just stick with proof #2. This is one of the reasons why I agree that proof #2 is preferred.

 

[Dick]

You are right. The problem is mine. I was completely missing the point of the 'finite table'. I thought the OP was extrapolating it to infinity without much justification. Explicitly saying all odds are congurent to something in the set justifies it. Apologies to you both.

 

[MitsuZero]

Dick I do apologize. I'm not sure why I saw David in place of Dick. Rs1n, I'll be sure to update the proof before I submit it. I emailed my professor with the same proof I posted, and he responded: "Your proof on the first problem looks good. It's a bit more "brute force" than a proof using the hint I gave, but it's a valid proof, and should get full credit."

I'm still adjusting to the idea of proofs. As much as I do actually enjoy them, I'm still far more comfortable doing computational mathematics.

Thanks again!