The Student Room Group
Uni students - Complete our survey >>
Uni students - Complete our survey >>
Uni students - Complete our survey >>

The Proof is Trivial!

Scroll to see replies

Reply 300
Avatar for und
und
OP
16
Original post by Slumpy
Can't you do that in about one step? 1^2=3^2=5^2=7^2=1mod8, so the only a s.t. a^k=7mod8 for some k is 7.

Indeed! :lol: Now I just can't remember why I took k<l,m without loss of generality yesterday. :beard:
Reply 301
Avatar for Slumpy
Slumpy
16
Original post by und
Indeed! :lol: Now I just can't remember why I took k<l,m without loss of generality yesterday. :beard:


The order is irrelevant, so by relabeling you can guarantee that k<l,m.
Reply 302
Avatar for und
und
OP
16
Original post by Slumpy
The order is irrelevant, so by relabeling you can guarantee that k<l,m.

I know but what about k=l<m. I'm sure I had good reasons!
Reply 303
Avatar for und
und
OP
16
Solution 45

pk+pl+pm=n2p^k+p^l+p^m=n^2

Clearly we cannot have k=l=mk=l=m because this would imply that nn had a factor of 99 and hence that 3∣p3|p. Consider k<m,lk<m,l. By writing n2=pkq2n^2=p^{k}q^2 and dividing, we get:

1+pl−k+pm−k=q2⇒pl−k+pm−k=(q+1)(q−1)1+p^{l-k}+p^{m-k}=q^2 \Rightarrow p^{l-k}+p^{m-k}=(q+1)(q-1)

Since pp is odd, the right hand side is even and is a multiple of 232^3. Therefore in the case where l≠ml \neq m (with equality 44 does not divide the right hand side, so this is impossible) where we can assume without loss of generality that m−l≥1m-l \geq 1, pm−l=−1mod  8p^{m-l}=-1 \mod 8.

It can be shown by exhaustion that pm−l=−1mod  8p^{m-l}=-1\mod 8 for some m−l≥1m-l \geq 1 if, and only if, p=−1mod  8p=-1\mod 8.

Now consider k=l<m⇒pm−l=q2−2k=l<m\Rightarrow p^{m-l}=q^2-2. Clearly qq is odd, and by exhaustion it can be shown that the residue of (2r+1)2−2=−1mod  8(2r+1)^2-2=-1\mod 8, completing the proof.
(edited 11 years ago)
Original post by und
Solution 45 (almost complete)

pk+pl+pm=n2p^k+p^l+p^m=n^2

Clearly we cannot have k=l=mk=l=m because this would imply that nn had a factor of 99 and hence that 3∣p3|p. Furthermore, ... Therefore, without loss of generality we can assume k<m,lk<m,l. By writing n2=pkq2n^2=p^{k}q^2 and dividing, we get:

1+pl−k+pm−k=q2⇒pl−k+pm−k=(q+1)(q−1)1+p^{l-k}+p^{m-k}=q^2 \Rightarrow p^{l-k}+p^{m-k}=(q+1)(q-1)

Since pp is odd, the right hand side is even and is a multiple of 232^3. Therefore in the case where l≠ml \neq m (with equality 44 does not divide the right hand side, so this is impossible) where we can assume without loss of generality that m−l≥1m-l \geq 1, pm−l=−1mod  8p^{m-l}=-1 \mod 8.

It can be shown by exhaustion that pm−l=−1mod  8p^{m-l}=-1\mod 8 for some m−l≥1m-l \geq 1 if, and only if, p=−1mod  8p=-1\mod 8, completing the proof.


Doesn't k have to be even for this to be true?
Reply 305
Avatar for und
und
OP
16
Original post by metaltron
Doesn't k have to be even for this to be true?

If k is odd then n is not an integer.
Reply 306
Avatar for Mladenov
Mladenov
1
Original post by und
...


Excellent. The last step can be done by contradiction.

Spoiler

Original post by und
If k is odd then n is not an integer.


Of course! Well done. :smile:
This has a really neat little solution. And it is a good demonstration of how useful modular arithmetic can be.

Problem 49**

Show that 7∣55552222+22225555 7| 5555^{2222} + 2222^{5555}
Reply 309
Avatar for Mladenov
Mladenov
1
Solution 49

We have 22225555+55552222≡35+42≡0(mod7)2222^{5555}+5555^{2222} \equiv 3^{5}+4^{2} \equiv 0 \pmod7.
Reply 310
Avatar for und
und
OP
16
Original post by Mladenov
Excellent. The last step can be done by contradiction.

Spoiler


I still need to prove it for k=l<mk=l<m. :beard:
Reply 311
Avatar for und
und
OP
16
Original post by Mladenov
Solution 49

We have 22225555+55552222≡35+42≡0(mod7)2222^{5555}+5555^{2222} \equiv 3^{5}+4^{2} \equiv 0 \pmod7.

What are the conditions for replacing everything with its modular counterpart? I'm not that familiar with modular arithmetic so I should probably read up on it a little.
Reply 312
Avatar for Mladenov
Mladenov
1
Original post by und
I still need to prove it for k=l<mk=l<m. :beard:


Not really. Assume k=l<mk=l<m. Then pm−l+2p^{m-l}+2 is a perfect square (why?). Hence pm−l≡−1(mod8) p^{m-l} \equiv -1 \pmod 8.

Original post by und
What are the conditions for replacing everything with its modular counterpart? I'm not that familiar with modular arithmetic so I should probably read up on it a little.


Those are relatively prime to 7. Use Fermat's little theorem and (mod6)\pmod 6
(edited 11 years ago)
Reply 313
Avatar for und
und
OP
16
Original post by Mladenov
Not really. Assume k=l<mk=l<m. Then pm−l+2p^{m-l}+2 is a perfect square (why?). Hence pm−l≡−1(mod8) p^{m-l} \equiv -1 \pmod 8.

It's clear that it's a perfect square but the second part isn't that clear in my opinion so I'll add it in.
Problem 50:

An inextensible rope of length l and uniform mass per unit length lies on a rough table with one end on an edge. The co-efficient of friction between the table and the rope is μ. The rope receives an impulse which sets it moving off of the edge of the table at speed v. Prove that, if the rope does not fall off the table, then:

v2<lgμ21+μ v^2<\dfrac{lg\mu^2}{1+\mu }

By considering this as μ \mu varies between zero and 1, find the maximum possible impulse that could potentially be given to the rope without it falling off of the table.
Reply 315
Avatar for und
und
OP
16
Original post by DJMayes
Problem 50:

An inextensible rope of length l and uniform mass per unit length lies on a rough table with one end on an edge. The co-efficient of friction between the table and the rope is μ. The rope receives an impulse which sets it moving off of the edge of the table at speed v. Prove that, if the rope does not fall off the table, then:

v2<lgμ21+μ v^2<\dfrac{lg\mu^2}{1+\mu }

By considering this as μ \mu varies between zero and 1, find the maximum possible impulse that could potentially be given to the rope without it falling off of the table.

Having solved the equation and obtained something not very nice, I don't feel inclined to continue! :tongue:
(edited 11 years ago)
Reply 316
Avatar for Mladenov
Mladenov
1
Problem 51**

One of my favorite number theory problems.

Let n>1n >1 be an integer, and kk be the number of distinct prime divisors of nn. Then there exists an integer aa, 1<a<nk+11<a<\frac{n}{k}+1, such that a2≡a(modn)a^{2} \equiv a \pmod n.

Problem 52**

Find all infinite bounded sequences a1,a2,...a_{1},a_{2},... of positive integers such that for each n>2n> 2, an=an−1+an−2(an−1,an−2)a_{n}=\frac{a_{n-1}+a_{n-2}}{(a_{n-1},a_{n-2})}.

Problem 53**

For those who have not covered much number theory.

Let kk be a positive integer. Then there exist infinitely many positive integers nn such that n2k−7n2^{k}-7 is a perfect suqare.
Original post by und
Having solved the equation and obtained something not very nice, I don't feel inclined to continue! :tongue:


:lol:

If you want to check solutions then you can PM me; mine may well need checking as well. :tongue:
Reply 318
Avatar for around
around
13
Original post by ukdragon37
A little, yes. But then topos theory is quite a different beast to set theory. :tongue:


In the Cambridge 4th year some people (tried) to run a Topos Theory reading group. I think in the end only about 5 or so people finished the course.

I started it and then gave up after about 6-7 'lectures' because it was just utterly incomprehensible.
Reply 319
Avatar for und
und
OP
16
Original post by DJMayes
:lol:

If you want to check solutions then you can PM me; mine may well need checking as well. :tongue:

This didn't exactly inspire confidence:

x=(μl2g(μ+1)+v2gl(μ+1))egl(μ+1)t+(μl2g(μ+1)−v2gl(μ+1))e−gl(μ+1)t−μlg(μ+1)\displaystyle x=\left( \frac{\mu l}{2g(\mu +1)}+\frac{v}{2\sqrt{\frac{g}{l}(\mu +1)}} \right) e^{\sqrt{\frac{g}{l}(\mu +1)}t} + \left( \frac{\mu l}{2g(\mu +1)}-\frac{v}{2\sqrt{\frac{g}{l}(\mu +1)}} \right) e^{-\sqrt{\frac{g}{l}(\mu +1)}t}-\frac{\mu l}{g(\mu +1)}

Quick Reply

Related discussions

Latest

Trending

Trending

Articles for you