Author Topic: TT's Maths Thread (Read 135540 times) Tweet Share

TrueTears · « **Reply #1005 on:** July 09, 2010, 08:13:12 pm »

Another question which I need some clarification over.

How many classes of solutions are there to $x^2-1 \equiv 0 \pmod{168}$

So I did this:

1. Let a be the number of the classes of solutions to $x^2-1 \equiv 0 \pmod{2^3}$

2. Let b be the number of the classes of solutions to $x^2-1 \equiv 0 \pmod{3}$

3. Let c be the number of the classes of solutions to $x^2-1 \equiv 0 \pmod{7}$

So the classes of solutions to $x^2-1 \equiv 0 \pmod{168}$ is equal to $abc$

For case 1. We have $0, \pm 1, \pm 2, \pm 3, 4$ as congruence classes and only $\pm 1$ and $\pm 3$ works so that's 4 classes of solutions.

For case 2. We have $0, \pm 1$ as congruence classes and only $\pm 1$ works so that's 2 classes of solutions.

For case 3. We have $0, \pm 1, \pm 2, \pm 3$ as congruence classes and only $\pm 1$ works so that's 2 classes of solutions.

So all together we have $2^4 = 16$ classes of solutions.

However what I'm wondering is, isn't this way a bit primitive because if I worked out the PPF of some number other than 168 and ended up with say $2^{100}$ as one of the prime powers, then I would have to work out the number of classes of solutions to $x^2-1 \equiv 0 \pmod{2^{100}}$ Which means I have to list out $0, \pm 1, \pm 2 \cdots$ then test each of them to see if they work, wouldn't that take ages? Is there a faster way other than plugging a solution from each class of solutions into the equation and seeing if it works?

Thanks.

zzdfa · « **Reply #1006 on:** July 12, 2010, 04:54:58 pm »

There is a result that tells you how many solutions $x^2=n \mod p^a$ has for prime p and integer exponent a.

If p=2, then the number of solutions to $x^2=n \mod p^a$ is :
1 if a=1 and n=1 mod 2
2 if a=2 and n=1 mod 4
4 if a>=3, and n=1 mod 8
0 otherwise

If p an odd prime then $x^2=n \mod p^a$ has either 0 or 2 solutions. (It follows that the only solutions of $x^2=1 \mod p^a$ are $x= \pm 1$

As you can see, this result reduces the above problem to looking things up in a chart, and it isn't too hard to prove. You can do it via induction on the exponent 'a'. If you want hints or more info, check out "Elementary Number Theory; A Problem Oriented Approcah" by Joe Roberts, pg192. It's a nice book, the whole book is just one big problem set designed to guide you through elementary number theory.

TrueTears · « **Reply #1007 on:** July 12, 2010, 05:31:18 pm »

omg thanks man, ill definitely check that book out, again thanks heaps!!

btw we haven't spoken for ages, where have u been bro?

TrueTears · « **Reply #1008 on:** July 16, 2010, 12:29:22 am »

Show that $(A \cap B) \cup C = A \cap (B \cup C)$ is false for all sets A, B and C using direct proof.

I'm not sure how to finish off my proof... can someone please help

If we were to prove that the statement is true then we would need to show that if $x \in (A \cap B) \cup C$ then $x \in A \cap (B \cup C)$ and if $x \in A \cap (B \cup C)$ then $x \in (A \cap B) \cup C$

To formalise this we denote the following:

Let P(x) denote the proposition function " $x \in (A \cap B) \cup C$ " and Q(x) denote the proposition function " $x \in A \cap (B \cup C)$ "

Thus we need to show that $\forall x \left(P(x) \to Q(x)\right)$ and $\forall x \left(Q(x) \to P(x)\right)$

Let us first focus on $\forall x \left(P(x) \to Q(x)\right)$

Because we are using a direct proof let us assume the hypothesis P(x) is true. If we can show that Q(x) is false then the universally quantified statement is false and we have complete our proof.

Since P(x) is assumed to be true then $x \in (A \cap B) \cup C$ can be interpreted as $x \in (A \cap B)$ or $x \in C$ .

$x \in (A \cap B) \cup C$ is only true if:

1. $x \in (A \cap B)$ is true and $x \in C$ is true

2. $x \in (A \cap B)$ is true and $x \in C$ is false

3. $x \in (A \cap B)$ is false and $x \in C$ is true

Now Q(x) is interpreted as $x \in A$ and $x \in B \cup C$

Now what...?

TrueTears · « **Reply #1009 on:** July 16, 2010, 01:27:42 am »

Can someone check if my working is correct for the following proof?

Prove $X \cup (Y-X) = X \cup Y$ for all sets $X$ and $Y$ .

Let $P(x)$ be the proposition function ' $x \in X \cup (Y-X)$ ' and $Q(x)$ be the proposition function ' $x \in X \cup Y$ '

Let the domain of discourse of both these proposition functions be $\mathbb{U}$ , the universal set.

Now to prove the statement to be true we must show the following 2 universally quantified statements to be true:

1. $\forall x \in \mathbb{U} \left(P(x) \to Q(x)\right)$

2. $\forall x \in \mathbb{U} \left(Q(x) \to P(x)\right)$

To show case 1 to be true, first we know that if $P(x)$ is false then the case is vacuously true, so we will ignore this trivial case.

We will assume $P(x)$ to be true and if we can show that $Q(x)$ is also true then case 1 is true.

Now $P(x): \left(x \in X\right) \lor \left(x \in (Y-X)\right)$ and $Q(x): \left(x \in X\right) \lor \left(x \in Y\right)$

Since $P(x)$ is true then either

a. $x \in X$ is true and $x \in (Y-X)$ is false

b. $x \in X$ is false and $x \in (Y-X)$ is true

[Note: these 2 propositions can not be both true since they are mutually exclusive]

If we use case a. Since $x \in X$ is true $\implies \left(x \in X\right) \lor \left(x \in Y\right)$ is true $\implies Q(x)$ is true.

Now using case b. Since $x \in (Y-X)$ is true $\implies x \in Y$ is true $\implies \left(x \in X\right) \lor \left(x \in Y\right)$ is true $\implies Q(x)$ is true.

Thus we have shown case 1. to be true.

To show case 2 to be true, first we know that if $Q(x)$ is false then the case is vacuously true, so again we will ignore this trivial case.

We will assume Q(x) to be true and Q(x) is true if either of the following 3 conditions are satisfied.

i. $x \in X$ is true and $x \in Y$ is false

ii. $x \in X$ is false and $x \in Y$ is true

iii. $x \in X$ is true and $x \in Y$ is true

Now using case i. Since $x \in X$ is true $\implies \left(x \in X\right) \lor \left(x \in (Y-X)\right)$ is true $\implies P(x)$ is true.

Using case ii. Since $x \in Y$ is true $\implies x \in (Y-X)$ is true $\implies \left(x \in X\right) \lor \left(x \in (Y-X)\right)$ is true $\implies P(x)$ is true.

Now using case iii. Since $x \in X$ is true and $x \in Y$ is true $\implies \left(x \in X\right) \lor \left(x \in (Y-X)\right)$ is true $\implies P(x)$ is true.

Case 2 is now proven to be true.

We have completed our proof to show that the original statement is true.

zzdfa · « **Reply #1010 on:** July 16, 2010, 11:55:56 am »

why so formal are you studying logic?

oh wait you are :\

_why?

TrueTears · « **Reply #1011 on:** July 16, 2010, 02:59:49 pm »

lololololol

yea logic, they formalise everything pretty damn hardcore so im just going along with it haha

logic is alright, its not as boring as i expected it to be

TrueTears · « **Reply #1012 on:** July 17, 2010, 04:38:58 pm »

Just wondering do De Morgan's generalised laws work for double universal quantifiers?

Say we want to prove that a function is not one-to-one, in other words we need to prove that the negation of $\forall x_1 \forall x_2 \left[\left(f(x_1)=f(x_2)\right) \to \left(x_1=x_2\right)\right]$ is true.

$\neg \forall x_1 \forall x_2 \left[\left(f(x_1)=f(x_2)\right) \to \left(x_1=x_2\right)\right]$

$\equiv \exists x_1 \neg \forall x_2 \left[\left(f(x_1)=f(x_2)\right) \to \left(x_1=x_2\right)\right]$

$\equiv \exists x_1 \exists x_2 \neg \left[\left(f(x_1)=f(x_2)\right) \to \left(x_1=x_2\right)\right]$

$\equiv \exists x_1 \exists x_2 \left[\left(f(x_1)=f(x_2)\right) \land \neg \left(x_1=x_2\right)\right]$

$\equiv \exists x_1 \exists x_2 \left[\left(f(x_1)=f(x_2)\right) \land \left(x_1 \neq x_2\right)\right]$

Is that correct?

Mao · « **Reply #1013 on:** July 17, 2010, 04:51:48 pm »

On a completely unrelated notes, TT, just WHAT are you going to do when you run out of maths to study?

TrueTears · « **Reply #1014 on:** July 17, 2010, 05:03:27 pm »

lol, study moar

zzdfa · « **Reply #1015 on:** July 17, 2010, 06:54:12 pm »

yeah i think you just proved it, didn't you? [that demorgans laws work for nested universal quantifiers]. just use the first 3 lines and replace the proposition (is that what it's called?) $\left[\left(f(x_1)=f(x_2)\right) \rightarrow \left(x_1=x_2\right)\right]$ with an arbitrary proposition $P(x_1,x_2)$

TrueTears · « **Reply #1016 on:** July 17, 2010, 07:54:06 pm »

Quote from: zzdfa on July 17, 2010, 06:54:12 pm

yeah i think you just proved it, didn't you? [that demorgans laws work for nested universal quantifiers]. just use the first 3 lines and replace the proposition (is that what it's called?) $\left[\left(f(x_1)=f(x_2)\right) \rightarrow \left(x_1=x_2\right)\right]$ with an arbitrary proposition $P(x_1,x_2)$

ah yup, just wanted some confirmation, thanks

TrueTears · « **Reply #1017 on:** July 19, 2010, 02:40:55 am »

Can someone show me how to do this?

Show that if a relation R on a set X is symmetric and transitive but not reflexive, then the collection of sets [a], $a \in X$ (equivalence classes of X) does not partition X.

/0 · « **Reply #1018 on:** July 19, 2010, 08:22:31 am »

(hope this is right lol)

If $a \not\sim a$ , then $a \not\in [a]$

Suppose there is an arbitrary element $b\in [a]$ , so that $b \sim a$ .

But if $b \sim a$ , then $[a]=[b]$ :
Consider an arbitrary $x \in [b]$ . Then $b \sim x$ . Since $b \sim a$ , then by transitivity, $a \sim x$ . Hence, $[a]=[b]$ .

So if there exists an element $b \in [a]$ , then it must also be true that $b \in [b]$ . But since $b \not\sim b$ , $b \not \in [b]$ , so there exists no element $b \in [a]$ .

Hence, $[a]$ is empty and does not partition the set.

Ahmad · « **Reply #1019 on:** July 19, 2010, 11:21:46 am »

What's wrong with this logic?

I claim that a symmetric and transitive relation is also reflexive.

Let a be in X, and let b be in X such that a ~ b. Now being symmetric means b ~ a also, and transitivity implies a ~ a as required.

Search the forums now!

We have moved!

Author Topic: TT's Maths Thread (Read 135540 times) Tweet Share

TrueTears

Re: TT's Maths Thread

zzdfa

Re: TT's Maths Thread

TrueTears

Re: TT's Maths Thread

TrueTears

Re: TT's Maths Thread

TrueTears

Re: TT's Maths Thread

zzdfa

Re: TT's Maths Thread

TrueTears

Re: TT's Maths Thread

TrueTears

Re: TT's Maths Thread

Mao

Re: TT's Maths Thread

TrueTears

Re: TT's Maths Thread

zzdfa

Re: TT's Maths Thread

TrueTears

Re: TT's Maths Thread

TrueTears

Re: TT's Maths Thread

/0

Re: TT's Maths Thread

Ahmad

Re: TT's Maths Thread

Recent Posts

User:
Password: