Official TSR Mathematical Society
Maths and statistics discussion, revision, exam and homework help.
-
- Reputation:
- Adored and Respected Member
- Location: Cambridge
Nice, you get the idea. Here's a simpler way to do it using your notation:(Original post by 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)
Consider two elements b,c. Since the group is cyclic, b=a^m and c=a^c
bc=a^m.a^n=a^(m+n)=a^(n+m)=a^n.a ^m=cb
I'd be glad to provide more interesting group theory problems for those interested. -
- Reputation:
- Overlord in Training
- Location: a.e.
- Posts: 2,134
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(Original post by SsEe)
Did you manage to do any of my other questions?
Assume that gcd(F(n),F(n+1)) > 1, then:
F(n+1) = F(n) (mod a), where a>1
F(n+1) - F(n) = 0 (mod a)
F(n-1) = 0 (mod a) [since F(n) and F(n+1) are consecutive their sum is F(n+2) and their difference is F(n-1)]
Since both F(n) and F(n-1) are both divisible by a>1, then so would F(n)-F(n-1)=F(n-2), as would F(n-1)-F(n-2)=F(n-3); then F(n-4), F(n-5), ... F(n-r) would also be divisible by a>1. When r=n, F(n-r)=F(0). By our assumption F(0) should also be divisible by a>1, but F(0)=1.
Contradiction.
Hopefully that wasn't too inelegant. -
- Reputation:
- Overlord in Training
- Location: a.e.
- Posts: 2,134
1) Does the equation
x³ - 117y² = 5
have integer solutions for x and y. If so find them.
Rewrite the equation:
y² = (x³-5)/117
Now consider:
x³ = 5 (mod 117), so solutions only exist if 5 is a perfect cube modulo 117.
I did this in my previous (deleted) post. In it I said that I thought 5 isn't a perfect cube so no solutions exist, but later I found that 5 is a perfect cube (don't remember for what x). So I don't know...
-
- Reputation:
- Vengeful, Imperial Overlord of The Student Room
- Posts: 4,064
Yeah. Fibonacci one's fine.
I said basically the same thing:
Assume that gcd[F(n),F(n+1)] = a, a>1
F(n) = ap and F(n+1) = aq for some integers p and q.
F(n+1) - F(n) = a(q-p) = F(n-1). So if F(n+1) and F(n) are multiples of a, F(n-1) is a multiple of a. From that F(n-2), F(n-3),... must all be multiples of a. But that means F(0)=1 is a multiple of a>1. Contradiction and gcd[F(n),F(n+1)]=1
For (1), the bad thing about your way is that you have to test it for loads of values of x. That'll work but it takes way too long and there's a much nicer way of doing the question. -
- Reputation:
- Adored and Respected Member
- Location: Cambridge
Question 1 isn't as harmless as it seems. I tried to prove that there are no integer solutions using a descent-type argument, but I don't know if its going to work. This is the problem with seemingly simply Diophantine equations.. they look easy but they are in fact complicated elliptic curves.
-
- Reputation:
- Overlord in Training
- Location: a.e.
- Posts: 2,134
Perhaps if we consider x³ = 117y² (mod 5), then we can see the only way 117y² would be an integer modulo 5 is when y=0. That leaves us with x³=5 which means no integer solutions exist. But is that really the case?
I know I'm missing something! -
- Reputation:
- Benevolent Member
x^3-117y^2=5 take mod3(Original post by dvs)
Perhaps if we consider x³ = 117y² (mod 5), then we can see the only way 117y² would be an integer modulo 5 is when y=0. That leaves us with x³=5 which means no integer solutions exist. But is that really the case?
I know I'm missing something!
x^3=2 mod 3
by flt x^2=1 mod 3
so x=2 mod 3
say x is a solution
x=3k+2 for some k
so
27k^3+54k^2+36k-117y^2+8=5
now take mod9 to get
8=5 mod 9
contradiction.
so no x exists. -
- Reputation:
- Vengeful, Imperial Overlord of The Student Room
- Posts: 4,064
Yeah. That works. The easiest way IMO is as follows:
Assume an integer solution exists and consider the hypothetical solution modulo 9:
x³ = 5 (mod 9)
Also consider cubes modulo 9:
0³=0, 1³=1, 2³=8, 3³=0, 4³=1, 5³=8, 6³=0, 7³=1, 8³=8
From this we can conclude that no cube is congruent to 5 modulo 9 and so no integer solution can exist. -
- Reputation:
- Benevolent Member
1000!/3^100 has no remainder.(Original post by SsEe)
Yeah. That works. The easiest way IMO is as follows:
Assume an integer solution exists and consider the hypothetical solution modulo 9:
x³ = 5 (mod 9)
Also consider cubes modulo 9:
0³=0, 1³=1, 2³=8, 3³=0, 4³=1, 5³=8, 6³=0, 7³=1, 8³=8
From this we can conclude that no cube is congruent to 5 modulo 9 and so no integer solution can exist.
roughly because all the numbers from 112-333 can be multiplied by 3 and still appear in 1000! so we can cancel out all 3s in the denominator with these multiples of 3 in the numerator.
oops wrong question!
for 300 answer still the same need more 3s but
1000! contains the 3 times table upto 333. -
- Reputation:
- Vengeful, Imperial Overlord of The Student Room
- Posts: 4,064
OK. Well done. That was too easy though
. I'll extend it.
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? -
- Reputation:
- Benevolent Member
well for 3^400 need to find a few more 3s.(Original post by SsEe)
OK. Well done. That was too easy though . I'll extend it.
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?
we can find them by considering the 9 times table upto 111 so that gives us the extra 100 3s we need.
the highest power will be
[1000/3]+[1000/9]+[1000/27]+[1000/81]+[1000/243]+[1000/729]
=333+111+37+12+4+1
=498 -
- Reputation:
- Benevolent Member
a) let e be the identity and x have order n(Original post by J.F.N)
Here's another group theory problem:
Prove that the cyclic group C generated by an element of order n has n distinct elements.
SsEe, where do you get your questions from?
the elements x,x^2,x^3....x^n are distinct
proof assume x^m=x^s for some m,s<n
then x^(m-s)=e (group so inverses exist)
but m-s<n contradiction since x has order n and the order of an element is the least power of the element which gives e
b) there are no more elements.
assume there exists g in G not equal to one of the x^m for m=1,2,..,n
since x generates G must have g=x^m with m>n
then m=qn+r with r<n
so x^m={x^(n)}^q.x^(r)
=> x^m=x^{r} with r<n
contradiction. -
- Reputation:
- Vengeful, Imperial Overlord of The Student Room
- Posts: 4,064
Erm, some off the questions we were given to answer when we arrived at Worcester College, one's off the IMO (don't go looking for the answer!), some from a book that I was reading a while ago, some I make up.
Yeah. I answered the question but evariste did it in the same way so there's no point in me posting my answer.
