Official TSR Mathematical Society

Yeah. I could do with learning some group theory.

Did you manage to do any of my other questions?

Reply 42

SsEe

Did you manage to do any of my other questions?

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

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.

Reply 43

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

Reply 44

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.

Reply 45

No integer solutions exist?

Reply 46

J.F.N

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.

Reply 47

Ahhhh. I hope I don't have to tell you the solution as you'll all kick yourselves so hard. :smile:

I've added another 2 questions to my post.

Reply 48

lgs98jonee

2

How about x=626, y=1448?

Reply 49

That's 8. We want 5.

By the by. :smile:

. How did you obtain the solution. The method may be helpful.

Reply 50

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!

Reply 51

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-117y^2=5 take mod3
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.

Reply 52

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.

Reply 53

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.

1000!/3^100 has no remainder.
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.

Reply 54

OK. Well done. That was too easy though :smile:

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

Reply 55

SsEe

OK. Well done. That was too easy though :smile:

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

well for 3^400 need to find a few more 3s.
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

Reply 56

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?

Reply 57

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?

a) let e be the identity and x have order n
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.

Reply 58