[SsEe]

I need to test those colours.

REDslkgh;lskdfg;lksdfjg;lksjdfgk js
GREENsdflkgjs;ldfkgjs;ldkfgjslkd fjg

You're such a pain in the ass with those colours. Why not red and blue or something.

Perfect squares modulo 3:
0² = 0
1² = 1
2² = 1
=> squares can only be written either as 3q or 3q+1 q is positive integer.

[JFN]

Here's an interesting problem I came across: prove that if you pick n+1 integers less than or equal to 2n, then at least 2 of them must be relatively prime. It took me ten minutes to come up with the simple proof, but its still interesting.

[dvs]

(Original post by JFN)
Here's an interesting problem I came across: prove that if you pick n+1 integers less than or equal to 2n, then at least 2 of them must be relatively prime. It took me ten minutes to come up with the simple proof, but its still interesting.

Consider the set {1, 2, 3, ..., 2n} from which you want to select n+1 integers. Partition the set into the subsets {1,2}{3,4}...{2n-1,2n}. Then according to the pigeonhole principle, if you pick n+1 integers then at least 2 of them will lie in one of the n subsets you created. And since gcd(n,n+1)=1, they'd be relatively prime.

[john !!]

(2) Prove that if a given integer n is a perfect square then either n=3q or n=3q+1 for some ineteger q.

n is a perfect square so can be written a^2, where a is an integer.
the conditions to show are that either:
a*a = 3q OR a*a = 3q + 1

this condition can be proven by showing that:

a*a is not equal to 2 (mod 3), or that
a*a =/= 3q + 2

where a and q are still integers.

by square rooting both sides,

a = sqrt(3q + 2)

we must now show that sqrt(3q + 2) is not an integer, for all values of q.
using induction, and testing the case for q=0,
sqrt 2 is not an integer.

now assume it is true for all q, and show it is true for q+1:

sqrt(3(q+1) + 2)) = sqrt(3q + 5)
now I will show that sqrt(3q+5) cannot be an integer...

*15 minutes, and a lot of messy weird work to do with roots of a quadratic, proof by contradiction and double negatives, later*

... well, that's that. I leave for someone else to continue in my messy footsteps.

(Q.E.D.) ..not quite

[Flytterbye]

Um...can I join? I'm kinda new, and I'm joining random societies (only the best ones, of course... *bats eyelashes*)

Pretty please?


Flytterbye

[lgs98jonee]

(Original post by mik1a)
(2) Prove that if a given integer n is a perfect square then either n=3q or n=3q+1 for some ineteger q.

n is a perfect square so can be written a^2, where a is an integer.
the conditions to show are that either:
a*a = 3q OR a*a = 3q + 1

this condition can be proven by showing that:

a*a is not equal to 2 (mod 3), or that
a*a =/= 3q + 2

where a and q are still integers.

by square rooting both sides,

a = sqrt(3q + 2)

we must now show that sqrt(3q + 2) is not an integer, for all values of q.
using induction, and testing the case for q=0,
sqrt 2 is not an integer.

now assume it is true for all q, and show it is true for q+1:

sqrt(3(q+1) + 2)) = sqrt(3q + 5)
now I will show that sqrt(3q+5) cannot be an integer...

*15 minutes, and a lot of messy weird work to do with roots of a quadratic, proof by contradiction and double negatives, later*

... well, that's that. I leave for someone else to continue in my messy footsteps.

(Q.E.D.) ..not quite

Btw, sorry if this got answered ages ago but I could not help myself when I saw I could do it

n=a^2
if a is a multiple of 3, then a^2 is of the form 3q

if a is not a multiple of 3, then
a^2=3q+1
a^2-1=3q
(a+1)(a-1)=3q

Therefore, either a+1 or a-1 is a multiple of 3. That last sentence probably needs a bit of proof but there we go.

[john !!]

very nice

[JamesF]

(Original post by lgs98jonee)
Btw, sorry if this got answered ages ago but I could not help myself when I saw I could do it

n=a^2
if a is a multiple of 3, then a^2 is of the form 3q

if a is not a multiple of 3, then
a^2=3q+1
a^2-1=3q
(a+1)(a-1)=3q

Therefore, either a+1 or a-1 is a multiple of 3. That last sentence probably needs a bit of proof but there we go.

What does that prove?

[SsEe]

Perfect squares modulo 3:
0² = 0
1² = 1
2² = 1
=> squares can only be written either as 3q or 3q+1 q is positive integer.

1) Does the equation
x³ - 117y² = 5
have integer solutions for x and y. If so find them. (SOLVED)

2) Find the remainder of 1000! / 3^300. What about 1000!/3^400 ? What's the highest power of 3 that will divide 1000! ?
Can you come up with something more general, for any n!/a^b where a, b and n are positive integers?

3) Show that the greatest common divisor of any two consecutive terms in the Fibonacci sequence is 1. Denote F(n) the nth number in the sequence. F(0) = F(1) = 1 (SOLVED)

4) Let G be a group. Show that if the square of every element of G is equal to the identity element then G is abelian. (SOLVED)

5)We are given a positive integer r and a rectangular board divided into 20 x 12 unit squares. The following moves are permitted on the board: one can move from one square to another only if the distance between the centers of the two squares is √r. The task is to find a sequence of moves leading between two adjacent corners of the board which lie on the long side.

(a) Show that the task cannot be done if r is divisible by 2 or 3.
(b) Prove that the task is possible for r = 73.
(c) Can the task be done for r = 97?

6) Prove that 1! + 2! + 3! + ... + n! is only a perfect square for n=1 or n=3.

7) Can 801,345,230,914 be written as the sum of 3 cubes?

[john !!]

(Original post by SsEe)
Perfect squares modulo 3:
0² = 0
1² = 1
2² = 1
=> squares can only be written either as 3q or 3q+1 q is positive integer.

But surely that doesn't prove there isn't a counter example for a million digit square?

[SsEe]

It's modulo 3. If a² has a million digits a can still be written as either 0, 1 or 2 modulo 3.

[lgs98jonee]

(Original post by JamesF)
What does that prove?

Sorry, I thought that one of the questions was to show that n (a perfect square) is either divisible by 3q or 3q+1 and that I showed it to be true.
Now I am confused

[RichE]

(Original post by lgs98jonee)
Sorry, I thought that one of the questions was to show that n (a perfect square) is either divisible by 3q or 3q+1 and that I showed it to be true.
Now I am confused

[Sorry if this a little patronising, but don't know how aware of modular arithmetic rules you are.]

Note that if you square an odd (resp. even) number, you get an odd (resp. even) number. It didn't matter what that "odd" number was. The reason is that an odd number can be written 2k+1, and try squaring that and expanding.

Similarly for "mod 3" arithmetic there are multiples of 3, and two types of "odd", those that are one more than a multiple of 3 (of the form 3k+1), or one under (of the form 3k-1).

If you square a multiple of 3 you have another such multiple.

But (3k+1)^2 = 3(3k^2+2k)+1
and (3k-1)^2 = 3(3k^2-2k)+1
both of which are of the form 3q+1.

All the question says is that a square is never of the form 3q+2.

Or equivalently that 3 never divides n^2-2 for any n.

[RichE]

(2) Prove that exp(x).exp(y) = exp(x+y) , where exp(x) is exponential function

A nicer proof of this comes if you take as your defintion that exp is its own derivative and that exp(0)=1.

Then it's easy to check for an arbitrary constant a,

f(t) = exp(a+t)exp(-t)

differentiates (wrt t) to zero and hence is constant. Note that f(0)=exp(a).

So

exp(a+t)exp(-t) = exp(a)

Set a = x+y and t = -y for the required equality.

[lgs98jonee]

Ok fair enough. But what was wrong with my attempt to the perfect square question? James seemed to think there was something wrong so I would be glad of any reassurance/explanation

[SsEe]

I think it would be better written:
If a is a multiple of 3 then a² is a multiple of 3.
If a is not a multiple of 3 then either (a-1) or (a+1) is.
From that (a-1)(a+1) is a multiple of 3.
(a-1)(a+1) = a² - 1 = 3q for some integer q.
a² = 3q + 1

It's a very nice proof.

[RichE]

(Original post by lgs98jonee)
Ok fair enough. But what was wrong with my attempt to the perfect square question? James seemed to think there was something wrong so I would be glad of any reassurance/explanation

Isn't it that what you're proving is irrelevant, rather than the proof being incorrect?

You seem to prove that if n^2 is 1 mod 3, then n is 1 or 2 mod 3.

Aren't you trying to exclude the possibility of n^2 being 2 mod 3 though? In SsEe's edit, he rearranges the logic to this effect.

[dvs]

(deleted)

[J.F.N]

(Original post by SsEe)
4) Let G be a group. Show that if the square of every element of G is equal to the identity element then G is abelian.

Consider any two elements a,b in G
a^2 = e
b^2 = e
ab = e.ab.e = (b^2).ab.(a^2) = b.(ba).(ba).a (by associativity) = b.(ba)^2.a
By closure, ba is in G. Therefore, ba^2 = e. Hence
b.(ba)^2.a = b.e.a = ba
--> ab=ba
--> G is Abelian

Here is another classic group theory question: prove that every cyclic group is abelian.

[SsEe]

"Here is another classic group theory question: prove that every cyclic group is abelian."

I haven't done any group theory but would it be enough to say:
Call the generator a and the operation *.
All elements are of the form a^k so given two elements a^m and a^n
(a^m)*(a^n) = [a*a*a*... (m times)]*[a*a*a*... (n times]
By associativity this can be "re bracketed" to [a*a*a*... (n times)]*[a*a*a*... (m times] = (a^n)*(a^m)