Two questions from my pre-calc book. I have a solution to the first one, but I think I am missing something
obvious on the second.

Edit: Got the second.

43. $ x^{ \minus{} \frac {1}{2}} \minus{} 2x^{\frac {1}{2}} \plus{} x^{\frac {3}{2}}$

[hide="my solution"]
let $ x^{\frac {1}{2}} \equal{} a$, and let the entire expression equal $ y$

we get $ a^{ \minus{} 1} \minus{} 2a \plus{} a^{3} \equal{} y$
multiplying by $ a$ yields $ 1 \minus{} 2a^{2} \plus{} a^{4} \equal{} ay$
which factors to $ a^{ \minus{} 1}(a^{2} \minus{} 1) \equal{} y$
and substituting back $ x^{ \minus{} \frac {1}{2}}(x \minus{} 1)^{2}$
[/hide]

47. $ (x^{2} \plus{} 2)^{\frac {5}{2}} \plus{} 2x(x^{2} \plus{} 2)^{\frac {3}{2}} \plus{} x^{2}\sqrt {x^{2} \plus{} 2}$

[hide="my solution"]
Once again let $ (x^{2} \plus{} 2)^{\frac {1}{2}} \equal{} a$
we obtain $ a^{5} \plus{} 2xa^{3} \plus{} ax^{2}$
which factorizes to $ a (a^{2} \plus{} x)^{2}$
and substituting back gives $ (x^{2} \plus{} 2)^{\frac {1}{2}}(x^{2} \plus{} x \plus{} 2)$
[/hide]

I thought these were relatively hard considering we've only had class for one day so far. Well enjoy.

They're for anyone to solve I want to see if anyone can come up with a quicker and more direct way to solve them though, they were bugging me for quite a bit.


Emilio, a video game consultant, charges a 25 dollar service charge for a house call which includes the first hour of work, and 15 dollars for each additional hour or part of an hour. Last Saturday, he made 3 house calls for $ 1\frac{1}{2}$hours and 2 hours and 15 minutes, and 1 hour. How many total dollars were his charge?

[quote="GameBot"]Emilio, a video game consultant, charges a 25 dollar service charge for a house call which includes the first hour of work, and 15 dollars for each additional hour or part of an hour. Last Saturday, he made 3 house calls for $ 1\frac {1}{2}$hours and 2 hours and 15 minutes, and 1 hour. How many total dollars were his charge?[/quote]

$ 40\plus{}55\plus{}25\equal{}120$.


number theory
prime numbers
number theory unsolved

An good problem .
Let $ m = \prod_{p\in P} p$
Consider $ x = 2^{m + 1}$
We will prove that x satisfy condition .
$ x = 2^m + 2^m = (2^{\frac {m}{p})^{p} + (2^{\frac {m}{p})^{p},   \forall p\in A}}$
So it can be represent in the form $ a^p + b^p,   \forall P\in A$
Next step we will prove that equation $ 2^m = a^p + b^p$ has not solution which p is not in A.
Case 1 : p=2 .
Then $ a = 2^{k_1}a',b = 2^{k_2}b'$ where $ a\equiv b\equiv 1 (\mod 2 )$
Easy to check that $ k_1 = k_2,a' = b' = 1$
Case $ p > 2$
$ a = 2^{k_1}c,b = 2^{k_1}d$ where $ c\equiv d\equiv 1 (\mod 2)$
Suppose $ a^p + b^p = 2^{m + 1}$ then $ k_1 = k_2$
Because $ \frac {c^p + d^p}{c + p}|a^p + b^p$ and $ \frac {c^p + d^p}{c+d}\equiv 1 (\mod 2 )$
From equation we must have $ \frac {c^p + d^p}{c + d} = 1$ and $ (c,d) = (1,1)$
It gives that $ a = b = 2^k$
So $ 2^pk = 2^m$ or $ p|m$ ,so $ p\in p$ (contradiction )
Problem claim .

[quote="discredit"]Given a finite set $ P$ of prime numbers, prove that there exists a positive integer $ x$ such that it can be written in the form $ a^p \plus{} b^p$ ($ a,b$ are positive integers), for each $ p\in P$, and cannot be written in that form for each $ p$ not in $ P$.[/quote]

What if we remove the condition that $ p$ is in $ P$?
Also if we have $ x^{p}$ instead of $ x$ and $ a,b,x,p$ are reals then what would we get?
I know that then $ p$ cannot be any natural number other than $ 1$ and $ 2$!

I had posted this before but no reply!

The claim is that $(a, b) = (2, 2)$ gives our desired number. To show this, we prove the following claim.

$\textbf{Claim:}$ When $a^p + b^p = 2^k$ for some positive integers $a, b, k$, $k \equiv 1 \pmod{p}$ for odd primes $p$.

$\textbf{Proof:}$ Assume that $k$ is the smallest number such that, for a given $p$, there exists positive integers $a, b$ such that $a^p + b^p = 2^k$ and $k \not\equiv 1pmod{p}$. It is clear that $a$ and $b$ are even. This is because if they are even, $(\frac{a}{2})^p + (\frac{b}{2})^p = 2^{k-p}$, contradicting our minimality assumption. Therefore, $a$ and $b$ are even. Now, we have that $a^p + b^p \equiv 1 \pmod{2^k}$. In other words, $(\frac{a}{b})^p \equiv -1 \pmod{2^k}$ since $p$ is odd. Therefore, $(\frac{a}{b})^{2p} \equiv 1 \pmod{2^k}$. Combining this with $(\frac{a}{b})^{2^{k-1}} \equiv 1 \pmod{2^k}$, $(\frac{a}{b})^{2} \equiv 1 \pmod{2^k}$. In other words $a \equiv \pm b \pmod{2^k}$. Notice that $a \not\equiv b + n \cdot 2^k$ because  if $a = b$, $k \equiv 1 \pmod{p}$ and if $n > 1$, $a^p + b^p > 2^k$. Similarly, $a + b \not\equiv 2^k \cdot n$ for some $n$ because $a^p + b^p = 2^k$. Thus a contradiction.

In addition, we know that $p=2$ should not be a trouble because the sum of two squares theorem gives that there is only one way to write $2^{2n}$ as sum of two squares of nonnegative integers, which is $2^{2n} + 0$. Therefore, we conclude that $(a, b) = (2, 2)$ works.

Let $N=\prod_{p \in P} p$. I claim that $x=2^{N+1}$ works. It can clearly be expressed in the form $a^p+b^p$ for any $p \in P$, by taking $a=b=2^{N/p}$, so I will show that for any $p \not \in P$, $x$ cannot be represented in the form $a^p+b^p$. The key idea is to apply the "not necessarily coprime" version of Zsigmondy's, which states that if $x,y$ are two distinct positive integers, then $x^n+y^n$ always has some primitive prime divisor, except when $\{x,y\}=\{k,2k\}$ for some positive integer $k$ and $n=3$. Clearly, this is equivalent to the original.

By applying this, we find that if $x$ can be represented in the form $a^p+b^p$ for any prime $p$, then we either have $\{a,b\}=\{k,2k\}$ for some $k$ and $p=3$, or $a=b$, since otherwise $a^p+b^p$ is divisible by at least two distinct primes. However, if $\{a,b\}=\{k,2k\}$ and $p=3$, then $3 \mid a^p+b^p$, which is bad as well. Therefore we must have $a=b$, and this common value must equal $2^t$ for some nonnegative integer $t$, hence $a^p+b^p=2^{pt+1}$ has 2-adic valuation congruent to $1$ modulo $p$, which is clearly only true for $p \in P$. $\blacksquare$


n is an integer, n-1 is divisible by 3, n^2 -1 is divisible by 4 and n^3 -1 is divisible by 5. Find all possible values of n.

[color=#666666]Hi...........[/color]

[quote="dgreenb801"]The first condition says n=3a+1, the second 2b+1, and the third 5c+1, so in total, the number must be 30k+1 :) [/quote]dgreenb801's answer is wrong because AndrewTom's problem is another.

AndrewTom's problem (by $ LaTex$) is:
$ n$ is an integer, $ 3|n\minus{}1$ , $ 4|n^2\minus{}1$ and $ 5|n^3\minus{}1$.  Find all possible values of $ n$.

[hide="Click to show my sol"]$ 3|n\minus{}1 \Rightarrow n\equal{}3k\plus{}1$    $ ^{[1]}$
$ 4|n^2\minus{}1 \Rightarrow 4|(n\minus{}1)(n\plus{}1) \Rightarrow 4|3k(n\plus{}1)   \Rightarrow$     $ 4|k$     OR      $ 4|n\plus{}1$
$ 5|(n\minus{}1)(n^2\plus{}n\plus{}1) \Rightarrow 5|3k(n^2\plus{}n\plus{}1)$    $ \Rightarrow$     $ 5|k$     OR     $ 5|n^2\plus{}n\plus{}1$

$ IF$   $ 4|k$ , $ 5|k$ : $ k\equal{}20l$ ($ l \in \mathbb{Z}$) $ \Longrightarrow^{[1]}$   $ \forall l\in\mathbb{Z} : n\equal{}60l\plus{}1$
$ IF$   $ 4|k$ , $ 5|n^2\plus{}n\plus{}1$ :   $ ...$ (please you continue)
$ IF$   $ 4|n^2\minus{}1$ , $ 5|k$ :       $ ...$ (please you continue)
$ IF$   $ 4|n^2\minus{}1$ , $ 5|n^2\plus{}n\plus{}1$: $ ...$ (please you continue)

if don't find answer tell me again.
[/hide]

Thanks. I had the same result, using mod 3, 4 and 5, i.e. the same method.

How irritating! Just about to rush out and saw vandermond's post. Gotta run but will get back.

Chinese Remainder Theorem

$ n \equiv 1 \mod 3 \qquad(1)$
$ n^2 \equiv 1 \mod 4 \qquad(2)$
$ n^3 \equiv 1 \mod 5 \qquad(3)$

From $ (1)\longrightarrow n\equal{}3l\plus{}1$. Sub into $ (2)$
$ 9l^2\plus{}6l\plus{}1 \equiv 1 \mod 4 \Longrightarrow l^2\plus{}2l \equiv 0 \mod 4$
$ \Rightarrow l \equiv 0 \mod 4$ or $ l\equiv 2 mod 4 \Longrightarrow l \equal{} 2k \Rightarrow n\equal{}6k\plus{}1$

sub into $ (3)$
$ (6k\plus{}1)^3 \equiv (k\plus{}1)^3 \equiv 1 \mod 5 \Longrightarrow k\equiv 0 mod 5$ or $ k^3 \plus{} 3k^2 \plus{} 3 \equiv 0 \mod 5$

Now if $ k^3 \plus{} 3k^2 \plus{} 3 \equiv 0 \mod 5$, then $ k(k\plus{}3) \equiv 2 \mod 5$ Which implies either $ k\equiv (1,2) \mod 5$ and $ k\plus{}3\equiv (1,2) \mod 5$ but this is impossible so the only possibility is $ k\equiv 0 mod 5$

From here we get $ n\equal{}30c\plus{}1$

[color=#666666]Hi........[/color]

Excuse me "dgreenb801" :blush:
my answer is $ 30x\plus{}1$ too because 2nd and 4th $ IF$ in my solution hasn't answer(no exist $ n$ that $ 5|n^2\plus{}n\plus{}1$). and answer of 3rd $ IF$ in my solution is $ 60l\plus{}31$. therefore(1st & 3rd $ IF$)  total answer is $ 30x\plus{}1$.
if U continue my solution you arrive this answer too.

[color=#666666]By.........[/color]

But why do you have to keep substituing back in so many times? Can't we just put several restrictions on n as I did using modular arithmetic, then we find n-1 has to be divisible by 2,3, and 5, so n=30k+1 which checks? We have proved no other solution can work using modular arithmetic, for n must be odd for $ n^2 \equiv 1 \pmod 4$ and n must be 5c+1 for $ n^3 \equiv 1 \pmod 5$?


function
search
algebra unsolved
algebra

Find all $ f: \mathbb{R} \to \mathbb{R}$ that \[ f(x\plus{}y)  f(x\minus{}y) \equal{} f(x^2) \minus{} f(y^2) \quad \forall x,y \in \mathbb{R}\]


inequalities
logarithms
function
integration
calculus
calculus computations

Prove the following inequality.

\[ \sum_{k=1}^{1003} \frac{1}{k}<\ln 2007. \]

Lemma: if $f$ is a convex function on the interval $(a-b,a+b)$, then $\int_{a-b}^{a+b}f(x)\,dx\ge 2bf(a).$

(Note: what I'm calling a "convex" function is what a typical American calculus textbook calls "concave up." I strongly urge anyone trying to understand the following proof to draw the graphs,)

Let $y=L(x)$ be the equation for the tangent line to the graph of $y=f(x)$ at the point $x=a.$ Hence $L(x)=f(a)+m(x-a)$ where $m=f'(a).$

Then $\int_{a-b}^{a+b}f(x)\,dx\ge\int_{a-b}^{a+b}L(x)\,dx$

$=\int_{a-b}^{a+b}f(a)+m(x-a)\,dx=2bf(a).$

Furthermore, if the function is strictly convex, this is a strict inequality.

(Note: this lemma is just a special case of Jensen's inequality, and I have reconstructed the proof of Jensen.)

Then:

$\ln(2007)=\int_1^{2007}\frac{dx}x=\sum_{k=1}^{1003} \int_{2k-1}^{2k+1}\frac{dx}x >\sum_{k=1}^{1003}2\cdot\frac1{2k}= \sum_{k=1}^{1003}\frac1k.$

I think in your last two sums you meant the upper limit to be 1003.
[color=blue]Of course. Thanks. -K.M.[/color]
It is quite nice though otherwise!  :D

Essentially what we did here was to approximate the integral $\int_1^{2007}\frac{dx}x$ by the midpoint Riemann sums using $\Delta x=2.$

For functions whose concavity has constant sign, the midpoint Riemann sums lie on one side of the integral and the trapezoidal rule estimates lie on the other side. We can find several closely related estimates using the trapezoidal rule. Here's one:

$\sum_{k=1}^{1003}\frac1k>\ln(1003)+\frac1{2006}.$

Summation from k = 1 to 10 of 1/k added to the
Integral from k = 9.5 to 1003.5 of (1/k)dk < ln(2007)


What is the ratio of the area of a square that circumscribes a circle to the area of a square that inscribes the same circle?

Hint:[hide]Try drawing the picture and rotating the smaller square[/hide]

Hint: [hide] Think about how you can relate the radius of the circle to either squares.[/hide]

Why do you think it's [hide]2:1[/hide] JS1527?

Well, [hide] you draw it out.  The side length of the outside square is 2r, so the area is 4r^2.  For the inside square, the radius forms 1/2 of a diagonal of the square.  So its a 45-45-90 triangle.  The length of the side is ( :rt2: *r), so the area is 2r^2.  4r^2/2r^2 = 2:1. [/hide]

JMI wrote:Hint:[hide]What I meant before is if you rotate the inscribed square it will have its vertices on the midpoints of the circumscribed square.[/hide]

But... what does that do?

It is just a different way to do the problem.

[hide]I did something like this a long time ago. The ratio of the area of an circumscribed regular n-gon to the area of an inscribed regular n-gon is csc :^2: ( :theta: ) where  :theta: is the half angle which is 180(n-2)/(2n).[/hide]

Big spoiler there.

[hide]What I meant is that if it is circumscribed, then the radius equals half of the diagonal of the square, if it is inscribed, then the radius equals half the length of one of the sides.[/hide]

Duck-Billed Platypus wrote:[hide]Let radius of circle equal 1. Diagonal of smaller square is 2, so 1 side of the smaller circle is  :rt2: . This makes the area of the smaller square 2.

If radius of circle is 1, then height/width of bigger square is 2, which makes the area of the bigger square 4.

So the ration is 2:1.[/hide]

BEST.DRAWING.EVAR.

[quote="blahblahblah"]BEST.DRAWING.EVAR.[/quote]
You're kidding, right?

[quote="tokenadult"]I appreciated Duck Billed Platypus's drawing. For anyone who is using Microsoft Paint to do a drawing, here is a tip: if you hold down the shift key while using the line drawing tool, the program will align the line with the grid, making the line straight. That works for horizontal and vertical lines, and lines at 45 degrees to those alignments are made as straight as possible given pixel approximation. Cool.[/quote]

That's why everyone needs Geometer's Sketchpad. It's very easy for all sorts of drawings and calculations. It's not that expensive (I got it for $35) and it's [i]very[/i] useful.

[quote="Yasha"]That's why everyone needs Geometer's Sketchpad. It's very easy for all sorts of drawings and calculations. It's not that expensive (I got it for $35) and it's [i]very[/i] useful.[/quote]

I've had Geometer's Sketchpad for more than three years now, and have upgraded to the latest release of the latest version. One thing I'm still wondering about, however, is what the most trouble-free steps are for getting a diagram drawn in Geometer's Sketchpad saved in a format that is compatible for uploading to this forum. I must have gone off on a wrong direction the last time I tried that, because I ended up using Microsoft Paint, which I could more reliably force to save in the appropriate file format. Did I forget about an export command, or what other step did I miss? I have all the usual Microsoft Windoze programs for image file conversions, but nothing fancy on my computer by way of image software.

As a general word of thanks to several participants, I'd like to say that the recent posts in several threads here on Getting Started have been [b]excellent[/b] examples of you young learners helping one another and practicing doing mathematics more rigorously. Keep up the good work.

The way I'd go about posting a .gsp file is using the print screen key and then pasting the screen into paint. Then I'd crop it and save it as an image file. Some other people have posted .gsp documents such as [url=http://www.artofproblemsolving.com/Forum/viewtopic.php?t=13206&postdays=0&postorder=asc&&start=10]this one here[/url] and so they might have a better way of doing this.

Selecting the relevant pieces and pasting into Paint to save as a bmp, jpeg, or gif works very nicely and is what I have done.

I always was thinking there was a simpler way. Argh!


Chlorine in swimmming pools is provided in the form of aqueous solution of hypochlorous acid in equilibrium with its salt as:
HClO <--> H+ + ClO- (yea.. I really gotta learn how to use latex)
The electrically neutral molecule HClO is able to pass through bacterial membranes more easily than the charged ClO- ion and is about 80x more effective at killing bacteria. Thus the pH control is very important. What pH would be required in the pool so that 88%  of the molecules are in the form HClO?

I haven't taken chemistry in over a year but if I remember, you need to use ICE as we called it, which is I believe initial, change, and equilibrium.  Then you need to use the formula for pH.

Ive tried a few methods including henderson hasslebach, but my values are a bit low.

Oh did I forget to mention  that????

Lol... silly me...
its 3E-8

$ [\mathrm{HA}] \equal{} 0.88$
$ [\mathrm{A^ \minus{} }] \equal{} 0.12$
$ \mathrm{pK_a} \equal{} \minus{} \log 3\times10^{ \minus{} 8}$

Henderson-Hasselbalch:

$ \mathrm{pH} \equal{} \mathrm{pK_a} \plus{} \log \frac {[\mathrm{A^ \minus{} }]}{[\mathrm{HA}]}$

plugging everything in,

pH = 6.66

@jdlkem: but why is concentration of the conjugate base .12? I agree that .88 is teh concentration of the acid, but the conjugate base of HClO should be ClO-, and if theres 88 molecules of HClO, then in every 100 molecules, 12 are NOT HClO, That means that 6 of them should be H and 6 should be ClO-. Can u explain the fault in my logic?

Every 100 molecules of what?  When the problem talks about "88% of the molecules" it means "88% of the molecules that contain chloride."  The hydrogen isn't included.

$ HClO \rightleftarrows H^\plus{} \plus{} ClO^\minus{}$
So, if we dissolve 1 mol of HClO in 1 L solution,
1 M = [HClO] + [ClO-]
= [HClO] + [H+] - 10^-7

So, from 100 molecules of HClO, 88 molecules should be of the form HClO and 12 should be of the form ClO-

The relevant equilibrium is

$ \ce{HClO} \plus{} \ce{H2O} \rightleftharpoons \ce{ClO\minus{}} \plus{} \ce{H3O\plus{}}$

and if the initial concentration of hypochlorous acid in the pool is $ C_i$ then at equilibrium we will have

$ [\ce{HClO}] \equal{} 0.88C_i$
$ [\ce{ClO\minus{}}] \equal{} 0.12C_i$.

Therefore,

$ K_a \equal{} \frac{0.12C_i \cdot [\ce{H3O\plus{}}]}{0.88C_i} \equal{}> [\ce{H3O\plus{}}] \equal{} 7.33K_a \equal{} 2.2 \times 10^{\minus{}7}$

and pH = 6.66.

As a quick technical note, realize that we are implicitly assuming that the $ \ce{HClO}$/$ \ce{ClO\minus{}}$ system is present in significant concentrations.  Otherwise, you would also need to take the equilibrium $ \ce{2H2O <\equal{}> H3O^\plus{}} \plus{} \ce{OH\minus{}}$ into account.  This is a reasonable assumption based on the problem context (if you want to kill some bacteria, trace amounts aren't going to do too much), but something worth thinking about regardless.


Assume that $m$ and $n$ are relatively prime. Place the rectangle of dimension $mxn$ in a Cartesian coordinate system with the lower left corner in $O=(0,0)$ and the upper right corner in $P=(m,n$). Then the straight line segment $OP$, which is a part of the line $y = nx/m$, intersects no lattice point (i.e. a point with integer coordinates) because $m$ and $n$ are coprimes. Moving a point along $OP$ from $O$ to $P$, we observe that every time this point either passes through a vertical line $x=i \; (i \in {\bf N} \;\; \& \;\; 0<i<m)$ or horisontal line $y=j \; (i \in {\bf N} \;\; \& \;\;0 < j < n)$, the point is leaving one unit square and entering another. Hence on this point's "journey" from $O$ to $P$ it passes through $1 + (m - 1) + (n - 1) = m + n - 1$ unit squares.

Using this fact it is fairly easy to show if $gcd(m,n) = d$, then the answer to this question is $m + n - d$.

[quote="numbergeek"]Consider a grid having 13 columns and 5 rows consisting of squares of 1 unit.

This figure would be a rectangle. If a diagonal is drawn from lower left corner to upper right corner then how many unit squares would be cut.

PS - There can be a generalized formula made for a rectangle of a rows and b cols if a and b are prime. If someone can derive that formula he would be of great help.
Though I solved it by a different and lengthier method.[/quote]

I had this problem, but with different numbers, in an Olympiad! It was with a rectangle of $120*144$. I'll post a hint to the generalization: [hide="hint"]Try to reduce the problem to the minimum congruent triangle (congruent to half the original rectangle)with integrer legs[/hide]

Basically what Solar Plexsus said:
[hide] Principle of Inclusion-Exclusion: $13+5-gcf(13,5)=18-1=\boxed{17}$ [/hide]

[hide]By using the Principle of Inclusion-Exclusion, we get the answer to be

$13+5-gcd(13,5)=17$[/hide]


topology
real analysis
real analysis unsolved

How to show that in $A\subset\mathbb{R}^{n}$ is measurable and $\epsilon>0$ arbitrary, then
1. There exist open $G\supset A$ s.t. $m(G\setminus A)<\epsilon$?
2. There exist closed $F\subset A$ s.t. $m(A\setminus F)<\epsilon$?
3. If $m(A)<\infty$, there exist compact $G\subset A$ s.t. $m(A\setminus G)<\epsilon$?

A stupid mistake. Of course it should be "if $A\subset \mathbb{R}^{n}$ is measurable". I used this to prove Lusin's theorem so I'm looking a proof which do not use Lusin's theorem.

Lemma. If $m$ is a finite Borel measure on a metric space $X$ then for every Borel set $B$ and $\epsilon>0$ there are open $G$ containing $B$ and closed $F$ contained in $B$ such that $m(G\setminus F) < \epsilon$.

Sketch the proof: Consider a family of all Borel sets that can be approximated in this way; show that this family is a $\sigma$-algebra, and contains all open sets.

From lemma you will get 1 easily by using it to the $B \cap (-k,k)^{n}$ for fixed $k$ (to have a finite measure). Then 1 gives 2; 3 follows by the remark that in an Euclidean space compact sets are exactly those which are both closed and bounded.


Hi.  I'm a newcomer to this forum and I'm currently in high school.  The ppl in my school are good at maths but some ppl here just leave me awestruck at their skill. (probably because I was never exposed to maths forums   :lol: ).

I would like to know how do you all hone your maths skills?  (Not just for competitions)?  Are there any books, resources etc that are really useful?  Please recommend them.  Thanks

I don't know if you already have them but the AoPS books are actually good for just math skills too.


group theory
abstract algebra
superior algebra
superior algebra solved

Find all groups with 30 elements and 8 automorphisms.

It isn't that hard and I think it's not very ugly.

I think G should be cyclic:

Let M be the set of all conjugation automorphisms of G; M={fg:G->G | fg(x)=gxg-1 for all x in G}. It's easy to see that (M,o) is a subgroup of (Aut(G),o), so |M| | |Aut(G)|=8, so |M| is 1, 2, 4, or 8. At the same time, we can easily prove that |M|*|Z(G)|=|G|, so |M| is either 1 or 2. We thus have 2 cases:

Case 1: |M|=2=>|Z(G)|=15. We can see that there are elements x of order 15 and a of order 2 s.t. G=<x> \cup a*<x>. We obviously have more than 8 automorphisms in this case, so the only remaining case is

Case 2: |M|=1=>|Z(G)|=30=>G is commutative, so we have an element of order 30 (there are elements x, y, z of orders 2,3,5 respectively, so xyz has order 30 because G is commutative), so G is cyclic. It's easy to prove that there are exactly 8 automorphisms in this case, because phi(30)=8, so for an element a of order 30, we have the automorphisms of the form f(a)=ak for all k s.t. (k,30)=1, and we have exactly 8=phi(30) such k.

Yeah, this is the easiest solution. Mine solution was:
   Usind that Aut(G) is a group we find easily that x^8 is in Z(G) for all x. Since x^30=e is in Z(G), we have x^2 in Z(G) for all x. Then use Cauchy to find an element a of order 3 and b of order 5. They belong to Z(G), so the subgroup generated by them is in Z(G). So, Z(G) has at least 15 elements, so it has 15 or 30. Suppose it has 15. Then G/Z(G) is cyclic, so G is abelian, false. Thus Z(G) has 30 elements and G is abelian.Since |G| is free of squares and G is abelian, G is cyclic and we're done.

My solution isn't really complete. We need some justification for the fact that there are more than 8 automorphisms in Case 1:

We can take all isomorphisms of the form f(x)=xk with (k,15)=1 and f(a)=a (it's defined for all the other elements). We have 8 such isomorphisms. Then we can take f(x)=x and f(a)=ax so we have at least an isomorphism besides the 8 already mentioned.


Find the least positive integer $ m$ such that for some prime number $ p$, $ 7^{p}+3^{p}+m$ can be a perfect square.

[hide]The answer might be $ m=6$ for $ p=2$.[/hide]

[quote="zhaoli"]Find the least positive integer $ m$ such that for some prime number $ p$, $ 7^{p}+3^{p}+m$ can be a perfect square.[/quote]
It's almost the same as the one [url=http://www.mathlinks.ro/Forum/viewtopic.php?t=155860]in the link[/url] (and actually easier).


function
calculus
derivative
algebra
polynomial
LaTeX
analytic geometry

OK, that way. Maybe someone could verify these results have a found. Personally i don't believe my text book is explaining every aspect of diffentiation. Quite a lot tasks, hope you don't mind:

1) $f(x)=\frac{1}{3}x^3 \implies f'(x)=3x^2$

2) $f(x)=\frac{1}{x^2} \implies f'(x)=-\frac{2x}{x^4}$

3) $f(x)=\frac{x^2-x-2}{x} \implies f'(x)=1+\frac{2}{x^2}$

4) $f(u)=\frac{12u^2+3x-8}{3u} \implies f'(u)=4+\frac{8}{3u^2}$

5) $f(t)=\frac{\sqrt{t}}{t-1} \implies f'(t)=-\frac\frac{1}{2\sqrt{x}}{t-1}^2$

6) $f(x)=\frac{(x+1)(1-x^2)}{3+x^3} \implies f'(x)=\frac{2x-1}{3x^2}$

7) $f(x)=x^4\sqrt{x} \implies f'(x)=4x^3\frac{1}{2\sqrt{x}}$

8) $f(x)=x^3+3x^5 \implies f'(x)=3x^2+15x^4$

9) $f(x)=\frac{3}{x} \implies f'(x)=-\frac{3}{x^2}$

10) $f(x)=x^5-5x^2+\frac{1}{x} \implies f'(x)=5x^4-10x-\frac{1}{x^2}$

11) $f(x)=\frac{x^5}{5}-\frac{1}{2}*x^-1 \implies f'(x)=x^4+\frac{0,5}{x^2}$

12) $f(x)=3\sqrt{x}-x^-1 \implies f'(x)=\frac{3}{2\sqrt{x}}+\frac{1}{x^2}$

Hope i didn't write something wrong :)

Plz reply if i have done something wrong (which i believe i have done at least one time) or if you think i could shorten it further.

Well, let's see.

1) is wrong because you forgot the factor $1/3$.
2),3) are fine.
4) is unclear: what is $x$ in the definition of $f(u)$?
5) is also strange: what is $x$ in the expression for $f'(t)$?
6) is wrong
7) is wrong (the derivative of the product is NOT the product of the derivatives)
8)-12) seem OK (I hope that $x^-1$ is meant to be $x^{-1}$)

As far as I can see you still have trouble with the product and the quotient rules (and, perhaps, are still not very comfortable with $\LaTeX$ :))

1) $f'(x)=x^2$

4) I now see the problem, here is the right one:
$f(u)=\frac{12u^2+3u-8}{3u} \implies f'(u)=4+\frac{8}{3u^2}$

5) This was a $\LaTeX$ problem. Let's try and see if i can do it right this time:
$f(t)=\frac{\sqrt{t}}{t-1} \implies f'(t)=-\frac{\frac{1}{2\sqrt{t}}}{(t-1)^2}$

6) Maybe i should have stopped sooner. I have this:

$f(x)=\frac{(x+1)(1-x^2)}{3+x^3} \implies f'(x)=\frac{1-3x^2-2x}{3x^2}$

Can it be squished smaller than this? I was thinking about the $3x^2$ both above and below the fraction line. Should i just ignore that or can i do something about it?

7) English is not my main language. Could you explain and maybe show me how you would do it? Took a look at it, but could not see what was wrong.

$f(x)=x^4*\sqrt{x} \implies f'(x)=4x^3\frac{1}{2\sqrt{x}} \implies f'(x)=\frac{4x^3}{2\sqrt{x}}$

Note: There's a $x^4*\sqrt{x}$, not the 4th sqrt.. (how do you write this BTW?)

11) Yes, it is $x^{-1}$

And can you help me with this one, let's call it 13):

13) $h(x)=\frac{x-1}{x+1}$

I get:

$h'(x)=\frac{0}{(x+1)^2}$

But i have a feeling this isn't right.

You seem to believe that $(f/g)'=f'/g'$ and $(fg)'=f'g'$ (see 5,6,7) Meanwhile, the truth is more complicated: $(f/g)'=\frac{f'g-g'f}{g^2}$ and $(fg)'=f'g+fg'$. So, for example,
$(x^4\sqrt x)'=(x^4)'\sqrt x+x^4(\sqrt x)'=4x^3\sqrt x+x^4\frac 1{2\sqrt x}$, which, of course, can be simplified to $\frac 92 x^3\sqrt x$.

Well, i do know about the $(f*g)'$ and the $(f/g)'$, but i guess i just forget about it too often - i'm pretty new into this differentiate chapter.

Could you show me step by step how you simplify this:

$4x^3\sqrt x+x^4\frac 1{2\sqrt x} \implies \frac92x^3\sqrt x$

This is just elementary algebra. Note that the second term equals $\frac 12\frac{x^4}{\sqrt x}=\frac 12 \frac{x^3\cdot\sqrt x\cdot\sqrt x}{\sqrt x}=\frac 12 x^3\sqrt x$. Now $4x^3\sqrt x+\frac 12 x^3\sqrt x=\left(4+\frac 12\right)x^3\sqrt x=\left(\frac 82+\frac 12\right)x^3\sqrt x=\frac 92x^3\sqrt x$

The first step is fine but then you made some mistake(s) in algebra, so the final line is wrong...

Your line 2 is correct. Your third line should be
$g'(x)=\frac{12x^9+24x^2-4x-8x^{-6}-8x^9-8x+12x^2+12x^{-6}}{(2x^4+4x^{-3})^2}$

The mistakes: $x^{-3}x^{-3}=x^{-6}$, not $x^0$, and $x^{-4}x^{-2}=x^{-6}$, not $x^{-2}$.
Also, you made a sign mistake in the subtraction.

How could i not see those errors, my bad :o  But: $-12x^{-4}(x^6+x^{-2})=-12x^2-12x^{-6}$, i don't see why this one is wrong.

One computational possibility: the original function could have been written as

$g(x)=\frac{x^9+x}{2x^7+4}$

The derivative is still messy, but you may be able to keep your footing a little better.

How do you conclude that? I can see it is true when you put in a number for $x$ in the whole equation, but it doesn't work when i put it into only the function above the fraction line.

Do you have any idea how it can be this is not true in case you agree Jmerry?
$-12x^{-4}(x^6+x^{-2})=-12x^2-12x^{-6}$

That subtraction is wrong because it should be $+12x^{-4}(x^6+x^{-2})$. There are two negative signs, and a double negative is a positive in mathematics.

Ah, now i see it, you mean from outside the brackets.

So here's the result now, took some time, but it was really learning, indeed:

$g'(x)=\frac{4x^9+36x^2-12x+4x^{-6}}{(2x^4+4x^{-3})^2}$

OK, hope it is right now. I believe it isn't quite possible (or at least very hard) to minimize it further than this. Thx to everybody who helped me ;)

One could also see possibly writing the answer as

$g'(x)=\frac{4x^{15}+36x^8-12x^7+4}{(2x^7+4)^2}$

What's a "simple form"? A possible meta-rule: whatever form makes it easiest to perform the next step. One possible next step after the finding of the derivative: can we locate the critical points of the original function? In this case those would be the roots of a 15th degree polynomial, which isn't a very nice answer, but at least we can see that it isn't a very nice answer.

Of course, not! :o What Kent meant is that if you multiply the numerator and the denominator in your expression by $x^6$ (which changes both the numerator and the denominator, but doesn't change the fraction), you'll get his formula.

Oh ok, that way. I see what you mean now :)

for number 1, im not sure if this is what you're looking for...

$f(x) = \frac{1}{3}x^3$ implies $f'(x) = x^2$
i'll make it $g(x) = cx^n$
$\frac{d}{dx}[c*g(x)] = c\frac{d}{dx}[g(x)]$
so i'll leave it out
$g'(x) = lim_{h\to0} \frac{g(x+h) - g(x)}{h}$
$g'(x) = lim_{h\to0} \frac{(x+h)^n - x^n}{h}$

im gonna expand the $(x+h)^n$, the first term will be x^n, the next term will be $nx^{n-1}h$.  thats hard to explain, but if you look at the ____ triangle (i forget the guy's name), the second number of each line will always be n, also the binomail theorem i think the name is will show it, but i can only get it with the taylor series which defeats the purpose of trying to show why its true.  all the rest of the terms will include an h to a power of 2 or greater.

$g'(x) = lim_{h\to0} \frac{x^n +nx^{n-1}h + ... - x^n}{h}$
$g'(x) = lim_{h\to0} \frac{nx^{n-1}h + ... }{h}$
$g'(x) = lim_{h\to0}nx^{n-1} + ...$

note, all the terms denoted with the ... contain an h, so as h approaches zero they'll disappear

$g'(x) = nx^{n-1}$
$\frac{d}{dx}[\frac{1}{3}x^3] = x^2$

[quote]i don't believe my text book is explaining every aspect of diffentiation[/quote]
im not sure how bad it is so:
$\frac{d}{dx}[c*g(x)] = lim_{h\to0}\frac{c*g(x+h) - c*g(x)}{h}$
$= lim_{h\to0}\frac{c*[g(x+h) - g(x)]}{h}$
$= lim_{h\to0}[c] * lim_{h\to0}[\frac{g(x+h) - g(x)}{h}]$
$= c * lim_{h\to0}[\frac{g(x+h) - g(x)}{h}]$
$= c\frac{d}{dx}[g(x)]$

Thx for the help, but this part wasn't where my textbook didn't tell me what to do. But let me give you just another example of the kind of problems i get that the textbook doesn't explain what to do with.

$f(x)=x^2$ and $g(x)=x^3$ intersect in the spot $(1,1)$. Find the angle between the two tangents in this spot.

First of i diffentiate it and find that:

$f'(x)=2x$

and

$g'(x)=3x$

But how can i find the angle between them? This is exactly where my textbook doesn't tell me what to do, but i still gives me these kind of tasks.

Well, you have two lines with the slopes $f'(1)=2$ and $g'(1)=3$. Recall that the slope of a line is just the tangent of the angle the line makes with the $x$-axis. Thus, the answer is $\arctan 3-\arctan 2$.

And what does this $arc$ in $arctan(3)$ mean. How do i drop it into my calculator and what is the final result.

PS. I have a TI-84 plus...

If i only put in the numbers in $tan$ i get the result $0.1749$, but if i use the $tan^{-1}$ i get $8.1301$.

$\arctan$ is one of the standard notations for the inverse function to $\tan$; another common notation for the same function is $\tan^{-1}$ (the latter is what they usually write on calculator buttons because it takes less space) $\text{arc}$ in $\arctan$, probably, means "the arc whose $\tan$ is... " but I'm not 100% sure about this. So, out of your two numbers, the second one is correct. Note that it is given in degrees (that's, probably, how your calculator is set to show angles). If you want it in radians, you should multiply it by $\frac{\pi}{180}$.

Degree is my prefered tool. It just sounded as a quite small angle, but i tried doing a $tan^{-1}(1)$ and it said $45$. I was pretty sure the angle between $x=0$ and $f'(x)=1$ was suppose to be $45$. So i think i've got the point on this subject now. Thx...

It does appear you know the chain rule. On the other hand, your notation is dangerous- the second line of each calculation is false.

Also, remember that $ab^2$ is not equal to $(ab)^2$; your algebra in the last step of each calculation is wrong. You're off by a factor of 15 in the first, and a factor of $27x-12$ in the second.

$15(5x+2)^2$

$(27x^2-12)(3x^3-4x+1)^2$

You want me to stop here?

If you don't mind i would like to see how you would do them. The text book only shows me one example. I don't think i see the problem with the second lines. But i believe you were referring to the bottom of each task when you said $ab^2$ is not $(ab)^2$. Hope you will go through it today (when it is daytime in the US) since i can't continue my studies before i've got this right. So if you give me the complete walkthough i should be able to do the next handful of more or less simular tasks and thereby not being stuck here. Thx...

No. You're trying to differentiate a product- use the product rule.

I need a tutor, i really need a tutor :( OK, here is what i got now (again i blame the textbook not to give me an example of how to do this type of diffentiation). If this is not right, could you plz post the entire walkthrough of the diffentiation so i can be sure to have the result at latest tomorrow and thereby also have an example to go back to whenever i see a simular problem ... I have quite a lot to do before i go to the university this summer and i don't have time to skip work for a day and do it another day.. thx.

$f*g=x^2*(x^3-x)^5$

$(f*g)'=(x^2)'*(x^3-x)^5+((x^3-x)^5)'*x^2$

$(f*g)'=2x*(x^3-x)^5+(5(x^3-x)^4*3x^2-1)*x^2$

$(f*g)'=2x*(x^3-x)^5+x^2*(15x^2-5)(x^3-x)^4$


Good luck guys!    :D

Show some Canadian pride, lol.   :moose:  :nhl:

I voted for six.  That would guarantee that... ;)

Heh. I vote for 5, Elyot. I'm having a hard time seeing this one particular IMO member getting a gold medal  ;)

[quote="billzhao"]The team should remain undisclosed until the official media release (probably by next week). The topic will be locked until then.[/quote]
I am really sorry. My principal made an announcement on last Thurday, which included the fact that I'm on IMO team.  I assumed official media release went as CMS previously planned(which was last Thursday or Friday). Good thing that I mentioned nothing about team members.

I don't know who the team is, but it seems reasonable that past performers Yufei Zhao, Peng Shi, and David Rhee will be on the team.

Saying that, I doubt that any of the 'new comers' will get any gold. [color=red][Edited by mod][/color]

[quote="Sunny"][quote="Singular"]I don't know who the team is, but it seems reasonable that past performers Yufei Zhao, Peng Shi, and David Rhee will be on the team.

Saying that, I doubt that any of the 'new comers' will get any gold.[/quote]

Oh i dunno...have some faith in the newcomers, they may surprise you.[/quote]
I agree. Some of them did better than me in many competitions.

I speculate this year's ranking of countries as:

1st China
2nd US
3rd Russia
4th Romania/Bulgaria
.
.
.
.
.
Canada would probably in 10 to 12

[quote="lightrhee"]Currently, 50% of the people think that we would win two gold medals. Interesting...[/quote]

I don't. I think the team can only get one realistically; mine will have to be made out of Aero wrappers  :lol:

[quote="billzhao"]mine will have to be made out of Aero wrappers  :lol:[/quote]
That's what I did last year, just to see Dr. Small eating steak :rotfl: .

Just to remind everyone that this poll is still going on.
Sorry for this double post, but I can't remind people if I just edit my previous post.

Thinking theoritically, countries continue to progress in mathematics. This most likely hints that the IMO will become harder and harder.  :idea:  Now that I think about the situation more thoroughly, 2 Gold Medals are a high standard.  :( But good luck anyway... maybe something miracuolous will happen.  :lol:

P.S. this is just my thinking... not everyone probably agrees...  :roll:

Of course, the number of golds, silvers, and bronzes is fixed as a proportion of the number of contestants...

[quote="d.lam.86"]Thinking theoritically, countries continue to progress in mathematics. This most likely hints that the IMO will become harder and harder.  [/quote]

I don't think so. Most team leaders agreed that it should remain a competition with reasonable difficulty level. The most important content should be the fun of solving problems, not for the sake of hard problems only. Thus problems with non-standard solutions should be proposed to IMO such that countries with a low level training don't face too many disadvantages, e.g. people with a high standard of creativity should win and not necessarily those who solved thousands of problems. What is the point of using intractable problems? It is still a high-school olympiad and many contestants are not elder than 15-17. I know Germans are different...  :D


[quote="hollandman"]Let $ k$ be a fixed positive integer. Consider the sequence defined by
\[ a_{0} \equal{} 1 \;\; , a_{n \plus{} 1} \equal{} a_{n} \plus{} \left[\root k \of{a_{n}}\right] \;\; , n \equal{} 0,1,\cdots
\]
where $ [x]$ denotes the greatest integer less than or equal to $ x$. For each $ k$ find the set $ A_{k}$ containing all integer values of the sequence $ (\sqrt [k]{a_{n}})_{n\geq 0}$.[/quote]
$ k\minus{} fixed$, therefore I denote $ A_{i(l)}\equal{}m(l)^k.$
Obviosly $ i(0)\equal{}1,m(0)\equal{}1,i(1)\equal{}2^k\minus{}1,m(1)\equal{}2$.
If $ a_n\equal{}m^k\plus{}b_m,b_m<m$, then $ a_{n\plus{}r}\equal{}(m\plus{}1)^k\plus{}b_m\minus{}1$, were $ r\equal{}\frac{(m\plus{}1)^k\minus{}m^k\minus{}1}{m}$.
It give \[ a_{i(l)}\equal{}m(l)^k,a_{i(l)\plus{}1\plus{}((m(l)\plus{}1)^k\minus{}1\minus{}m(l)^k)/m}\equal{}(m(l)\plus{}1)^k,...,\]
$ a_{i(l\plus{}1)}\equal{}m(l\plus{}1)^k,m(l\plus{}1)\equal{}m(l)\plus{}m(l)\equal{}2^l$.
It mean all integer values $ \sqrt[k]{a_n}$ are $ 2^l,l\equal{}0,1,...$


Define a a sequence $ {<{a_n}>}^{\infty}_{n\equal{}1}$ as follows

$ a_n\equal{}0$, if number of positive divisors of $ n$ is  [i]odd[/i]
$ a_n\equal{}1$, if number of positive divisors of $ n$ is [i]even[/i]

(The positive divisors of $ n$ include $ 1$ as well as $ n$.)Let $ x\equal{}0.a_1a_2a_3........$ be the real number whose decimal expansion contains $ a_n$ in the $ n$-th place,$ n\geq1$.Determine,with proof,whether $ x$ is rational or irrational.

Answer is irrational.

$ a_n\equal{}0$ if and only if $ n$ is perfect square.
Suppose the number is rational, then its decimal expansion is periodic. Say, $ p$ is the period. Then for large $ n$, we have
$ a_{n\plus{}p}\equal{}a_n$. But if we try $ n\equal{}p^{2m}$ for big $ m$. We see $ a_{n\plus{}p}\equal{}1$, $ a_n\equal{}0$. Contradiction!

Well !!
Even I followed the Same Approach. One could easily think of this logic !
 :)

OMG! U used prime number theorem. I don't know if they expected anyone to know and use this theorem for a INMO problem.  :D Anyway how did u prove the fact that there is no regularity in the sequence.

Skand has a solution using Dirichlets theorem. Could u please explain your method.

Well gautam's argument was the [i]obvious[/i] argument and i have used the same but it lacks rigour.

i very well recognise lack of rigour in my proof but i had no option. indeed i should have proved my result on spacing between enevenly distributed primes from prime number theorem with rigour. but , that would require atleast 2.5 - 3 pages when i had only one page left in my answer booklet. authorities at my centre were not providing xtra sheets.

[quote="gautam.a"]indeed i should have proved my result on spacing between enevenly distributed primes from prime number theorem with rigour. but , that would require atleast 2.5 - 3 pages when i had only one page left in my answer booklet.[/quote]
[quote="Fermat"]I have a truly marvellous proof of this proposition which this margin is too narrow to contain.[/quote]

Try the following sequence:

$ a_n = \{\begin{array}{l} 1 \text{ if } n \le 6 \\
1 \text{ if } n \equiv \pm 1 \text{ mod } 6 \\
0 \text{ in the other cases} \end{array} $

The number $ 0.a_1a_2...$ is rational, but we have $ a_p = 1$ for every prime $ p$.

friend, it seems that you did not see the question prperly which came in our Indian National Mathematics Olympiad, we very well know that fixed modulos shall make such sequences periodic but in the question there was nothing such as fixed modulos. my result on eneven prime distribution causing irrationality was case specifique and is not a universal result. notice one thing that in the original question, the function aquires one only when n is a perfecr square.

[quote="Agr_94_Math"]The proof must be written very strongly. So it would be nice if someone writes a very very detailed and rigorous proof for this.[/quote]
I'll do that then :)
[color=darkred][b]Lemma 1:[/b][/color] $ a_n \equal{} 0$ if and only if $ n$ is a perfect square. Otherewise we have $ a_n \equal{} 1$.

[color=darkblue][b]Proof:[/b][/color] Write $ n$ as it's primefactorisation: $ n \equal{} p_1^{a_1}...p_r^{a_r}$ where $ p_i$ are distinct primes and $ a_i \in \mathbb{Z}$. Then it is generally known that the number of divisors of $ n$ is exactly $ (a_1\plus{}1)...(a_r\plus{}1)$. This is obviously odd if and only if $ 2 \mid a_1,a_2,...,a_r$ or equivalently: $ n$ is a perfect square.

[color=darkred][b]Lemma 2:[/b][/color] A number $ m \equal{} 0.b_1b_2b_3.....$ is rational only if the sequence $ b_1,b_2,b_3,...$ is periodic.

[color=darkblue][b]Proof: [/b][/color] Equivalently we just need to prove that every rational number $ x \equal{} 0.c_1c_2c_3....$ has a periodic decimal representation. Let $ x \equal{} \frac{p}{q}$ where $ (p,q) \equal{} 1$, $ q > p > 0$. First I'll mention that $ \exists r,s \in \mathbb{Z}$ such that $ q \mid 10^s(10^r \minus{} 1)$. Let $ s \equal{} max \{ e_2(q), e_5(q) \}$. (Definition: $ e_p(n)$ is the maximal exponent of $ p$ which divides $ n$) Then let $ g \equal{} \frac{q}{2^{e_2(q)}5^{e_5(q)}}$, so we have $ q \mid 10^s(10^r\minus{}1) \iff g \mid 10^r \minus{} 1$. Now just choose $ r \equal{} \phi (g)$. So there $ \exists r,s \in \mathbb{Z}$ such that $ q \mid 10^s(10^r \minus{} 1)$. Then let $ k \equal{} \frac{10^s(10^r \minus{} 1)}{q}$. So $ x \equal{} \frac{p \cdot k}{q \cdot k}$. Now define the digits $ d_1,d_2,..,d_t$ of $ p \cdot k$ so that $ p \cdot k \equal{} d_1d_2....d_t$. Now $ x \equal{} \frac{p \cdot k}{q \cdot k} \equal{} \frac{d_1d_2...d_t}{99...99}$. With $ t$ $ 9's$. From here it is easy to see that $ x \equal{} 0.d_1d_2....d_td_1d_2...d_td_1d_2....$. And thus it has periodic decimal representation.

We want to prove that the number is irrational, and we prove the problem by the method of contradiction. Assume that the number is rational. By Lemma 2 we get that $ a_1,a_2,...$ is periodic. Let $ n$ be it's period. (That is $ a_k \equal{} a_{n\plus{}k} \forall k \in \mathbb{N}$) Now $ a_1 \equal{} 1$, so $ a_{kn\plus{}1} \equal{} 1$ for all $ k \in \mathbb{N}$ by induction. By Lemma 1 we know that $ 1,n\plus{}1,2n\plus{}1,3n\plus{}1,...$ are all squares. (It can be proved that this is impossible both by $ \bmod p$ for some prime $ (p,n)\equal{}1$. I will present a proof using inequalities) Let $ kn\plus{}1 \equal{} m^2 > n$ for some $ k$. Then $ (m\plus{}1)^2 \equal{} m^2 \plus{} 2m \plus{} 1 > m^2 \plus{} n \equal{} (k\plus{}1)n\plus{}1$. Then $ (k\plus{}1)n\plus{}1$ is between two squares, namely $ m^2$ and $ (m\plus{}1)^2$, and then it cannot be a square. Thus by Lemma 1 $ a_{(k\plus{}1)n\plus{}1} \equal{} 0$ and $ a_1,a_2,..$ is not periodic. Contradiction. And our assumption about the number being rational must be wrong. Thus the number is irrational!

[quote="Mathias_DK"]
[color=darkred][b]Lemma 2:[/b][/color] A number $ m \equal{} 0.b_1b_2b_3.....$ is rational only if the sequence $ b_1,b_2,b_3,...$ is periodic.
[/quote]

Is it that for some natural $ k$ the sequence $ b_k,b_{k\plus{}1},b_{k\plus{}2},...$ is periodic?

For example: $ 0.13333...\equal{}\frac{4}{30}\equal{}\frac{2}{15}$

[quote="mszew"][quote="Mathias_DK"]
[color=darkred][b]Lemma 2:[/b][/color] A number $ m \equal{} 0.b_1b_2b_3.....$ is rational only if the sequence $ b_1,b_2,b_3,...$ is periodic.
[/quote]

Is it that for some natural $ k$ the sequence $ b_k,b_{k \plus{} 1},b_{k \plus{} 2},...$ is periodic?

For example: $ 0.13333... \equal{} \frac {4}{30} \equal{} \frac {2}{15}$[/quote]
Thank you. I'll edit.

[quote="Mathias_DK"][color=darkred][b]Lemma 2:[/b][/color] A number $ m \equal{} 0.b_1b_2b_3...$ is rational only if the sequence $ b_1,b_2,b_3,...$ is periodic.

[color=darkblue][b]Proof: [/b][/color] Equivalently we just need to prove that every rational number $ x \equal{} 0.c_1c_2c_3....$ has a periodic decimal representation.[/quote]

I'm sorry, but it is completly false, you shall proof that $ x \equal{} a_0, a_1a_2\cdots \in Q \Rightarrow \exists k, p$ such as $ a_{k\plus{}a}\equal{}a_{k\plus{}a\plus{}p} \forall a\in Z_{\geq 0}$
And you afirm that it is equivalent to $ \exists k, p$ such as $ a_{k\plus{}a}\equal{}a_{k\plus{}a\plus{}p} \forall a\in Z_{\geq 0}\Rightarrow x\equal{}a_0, a_1a_2\cdots \in Q$.

Really we know that both is equivalent :D :D

I'm not shure that I was clear but I hope so...in the rest it is welll :D

[quote="gautam.a"]hi, i am a new user.
my soln to this was -
for all primes. the function is 1.
by prime number theorem( proved by selberg and erdos), we can eaily deduce that distance between 2 consecutive primes follow no arithmetic or otherwise patterns eventhough pi(x) / legendre's formula tends to 1 as x tends to infinity( however these two are never equal).
and,
if any number is distributed infinitely in any non regular fashion one cannot put other numbers   between such that a periodic sequence is formed, so although other numbers have our function = 1, we donot have any periodicity in distributed 1's and hence x is irrational.
pls comment.[/quote]
Isn't this solution wrong ? :wink:

I think that Kronecker's theorem kills it.

When there is an ant in front of you and you are puzzled to choose what should be used to kill it-atom bomb or gun? Then these type of mess is created.
              So, here is my most ordinary solution :-D
It is obvious that a(n) is 0 iff n is a perfect square. Now,if t is a natural no. the consider (t+1)^2-t^2=2t+1,which is not a constant one i.e, the difference b/w two consecutive squares is increasing in nature. So, x is not a periodic decimal fraction. Hence,x is irrational. :harhar:


calculus
integration
trigonometry
logarithms
calculus computations

Does the Riemann integral $\ds\int_{0}^{\infty}\frac{\sin x\,dx}{x+\ln x}$ converge? (A. Kukush)

See all the problems from [color=orange]Kyiv Mechmat Competition, 2007[/color] [url=http://www.mathlinks.ro/Forum/viewtopic.php?t=135749]here[/url]

More generally if $a>0$ then the integral

$\int_{0}^{\infty}\frac{\sin x}{(x+\ln x)^{a}}dx$ converges via the Dirichlet test.

Actually, it diverges because of the singularity at $\alpha$, where $\alpha e^{\alpha}=1$; there is one such point between zero and 1.

[quote="didilica"]You are right. What an elementary mistake   :oops:

$\int_{0}^{\infty}\frac{\sin x}{x+\ln x}dx=\int_{0}^{\beta}f(x)dx+\int_{\beta}^{\infty}f(x)dx$

where $\beta$ is the zeto of the denominator. The first integral diverges and the second one converges via Dirichlet test.[/quote]

What about $\int_{0}^{\infty}\frac{\sin x}{x}dx$ ? It's denominator is also zero but it converges to $\frac{\pi}{2}$ ... or I miss something?

The discontinuity there is removable, though, i.e. the limit still exists at $0$.

[quote="didilica"]... the second one converges...[/quote]
It doesn't, unless we go even farther- starting at 1 would eliminate the problem.


algebra
polynomial
induction
floor function

(1) If $ x \plus{} \frac {1}{x} \equal{} r$, express $ x^n \plus{} \frac {1}{x^n}$ in a polynomial of $ r$.
(2) More generally, given $ a_0 \equal{} 2$, $ a_1 \equal{} r$, and recursion $ a_n \equal{} a_{n \minus{} 1}\cdot a_1 \minus{} a_{n \minus{} 2}$, find an explicit polynomial formula of $ a_n$.

I don't have any clue...

1. Let $ a_k \equal{} x^k \plus{} x^{\minus{}k}$. So $ a_0 \equal{} 2, a_1 \equal{} r$, both polynomials in $ r$. Then observe that $ a_{k\plus{}1} \equal{} a_ka_1 \minus{} a_{k\minus{}1}$, sufficient to solve the problem: if $ P(x), Q(x)$ are polynomials, then $ xP(x) \minus{} Q(x)$ is going to be one as well.

2. Eerie... I didn't even read the second problem before giving the above solution. Is this problem just asking for $ a_k \equal{} x^k \plus{} x^{\minus{}k}$?

err...can you give the explicit formula? Maybe this sounds dumb, but I don't know the next step...

Edit: okay, basically the problem one is the set up of problem two. Yes, it asks for the formula of $ a_n$ in $ r$.

$ x^{k\plus{}1} \plus{} x^{\minus{}k\minus{}1} \equal{} (x^k \plus{} x^{\minus{}k})(x \plus{} x^{\minus{}1}) \minus{} x^{k\minus{}1} \minus{} x^{\minus{}k\plus{}1}$

So by a variant of math induction, if $ x^k \plus{} x^{\minus{}k}$ and $ x^{k\minus{}1} \minus{} x^{\minus{}k\plus{}1}$ are polynomials in $ x \plus{} x^{\minus{}1}$ (notice we gave two base cases), then $ x^{k\plus{}1} \plus{} x^{\minus{}k\minus{}1}$ is also. Is that what you were looking for?

Sorry, perhaps I didn't express the idea of this problem well, but it [b]doesn't[/b] ask for the [b]proof[/b] of the fact that $ x^n \plus{} \frac {1}{x^n}$ is a polynomial in $ r$, but demands [b]what [/b]the polynomial is.

I see. Sorry.

$ a_n \equal{} \sum_{i\equal{}0}^{\lfloor n/2 \rfloor}{\left({n\plus{}1\minus{}i \choose i} \minus{} {n\minus{}1\minus{}i \choose i\minus{}2}\right) \cdot(\minus{}1)^i \cdot r^{n\minus{}2i}}$ for $ n > 0$ is the required polynomial, where a binomial coefficient with a negative bottom element is treated as $ 0$.

The proof I found is slogging through algebra and repeated use of the recurrence relation and the identity $ {n\minus{}1 \choose k\minus{}1} \plus{} {n\minus{}1 \choose k} \equal{} {n \choose k}$. I didn't carry it through the whole way, so it's possible I screwed up the formula, but that should be very close. If someone has a better method or wants to write this one out, be my guest.


a) use the quadatric formula to find the zeroes of f
b) find the max and min value of f(x)
c) sketch the graph of f

1) -x^2 - 6x
2) -4x^2 + 4x -1

These look like textbook excersizes, you could probably post these in the middle school forums.

1. [hide]

a)

b)

A quadratic function will have its minimum or maximum at the vertex, which is at .

c) I don't know how to post images, so figure it out yourself.  It's a parabola.

[/hide]

2.[hide]

a)

b)

Since 1/2 is a root the maximum must be .

[/hide]


modular arithmetic
Recurrence
polynomial
Divisibility
Sequence
prime
IMO Shortlist

The sequence $a_0$, $a_1$, $a_2,$ $\ldots$ is defined as follows: \[a_0=2, \qquad a_{k+1}=2a_k^2-1 \quad\text{for }k \geq 0.\] Prove that if an odd prime $p$ divides $a_n$, then $2^{n+3}$ divides $p^2-1$.

[hide="comment"]
Hi guys ,

Here is a nice problem:

Let be given a sequence $a_n$ such that $a_0=2$ and $a_{n+1}=2a_n^2-1$ . Show that if $p$ is an odd prime such that $p|a_n$ then we have $p^2\equiv 1\pmod{2^{n+3}}$

Here are some futher question proposed by me :Prove or disprove that :
1) $gcd(n,a_n)=1$
2) for every odd prime number $p$ we have $a_m\equiv \pm 1\pmod{p}$ where $m=\frac{p^2-1}{2^k}$ where $k=1$ or $2$

Thanks kiu si u

[i]Edited by Orl.[/i]
[/hide]

Let  $ T_n $ be the Chebychev polynomial of degree $ n $ which is defined for $ x $  in [-1,1] , by $T_n(x)=\cos\left(n\cdot \arccos{x}\right) $.
 In this case  $  T_2(y)=2y^2-1 . $ Observe that
  \[
T_n\left(T_m(y)\right)=T_{nm}(y)=T_{m}\left(T_n(y)\right).
\]
In your case \[ a_{n+1}=T_2(a_n)=
T_{2}\left(T_{2}(a_{n-1})\right)=T_{2^2}(a_{n-1})(x)=...=\]
\[ =T_{2^j}(a_{n-j+1})=...=T_{2^{n+1}}(a_0)= ??
\]
 Note that another representation of $ T_n $ is  $
T_n(t)=\frac{1}{2}\left( (t+\sqrt{t^2-1})^n+ (t-\sqrt{t^2-1})^n\right)\; ,\;
t\in {\mathbb  R}. $ However $ T_m(1)=1 .$ Therefore ... ?
Perhaps help.

I'm under the impression that the problem has been posted before.

yeah, it's at least the third time it is posted.

your number 2 is correct, it is particularly easy to prove knowing $a_n=\frac{1}{2} \left((2+\sqrt{3})^{2^n}+(2-\sqrt{3})^{2^n}\right)$. it helps with the original problem as well, when going from $F_p$ into $F_{p^2}$, so one has no problems with square roots. but the reason that one has to do this is sure the reason for not taking it as an IMO problem since the problem itself is beautiful.

Peter

number 1 is correct as well if i'm not wrong. the proofs are not that hard.

Peter

Um! Sorry if the orginal problem is old!

 [quote]number 1 is correct as well if i'm not wrong. the proofs are not that hard[/quote]

Really i see!

[quote]your number 2 is correct, it is particularly easy to prove knowing....... . it helps with the original problem as well, when going from  into , so one has no problems with square roots. but the reason that one has to do this is sure the reason for not taking it as an IMO problem since the problem itself is beautiful.
[/quote]

Can u describe more details ? I just use something on $Z_p^*[\sqrt{3}]$ i think it helps!

it is correct that $gcd(n,a_n)=1$
We consider the $a_i$ modulo $p$.(p is prime) if one of $a_1,a_2,...,a_{p-1}$ is 0 or 1 modulo $p$ then $gcd(a_{kp},p)=1$. So one of the residues is came at least 2 times and because $a_i$ is alternating modulo $p$ so $gcd(a_n,p)=1$ for every $n$.So If $n=p_1^{a_1}p_2^{a_2}...p_k^{a_k}$ then $gcd(a_n,p_i)$=1 and problem is solved.

Oh if $p|a_n$ then $2^n+3|p^2-1$ and $p> \sqrt 2^{n+3}>n$ and problem is obvious.

I read the official solution, but it seems  that yours is slightly different. Can you please post a detailed solution? Thank you very much

Before proceeding with the proof, we note that if $p | a_n$, then 2 is a quadratic residue modulo $p$. Indeed, since $p | a_n = 2a_{n-1}^2 - 1$, $\left(\frac{1}{a_{n-1}}\right)^2 \equiv 2 \pmod{p}$, so 2 is a quadratic residue modulo $p$.

If $\theta = i \ln(2 + \sqrt{3})$, then $\cos \theta = 2$. We clearly have that
\begin{align*}
a_n
&= \cos(2^n \theta) \\
&= \frac{e^{2^n \theta i} + e^{-2^n \theta i}}{2} \\
&= \frac{e^{2^n (i \ln(2 + \sqrt{3})) i} + e^{-2^n (i \ln(2 + \sqrt{3})) i}}{2} \\
&= \frac{(2 + \sqrt{3})^{2^n} + (2 - \sqrt{3})^{2^n}}{2}
\end{align*}

We will now consider the sequence in $F_{p^2}$ (henceforth, all equalities will be taken in this field extension.) If $p | a_n$, we have that $(2 + \sqrt{3})^{2^n} + (2 - \sqrt{3})^{2^n} = 0$. Since $\frac{2 + \sqrt{3}}{2 - \sqrt{3}} = (2 + \sqrt{3})^2$, we rearrange this to find that $(2 + \sqrt{3})^{2^{n+1}} = -1$. But $2 + \sqrt{3} = \frac{(1 + \sqrt{3})^2}{2}$; since 2 is a quadratic residue mod $p$, we have that there exists some $a$ such that $a^2 = 2 + \sqrt{3}$. Therefore, $a^{2^{n+2}} = -1$.

Since $a^{2^{n+3}} = 1$, we must have that the order of $a$ in $F_{p^2}$ divides $2^{n+3}$, so it must be $2^k$ for some $k \leq n+3$. But if $k < n+3$, we may square the equality $2^{2^k} = 1$ a total of $n+2-k$ times to get that $2^{2^{n+2}} = 1 = -1$, which is a contradiction, so the order of $a$ is in fact $2^{n+3}$.

By Lagrange's theorem, $a^{p^2 - 1} = 1$, so we have that $2^{n+3} | p^2 - 1$, as desired.

[quote="Zhero"]
We will now consider the sequence in $F_{p^2}$ (henceforth, all equalities will be taken in this field extension.) If $p | a_n$, we have that $\color{red}{(2 + \sqrt{3})^{2^n} + (2 - \sqrt{3})^{2^n} = 0}$.

By Lagrange's theorem, $\color{red}{a^{p^2 - 1} = 1}$, so we have that $2^{n+3} | p^2 - 1$, as desired.[/quote]
Sorry to revive, but can you tell me how you reached these?
For the first one, that it holds on $F_p$ is clear but I'm not clear how it holds in $F_{p^2}$.
For the second one, I don't think Lagrange's Theorem implies that.

The first conclusion follows from the fact that any element zero in $F_p$ is zero in $F_{p^2}$. The second follows from the fact that the $p^2 - 1$ nonzero elements of $F_{p^2}$ form a group under multiplication, so we may apply Lagrange's theorem accordingly. Keep in mind that $F_{p^2}$ is not the same as $\mathbb{Z}/p^2 \mathbb{Z}$; it is the finite field of order $p^2$, which contains all elements of the form $a + b\sqrt{c}$, where $a$ and $b$ are integers and $c$ is a quadratic non-residue mod $p$.

One can find out $a_n$ explicitly in terms of $n$ by defining the sequence of $<b_k>_{k \ge 0}$ by $a_k=\cosh b_k$ where $\cosh$ is the hyperbolic cosine defined by $\cosh x=\frac{e^x+e^{-x}}{2}$(By observing that $b_{k+1}=2b_k$.Then there is a bit of case study as when $(\frac{3}{p})=1$ and when $(\frac{3}{p})=-1$

In fact, working in $ F_{p^2} $ is only required if $ 3 $ is nonresidue modulo $ p $.  If $ \sqrt{3} \in F_p $ then we can strengthen the claim to $ 2^{n + 3} \vert p - 1 $ using the same arguments as in Zhero's post.

It is interesting to note that the trick of finding an $ a $ such that $ a^2 = 2 + \sqrt{3} $ can be motivated by the proof of a very similar problem.  When proving that every prime factor $ p $ of a Fermat number $ 2^{2^n} + 1 $ satisfies $ p \equiv 1 \pmod{2^{n + 2}} $ this trick is also employed.

The hardest part of this problem the case when $\left(\frac{3}{p}\right)=-1$
Is there any way to do it without using Finite series and all that stuff.
Here are some facts that may help $v_2(a_n-1)=2^{n+1}\forall n\ge 2$.
By substituting $b_n=\frac{a_n-1}{2^{n+1}}$, I am getting a nice expression for $a_{n+1}$ in terms of $b_n$.
dibyo_99 told me that this problem cannot be solved using the facts that I have found...but still if somebody's interested.. please try to solve the problem using these facts .

This proof is actually really similar to the proof of Lucas-Lhemer on finding Mersenne primes.

We work in $\mathbb{F}_{p^2}$.

First let $b_n=2a_n$. Then $b_n$ satisfies the recurrence $b_{n+1}=b_n^2-2$. Then take an element $x$ in $\mathbb{F}_{p^2}$ with $x+1/x=4=b_0$. Then $b_n=x^{2^n}+x^{-2^n}$. Since $b_n=0$ this means $x^{2^{n+1}}=-1$, so the order of $x$ is $2^{n+2}$. Unfortunately, this means $2^{n+2}\mid p^2-1$, so we want to strengthen this somehow. It would work to show $\sqrt{x}\in\mathbb{F}_{p^2}$. But note $x=2+a$ where $a^2=3$. Then $2+a=(1+a)^2/2$, so we want to show $2$ has a square root. But note $\left(\frac{2}{p}\right)=1$ if $8\mid p^2-1$. Since $n>0$ we have $8\mid 2^{n+2}\mid p^2-1$, so $x=2+a$ has a square root in $\mathbb{F}_{p^2}$, so the order of that square root is $2^{n+3}$ and we are done.

Nice problem! Here's my solution:
Claim $1$: We have $a_n=\frac{(2+\sqrt{3})^{2^n}+(2-\sqrt{3})^{2^n}}{2}$.
Proof: Note that $a_{n+1}=2a_n^2-1$ which is similar to the $\cos(2x)=2 \cos(x)^2-1$. This motivates us to choose a complex number $z$ such that $\cos z=2$(defining the $\cos$ function by the De Moivre formula for complex numbers that is) and then we have $\cos (2^n*z)=a_n$. Thus, if we can find a nice recursion for $\cos (2^n*z)$, say $b_n$, then we have $b_{2^n}=a_n$. Some work from here using trigonometric identities and De Moivre formula gives that $b_1=2, b_2=7, b_n=4b_{n-1}-b_{n-2}$ and thus $a_n=b_{2^n}$. Solving for closed form gives $b_n=\frac{(2+\sqrt{3})^n+(2-\sqrt{3})^n}{2}$ which proves our claim.
Consider the sequence $c_n$ now, which is $c_1=1, c_2=4, c_n=4c_{n-1}-c_{n-2}$.
First of all, note that $2b_nc_n=c_{2n}$ which comes from solving for the closed form of $c_n$ which is
$c_n=\frac{(2+\sqrt{3})^n-(2-\sqrt{3})^n}{2}$.
Now we make a bunch of algebraic manipulations. Note that $2^nc_n=\frac{(4+2\sqrt{3})^n-(4-2\sqrt{3})^n}{2}$. But note that $4+2\sqrt{3}=(1+\sqrt{3})^2$ and $4-2\sqrt{3}=(1-\sqrt{3})^2$. Which means that if we take a sequence $d_n$ with
$d_1=1, d_2=2, d_{n+2}=2(d_{n-1}+d_n)$ then we have $d_{2k}=c_k*2^k$ by the closed form. This subtle manipulation will help us later, as we will see, also we can safely do it, as we are only concerned about the odd prime factors of $b_{2^k}=a_k$.
Now, we will prove some lemmas.
Lemma $1$: Define by $f(k)$ for a positive integer $k$ to be the largest positive odd factor of $k$. Then, we have $gcd(f(d_k),f(d_l))=f(d_{gcd(k,l)})$.
Proof: Same idea as proving that for Fibonacci numbers $F_i$ we have $gcd(F_m,F_n)=F_{gcd(m,n)}$, just consider mod $n$ for any factor(which must be odd) $n$ of $gcd(f(d_k),f(d_l))$ and use Bezout lemma. We leave the detail since the rest is trivial.
Lemma $2$: For any odd prime $p$, we have $p$ divides one of $d_p,d_{p-1},d_{p+1}$.
Proof: Again similar to the proof for $F_n$, except this time we have $p|d_{p-{3|p}}$ where we use the Legendre symbol, analogous proof as for $p|F_{p-{5|p}}$, just some manipulations with the closed form. We omit details so as to not make the proof too long.
Lemma $3$: In [Hide=my blog]https://artofproblemsolving.com/community/c932427[/Hide] I showed a LTE-like result on $F_n$. We can apply a particular part of the proof exactly the same and show that:
For any prime $p \neq 2,3$, if for some $n$ we have $p|d_n$ then we have, for all positive integers $k$:
$v_p(d_{nk})=v_p(d_n)+v_p(k)$, and hence the same can also be said if $d_n$ is replaced by $c_n$ as $c_n*2^n=d_{2n}$.
Note that the $p \neq 3$ condition doesn't affect our proof, and is safe, since mod $3$ check shows that $3$ never divides $b_{2^n}=a_n$ for any $n$.

Corollary of lemma $3$( this is the main thing we are concerned with): If an odd prime $p$ divides $2^k*c_{k}=d_{2k}$(hence it divides $c_k$) for any $k$ and $v_2(k)=l$, then $p$ doesn't divide any number of the form $b_q$ with $v_2(q) \geq l$.
Proof: We can see that there exists an odd number $r$ such that $p|c_{qr}$ and $p|b_q, b_q|b_{qr}$ by closed form thus $p|b_{qr}$. Now consider the LTE-ish result over $n=qr,k=2$ to get a contradiction.

Conclusion: Hence, we get that if odd prime $p$ divides $d_{2m}$ and $v_2(m)=l$ then $p$ never divides any number of the form $b_{2^l*k}$.
However we know that for $p \neq 3$( as $p=3$ doesn't matter since $3$ doesn't divide any $a_n$ anyway) we know from Lemma $2$ that $p$ divides one of $d_{p-1}, d_{p+1}$. Thus, if a prime $p$ divides $a_m=b_{2^m}$, and if $f(p)$ is the smallest positive number for which $p|d_{2f(p)}$, then we can see that $2^{m+1}|f(p)$ thus $2^{m+2}|2f(p)$. So one immediate necessary condition we get is that $2^{m+2}$ divides at least one of $p-1, p+1$. So we get that $p$ should be of the form $r*2^{m+2} \pm 1$ for some integer $r$, which translates to $2^{m+3}|p^2-1$. Thus we have proved that if an odd prime $p$ divides $b_{2^m}=a_m$ then we have $2^{m+3}|p^2-1$. Done.

Let $a_k=\frac{b_k+1/b_k}{2}$. The recursion becomes $b_{k+1}=b_k^2$, and we see that $b_0=2+\sqrt{3}$. Thus,
\[a_n=\frac{1}{2}\left[(2+\sqrt{3})^{2^n}+(2-\sqrt{3})^{2^n}\right].\]
Suppose $p$ is an odd prime dividing $a_n$. First, note that $(1/a_k)^2\equiv 2\pmod{p}$, so $2$ is a square mod $p$. Now, we'll work in the field $K=\mathbb{F}_p[\sqrt{3}]$, which may be just $\mathbb{F}_p$, or may be $\mathbb{F}_{p^2}$. We see that
\[a_n=0\iff\left(\frac{2+\sqrt{3}}{2-\sqrt{3}}\right)^{2^n}=-1.\]
But,
\[\frac{2+\sqrt{3}}{2-\sqrt{3}}=(2+\sqrt{3})^2=\left(\frac{(1+\sqrt{3})^2}{2}\right)^2=a^4\]
for some $a$, since $2$ is a square in $K$. Thus, we have $a^{2^{n+2}}=-1$. Let $\ell$ be the order of $a$ in $K$. We see that $\ell\nmid 2^{n+2}$ but $\ell\mid 2^{n+2}$, so $\ell=2^{n+3}$. But we also know $\ell\mid|K^\times|\mid p^2-1$ by Lagrange's theorem, so $2^{n+3}\mid p^2-1$, as desired.

Here's an informal solution written to highlight motivation instead of rigor. Solved with [b]eisirrational[/b] and [b]goodbear[/b].

Let $b_n = 2a_n$, so $b_n = b_{n-1}^2 - 2$. The key is to note (in a massive abuse of notation that will be resolved later), that for a prime $p \mid a_n$:
\begin{align*}
  a_{n-1}^2 - 2 &\equiv 0 \implies a_{n-1} \equiv \sqrt{2} \pmod{p}, \\
  a_{n-2}^2 - 2 &\equiv \sqrt2 \implies a_{n-2} \equiv \sqrt{2+\sqrt{2}} \pmod{p},\\
\end{align*}
and so on. So we need $\sqrt{2}, \sqrt{2+\sqrt{2}}, \dots$ to all exist modulo $p$, and moreover $\sqrt{2+\sqrt{2+\dots}} \equiv 4 \pmod{p}$ (where the LHS has $n$ twos).

Let's rewind to make sure we are doing real math. Let $x_k = {2+\sqrt{2+\sqrt{2+\dots}}}$ with $k$ twos, which exists modulo $p$ if $x_{k-1}$ is a quadratic residue. It does [i]not[/i] depend on the choice of square root we take, since it is true for $x_1 = 2$, and moreover $(2-\sqrt{x_{k}})(2+\sqrt{x_{k}}) = 4-x_{k} = 2 - \sqrt{x_{k-1}}$ is a QR (assuming $x_{k-1}$ is a QR) by induction so both factors are QRs or QNRs.

The following is our main claim.

[b][color=#ff9a00]Claim.[/color][/b] The value $\sqrt{x_k}$ exists (i.e. $x_k$ exists and is a QR) and can equal $4$ (for some choice of square roots) only if $p \equiv \pm 1 \pmod{2^{k+2}}$.

[i][color=#ff9a00]Proof.[/color][/i] By induction, $x_k$ exists if and only if $p \equiv \pm 1 \pmod{2^{k+1}}$. We now check when it is a QR; we use two cases.

[list]
[*] [b]Case 1: $-1$ is a QR.[/b] Then the number $\sqrt{x_k}/2 + \sqrt{4-x_k}/2 \cdot i = \operatorname{cis} \frac{\pi}{2^{k+1}}$ modulo $p$ exists and has order $2^{k+2}$. Thus, $2^{k+2} \mid p-1$.

[*] [b]Case 2: $-1$ is not a QR.[/b] We do largely the same thing: we just work in $\mathbb{F}_p[i]$ or $\mathbb{F}_{p^2}$. Then the number $\sqrt{x_k}/2 + \sqrt{4-x_k}/2 \cdot i = \operatorname{cis} \frac{\pi}{2^{k+1}}$ now exists and still has order $2^{k+2}$, but is also equal to $2$ and is thus a QR in of itself. So $2^{k+3} \mid p^2 - 1$ and thus $p \equiv -1 \pmod{2^{k+2}}$.
[/list]

Yeehaw! $\square$

Using the claim, $p \mid a_k$ if and only if $x_n$ is a QR, i.e. $p \equiv \pm 1 \pmod{p}$ and thus $2^{k+3} \mid p^2 - 1$ as desired.

 Define the sequence $b_n$ such that $a_n= \frac 12 \left( b_n+ \tfrac {1}{b_n} \right).$ Then the equation reads $b_{n+1}=b_n^2$ with $b_0=2+\sqrt 3$. Using this we have :

$$ a_n = \frac 12 \left ( (2+\sqrt 3)^{2^n} + (2-\sqrt 3)^{2^n} \right)$$

We will work in $\mathbb F_p[\sqrt 3]$ which maybe $\mathbb F_p$ if $3$ is a QR mod $p$ and $\mathbb F_{p^2}$ otherwise.

Note that if $\theta=2+\sqrt3$, we have :

$$ a_n=0 \iff \theta^{2^n}+ \theta^{-2^n}=0 \iff \theta^{2^{n+2}}=1$$

Since $\mathbb F_p[\sqrt 3]^{\times}$ is cyclic, we have $2^{n+2} \vert p^2-1$. It boils down to proving that $\sqrt \theta$ exists in $\mathbb F_p[\sqrt 3]$

Note that :

$$ \theta= 2+ \sqrt 3 = \frac 12 \left( 1+ \sqrt 3 \right)^2$$

So we need that $\left( \tfrac 2p \right)=1$ or equivalently $8\mid p^2-1$. However, we have $8 \mid  2^{n+2}\mid p^2-1$, so we are done.

Work in \(\mathbb F_{p^2}\), and let \(\omega=\frac{\sqrt6-\sqrt2}2\).

Observe by Chebyshev that \[a_n=\cosh\left(2^n\cdot\cosh^{-1}2\right)=\frac{(2-\sqrt3)^{2^n}+(2+\sqrt3)^{2^n}}2=\frac{\omega^{2^{n+1}}+\omega^{-2^{n+1}}}2.\] It follows that \[a_n=0\iff\omega^{2^{n+1}}+\omega^{-2^{n+1}}=0\iff\omega^{2^{n+2}}=-1.\]

This implies the order of \(\omega\) in \(\mathbb F_{p^2}\) is \(2^{n+3}\), i.e.\ \(2^{n+3}\mid p^2-1\).

I claim
\[a_{n} = \frac{(2+\sqrt{3})^{2^{n}} + (2-\sqrt{3})^{2^{n}}}{2}\]
We will prove this by inducktion. Our base case is $n = 0$, where we have
\[a_{0} = \frac{(2+\sqrt{3})^{2^{0}} + (2-\sqrt{3})^{2^{0}}}{2} = \frac{2+\sqrt{3} + 2-\sqrt{3}}{2} = 2\]
so our base case is proven. Onto our inducktive step. Assume this was true for $a_{n}$, we will prove this formula holds for $a_{n+1}$. We have
\[a_{n+1} = 2a_{n}^{2} - 1 = \frac{((2+\sqrt{3})^{2^{n}})^{2} + ((2-\sqrt{3})^{2^{n}})^{2} + 2\cdot((2-\sqrt{3})(2+\sqrt{3})^{2^{n}}}{2} - 1\]
\[= \frac{(2+\sqrt{3})^{2^{n+1}} + (2-\sqrt{3})^{2^{n+1}} + 2}{2} - 1 = \frac{(2+\sqrt{3})^{2^{n+1}} + (2-\sqrt{3})^{2^{n+1}}}{2}\]
This proves our inducktive step, so our inducktion is complete. First, observe that
\[2-\sqrt{3} = 2\cdot \left(\frac{1-\sqrt{3}}{2}\right)^{2}, 2+\sqrt{3} = 2\cdot\left(\frac{1 + \sqrt{3}}{2}\right)^{2}\]

Now, consider some prime $p | a_{n}$. I claim $2$ is a QR modulo $p$. This is because since $p | a_{n} = 2a_{n-1}^{2} - 1$, it means
\[\genfrac{(}{)}{}{}{\frac{p+1}{2}}{p}\genfrac{(}{)}{}{}{2}{p}= 1\Rightarrow \genfrac{(}{)}{}{}{2}{p} = 1\]
Therefore, $2$ is a QR modulo $p$.

Next, since $p$ is odd we must have
\[p | (2+\sqrt{3})^{2^{n}} + (2-\sqrt{3})^{2^{n}} \Rightarrow p | \left(\frac{(1-\sqrt{3})^{2}}{2}\right)^{2^{n}} + \left(\frac{(1+\sqrt{3})^{2}}{2}\right)^{2^{n}} \]
Again since $p$ is odd, we can ignore the factors of $2$ to get
\[p | (1-\sqrt{3})^{2^{n+1}} + (1+\sqrt{3})^{2^{n+1}}\]
If $3$ was a quadratic residue modulo $p$, then we can write $\sqrt{3}\equiv a\mod p$ to get
\[(1-a)^{2^{n+1}} \equiv -(1+a)^{2^{n+1}} \Rightarrow \left(\frac{(1-a)}{1+a}\right)^{2^{n+1}} \equiv -1 \mod p\]
Then, the order of $\frac{1-a}{1+a}$ must be $2^{n+2}$, so $p\equiv 1\mod 2^{n+2}$, which implies
\[v_{2}(p^{2}-1) = v_{2}((p-1)(p+1)) = v_{2}(p-1) + v_{2}(p+1) \geq n+2 + 1 = n+3\]
so $2^{n+3} | p^{2} - 1$.

Otherwise, assume $3$ was not a QR modulo $p$. Consider the field
\[\mathbb{F}_{p^{2}} = \mathbb{F}_{p}[\sqrt{3}] = \{a + b\sqrt{3} | a, b\in\mathbb{F}_{p}\}\]
Then since $p | a_{n}$ we have
\[(2+\sqrt{3})^{2^{n}} + (2-\sqrt{3})^{2^{n}} = 0 \Rightarrow \left(\frac{2+\sqrt{3}}{2-\sqrt{3}}\right)^{2^{n}} = -1\]
\[\Rightarrow ((2+\sqrt{3})^{2})^{2^{n}} = -1
\Rightarrow \left(\frac{(1+\sqrt{3})^{2}}{2}\right)^{2^{n+1}} = -1\]
Next, since $2$ is a QR modulo $p$, we can rewrite $2 = a^{2}$, and let $\frac{1+\sqrt{3}}{a} = c$. Now, we have
\[(c^{2})^{2^{n+1}} = c^{2^{n+2}} = -1\]
Therefore, the order of $c$ is $2^{n+3}$. It is well known that for any $x\neq 0$ in $\mathbb{F}_{p^{2}}$, we have $x^{p^{2} - 1} = 1$, thus $2^{n+3} | p^{2} - 1$, which is what we wanted to prove.

Note that
\[a_i=\frac{(2+\sqrt{3})^{2^i}+(2-\sqrt{3})^{2^i}}{2}\]
by an easy induction.
Work in the field extension of $\mathbb F_p$ containing $\sqrt{3}$ for $p\mid a_n$. Then $(2+\sqrt{3})^{2^{n+1}}=-1$. This implies $(2+\sqrt{3})^{2^{n+2}}=1$ so $2^{n+2}\mid p-1$, implying the desired.

This problem has a very beautiful theoretical background. Let me first present and prove a theorem of Lucas and Lehmer, which has a striking resemblance with our problem. We will then see how, in fact, the two proofs are isomorphic.
[rule]
[b][color=#3D85C6]Theorem:[/color][/b] Define the sequence $(t_i)_{i\geq 0}^{\infty}$ as $t_0=4$ and for $i\geq 1, \ t_i=t_{i-1}^2-2.$ Then, the $p^{th}$ Mersenne Number, $M_p:=2^p-1$ is prime if and only if $t_{p-2}\equiv 0\bmod{M_p}.$ This is also known as the [i]Lucas–Lehmer primality test[/i].

[b][color=#3D85C6]Proof:[/color][/b] We first want to find the general term of the sequence. Let $\omega=2+\sqrt{3}$ and $\overline{\omega}=2-\sqrt{3}.$

It follows by induction that $t_i=\omega^{2^i}+\overline{\omega}^{2^i}$ as such: \[t_{i-1}^2-2=\bigg(\omega^{2^{i-1}}+\overline{\omega}^{2^{i-1}}\bigg)^2-2=\omega^{2^{i}}+\overline{\omega}^{2^{i}}+2\big(\omega\overline{\omega}\big)^{2^{i-1}}-2=t_i.\]Assume that $t_{p-2}\equiv 0\bmod{M_p}.$ Therefore, for some positive integer $k,$ we have $\omega^{2^{p-2}}+\overline{\omega}^{2^{p-2}}=k\cdot M_p.$ By multiplying by $\omega^{2^{p-2}}$ we then get that $\omega^{2^{p-1}}+1=\omega^{2^{p-2}}\cdot kM_p.$ Assume that $M_p$ is composite and let $q$ be it's smallest prime factor. We will proceed to work in $\mathbb{Z}_q[\sqrt{3}].$

Observe that the inversable elements of $\mathbb{Z}_q[\sqrt{3}]$ form a group, $\mathbb{Z}_q^\times[\sqrt{3}]$ and because $0$ is an element with no inverse, then we have $$\big|\mathbb{Z}_q^\times[\sqrt{3}]\big|\leq \big|\mathbb{Z}_q[\sqrt{3}]\big|-1=q^2-1.$$Now, since $M_p\equiv 0\bmod{q}$ so $\omega^{2^{p-2}}\cdot k M_p=0$ which gives us $\omega^{2^{p-1}}=-1.$ Therefore, $\omega\in \mathbb{Z}_q^\times[\sqrt{3}]$ and its order is $2^p.$

However, the order of an element $g$ of a group $G$ is at most $|G|.$ This yields $2^p=\text{ord}(\omega)\leq\big|\mathbb{Z}_q^\times[\sqrt{3}]\big|\leq q^2-1.$

This is a contradiction, since $q$ is the smallest prime factor of $M_p,$ which is composite, so $q^2\leq M_p=2^p-1.$

Now, assume that $M_p$ is prime. Assume that $p>2$ yet again, to get that $M_p\equiv 7\bmod{12}$ and thus, $3$ is not a quadratic residue modulo $M_p$ but $2$ is a quadratic residue modulo $M_p.$ Then, by Euler's criterion, we get that \[3^{\frac{M_p-1}{2}}\equiv -1\pmod{M_p}\text{ and }2^{\frac{M_p-1}{2}}\equiv 1\pmod{M_p}.\]We'll continue working in $\mathbb{Z}_{M_p}.$ Now, by using the two latter congruences and the Binomial Theorem in a finite field, we get that \[(6+2\sqrt{3})^{M_p}= 6^{M_p}+(2\sqrt{3})^{M_p}=6-2\sqrt{3}.\]It now follows after a bunch of computations (we just use the 3 latter congruences) that \[\omega^{\frac{M_p+1}{2}}=\bigg(\frac{(6+2\sqrt{3})^2}{24}\bigg)^{\frac{M_p+1}{2}}=\frac{(6-2\sqrt{3})(6+2\sqrt{3})}{24}=-1.\]Finally, using the above evaluation of $\omega^{(M_p+1)/2}$ we can conclude that \[t_{p-2}=\omega^{2^{p-2}}+\overline{\omega}^{2^{p-2}}=\omega^{\frac{M_p+1}{4}}+\overline{\omega}^{\frac{M_p+1}{4}}=\overline{\omega}^{\frac{M_p+1}{4}}\big(\omega^{\frac{M_p+1}{2}}+1\big)=0.\]Hence, we proved both implication. The theorem is proven.
[rule]
Back to our problem, now that we have the LL Theorem in mind, observe that $a_i=t_i/2$ and thus we deduce that \[a_i=\frac{\omega^{2^i}+\overline{\omega}^{2^i}}{2}.\]Moreover, it follows naturally to work in $\mathbb{Z}_{p^2}^\times\cong\mathbb{Z}_p^\times[\sqrt{3}].$ As the numerous solutions above, we get that the order of $\omega$ is $2^{n+2}$ so $$2^{n+2}\mid |\mathbb{Z}_{p^2}^\times|=p(p-1)$$ and thus, $2^{n+3}\mid p^2-1.$

[quote=pluricomplex]The sequence $a_0$, $a_1$, $a_2,$ $\ldots$ is defined as follows: \[a_0=2, \qquad a_{k+1}=2a_k^2-1 \quad\text{for }k \geq 0.\] Prove that if an odd prime $p$ divides $a_n$, then $2^{n+3}$ divides $p^2-1$.[/quote]

[hide=A solution without using finite field would be better.]It is clear that $$a_n=\frac{(2+\sqrt{3})^{2^n}+(2-\sqrt{3})^{2^n}}{2}$$ by setting $a_0=\frac1{2}\left(t+\frac1{t}\right)$. Accordingly, if we define $(b_n)$ such that $b_0=1,b_1=2$ and $b_{n+2}=4b_{n+1}-b_n$, then $b_{2^k}=a_k$. Let $c_n$ be a sequence such that $c_1=1,c_2=4$ and $c_{n+2}=4c_{n+1}-c_n$, then $$c_n=\frac{(2+\sqrt{3})^{n}-(2-\sqrt{3})^{n}}{2\sqrt{3}}$$
and $$2b_nc_n=c_{2n}\implies p\mid 2b_{2^k}c_{2^k}=c_{2^{k+1}}.$$

By induction, one can show that $c_{m+n}=c_{m+1}c_n-c_mc_{n+1}$, so $\gcd (c_m,c_n)=c_{\gcd (m,n)}$ due to Bezout's theorem for $\gcd$ (Doing similarly to Fibonacci sequence). By the general formula, we get $b_n\pm \sqrt{3}c_n=(2\pm\sqrt{3})^n$, thus $b_n^2-3c_n^2=1$ or $\gcd (b_n,c_n)=1$. Henceforth $d=2^{k+1}$ is the minimal index such that $p\mid c_d$. It also can be proved that $p\mid c_{\frac{p-1}2}c_{\frac{p+1}2}$, so $$2^{k+1}\mid \frac{p\pm 1}2\implies 2^{k+3}\mid p^2-1.$$[/hide]

It is clear by induction that
$$a_n=\frac{(2+\sqrt{3})^{2^n}+(2+\sqrt{3})^{-2^n}}{2^{n+1}}.$$
Take some $p \mid a_n$ and work in $\mathbb{F}_{p^2}$. Since $2,\sqrt{3},\sqrt{2} \in \mathbb{F}_{p^2}$ and the last of these is nonzero, we can write
$$2+\sqrt{3}=\left(\frac{1+\sqrt{3}}{\sqrt{2}}\right)^2,$$
with the expression in parentheses being in $\mathbb{F}_{p^2}$ as well. Since $a_n=0$, we should have
$$(2+\sqrt{3})^{2^n}+(2+\sqrt{3})^{-2^n}=0 \implies (2+\sqrt{3})^{2^{n+1}}=-1 \implies \mathrm{ord} (2+\sqrt{3})=2^{n+2} \implies \mathrm{ord} \left(\frac{1+\sqrt{3}}{\sqrt{2}}\right)=2^{n+3},$$
so by Lagrange we have $2^{n+3} \mid p^2-1$, as desired. $\blacksquare$


function
geometry
geometric transformation
rotation
algebra proposed
algebra

find a function like $ f: N \to N$ such  that  :
$ f(f(n))\equal{}n^2$

More than just pointing out a function satisfies the problem, we will find every function $ f: \mathbb{N}\to\mathbb{N}$ satisfies it.

Suppose that $ \exists n_1,n_2\in\mathbb{N}$ such that $ f(n_1) \equal{} f(n_2)$ then $ f(f(n_1)) \equal{} f(f(n_2))$ so $ n_1^2 \equal{} n_2^2$, meanwhile $ n_1 \equal{} n_2$. Hence, $ f(n)$ is an injective function.

From the problem we have $ f(n^2) \equal{} f(f(f(n))) \equal{} f^2(n)$, since then $ f(0) \equal{} f^2(0)$ and $ f(1) \equal{} f^2(1)$, providing that $ f(0) \equal{} 0,f(1) \equal{} 1$ or $ f(0) \equal{} 1,f(1) \equal{} 0$ (since $ f$ is injective). Moreover, we will just need to find $ f$ in the set of non-perfect squares. Let $ \mathcal{H}$ denoted the set of every non-perfect squares.

Consider $ n\in\mathcal{H}$, there are two cases:
1. There is no such $ m\in\mathbb{N}$ such that $ f(m) \equal{} n$, then $ f(n)\in\mathcal{H}$. Indeed, if $ f(n)$ is a perfect square, i.e. $ f(n) \equal{} k^2$ then $ f(n) \equal{} f(f(k))$, and with the deduced fact that $ f$ is injective we have $ n \equal{} f(k)$, contradiction.

2. There is a number $ m\in\mathbb{N}$ such that $ f(m) \equal{} n$, then $ m\in\mathcal{H}$. Indeed, suppose the contrary that $ m$ is a perfect square, i.e. $ m \equal{} k^2 \equal{} f(f(k))$, then $ n \equal{} f(m) \equal{} f(f(f(k))) \equal{} f^2(k)$, contradicted to the fact that $ n\in\mathcal{H}$. We also have $ f(n) \equal{} f(f(m)) \equal{} m^2$.

Thus, we conclude that the existence of $ f$ divided $ \mathcal{H}$ into two sets $ \mathcal{H}_1$ and $ \mathcal{H}_2$ in such way that $ \forall m\in\mathcal{H}_1$, there exists one and only one $ n\in\mathcal{H}_2$ such that $ f(m) \equal{} n$ and $ f(n) \equal{} m^2$.

Therefore, we can describe the class of functions satisfies the problem as followed:

1. $ f(1) \equal{} 0,f(0) \equal{} 1$ or $ f(0) \equal{} 1$ and $ f(1) \equal{} 0$.
2. Divide the set $ \mathcal{H}$ of non-perfect squares into ordered pairs of $ (a,b)$. Then define for every $ (a,b)$ such that $ f(a) \equal{} b$ and $ f(b) \equal{} a^2$.
3. For every perfect square $ n^2$, define $ f(n^2) \equal{} f^2(n)$.

Functions defined above satisfies the problem. Also, with the argument given, this is the whole class of functions satisfies it. QED.

More generally,for any prime $ p$ ,there exists a function $ f: N\to N$ such that $ f(f(n))\equal{}n^p$.

[i]I have read the solution of this problem a long time ago , so now I cannot remmember clearly

    But I guess that  the main key to do that problem is to prove :

    There exist  a function $ g \ : \ \mathbb{N} \mapsto  \mathbb{N}$ such that :

    \[ g(g(n)) \ \equal{} \ 2n  \ \forall n \ \in \ \mathbb{N}\]

   Sorry for me , I have to go out with my girl friend , I will continue that work as soon as possible :blush: [/i]

In the general case, you can always point out whether there exists a function $ f: \mathbb{N}\to \mathbb{N}$ satisfies $ f(f(n)) \equal{} g(n),\forall n\in\mathbb{N}$ or not. It depends whether $ |\mathcal{H}(g)|$ is odd or even, where $ \mathcal{H}(g)$ is the set of positive integer $ n$ that can not be written in the form $ n\equal{}g(m)$.

Another example:

[b]Problem 4, IMO 1987.[/b]
Prove that there is no such function $ f: \mathbb{N}^*\to\mathbb{N}^*$ satisfies $ f(f(n)) \equal{} n \plus{} 1987,\forall n\in\mathbb{N}^*$.

[quote="Mashimaru"]In the general case, you can always point out whether there exists a function $ f: \mathbb{N}\to \mathbb{N}$ satisfies $ f(f(n)) \equal{} g(n),\forall n\in\mathbb{N}$ or not. It depends whether $ |\mathcal{H}(g)|$ is odd or even, where $ \mathcal{H}(g)$ is the set of positive integer $ n$ that can not be written in the form $ n \equal{} g(m)$.[/quote]What if $ \mathcal{H}(g)$ is an infinite set? For example, as in the original problem $ f(f(n))\equal{}n^2$, there are infinitely many positive integer $ n$ that cannot be written in the form $ m^2$.

Anyway, the problem appears in PEN K1: http://www.mathlinks.ro/viewtopic.php?t=150744

[quote="Johan Gunardi"][quote="Mashimaru"]In the general case, you can always point out whether there exists a function $ f: \mathbb{N}\to \mathbb{N}$ satisfies $ f(f(n)) \equal{} g(n),\forall n\in\mathbb{N}$ or not. It depends whether $ |\mathcal{H}(g)|$ is odd or even, where $ \mathcal{H}(g)$ is the set of positive integer $ n$ that can not be written in the form $ n \equal{} g(m)$.[/quote]What if $ \mathcal{H}(g)$ is an infinite set? For example, as in the original problem $ f(f(n)) \equal{} n^2$, there are infinitely many positive integer $ n$ that cannot be written in the form $ m^2$.

Anyway, the problem appears in PEN K1: http://www.mathlinks.ro/viewtopic.php?t=150744[/quote]

If $ \mathcal{H}(g)$ is an infinite set, just think that the parity of a number is not change after a rotation, I meant $ 8$ and $ \infty$ :rotfl:.

OK, it is just some kidding. The key point here is that the set $ \mathcal{H}(g)$ can be divided into pairs, which is able with an infinite set $ \mathcal{H}(g)$.

[quote="Johan Gunardi"]That doesn't hold if g is not injective. For example, define g(1)=1 and g(n)=n-1 for n>1.

We'll prove that there no function f such that f(f(n))=g(n). Let f(2)=k. Assume that k>2. Then f(k)=f(f(2))=1. Thus f(1)=f(f(k))=k-1, hence f(f(1))=f(k-1), which gives 1=f(k-1), so f(1)=f(f(k-1))=k-2. So we have f(1)=k-1 and f(1)=k-2, impossible. Therefore k=1 or k=2. If f(2)=2, then 1=f(f(2))=f(2)=2 which is impossible. If f(2)=1, then f(f(2))=f(1)=1. We have f(1)=f(2)=1. Let c be such that f(c)=2, thus f(f(c))=1, so c-1=1, or c=2. So f(2)=2, a contradiction. So no such function exists.[/quote]

That's right, Mr.[b]Johan Gunardi[/b]. I should have stated that $ g$ must be injective. The proof when $ g$ is injective can be obtained similarly from the proof posted in this topic (#2).


Does there exists two transcendental numbers $ x,y > 0$ such that $ x \plus{} y\in \mathbb{N}$ and $ xy\in\mathbb{N}$? If yes, can you find infinitely many of them?

If $ x\plus{}y\equal{}m$ and $ xy\equal{}n$, you get $ x(m\minus{}x)\equal{}n$, thus $ x$ (and the same way $ y$) is algebraic.


Well I go on with the following:
If $ a,b,c$ are positive reals, with $ \sum a^2 \equal{} 1$, then the following inequality holds good:
$ \sum\dfrac{a^5 \plus{} b^5}{ab(a \plus{} b)}\ge n \plus{} 1(\sum ab) \minus{} n$ for all natural nos. $ n \ge 2$.

Proof:
It is very well known that $ a^5 \plus{} b^5\ge a^2b^2(a \plus{} b)$ which is easily seen from power mean inequality.
This implies that
$ \sum\dfrac{a^5 \plus{} b^5}{ab(a \plus{} b)}\ge \sum ab$.
Now our inequality is equivalent to proving that $ \sum ab\ge n\plus{}1(\sum ab) \minus{} n$ which is further equivalent to prove that
$ n(\sum ab) \le n$ which is easily seen from the fact that $ \sum ab\le \sum a^2 \equal{} 1$.

In fact, $ \sum\dfrac{a^5 \plus{} b^5}{ab(a \plus{} b)}\ge (n \plus{} 1)(\sum ab) \minus{} n$ holds not only for natural $ n\ge 2$, but for all $ n\in \mathbf{R_0^\plus{}}$

Yes. t holds for all positive. Thanks. :lol:


algebra
function
domain
polynomial
Galois Theory
Ring Theory

I believe this is the correct forum to post it in since I'm still at high school.
I'm working with the Isomorphism Extension Theorem and is a bit stuck. I understand the conjugate isomorphism ${{ \psi _{\alpha, \beta} : F(\alpha}) \rightarrow F(\beta})$ completly.

The idea of Isomorphism Extension Theorem, is to extend the map  $ \sigma : F \rightarrow F'$   to an extension    $ \tau : E \rightarrow E' \subseteq \overline{F'}$, such that $ \sigma(a)= \tau(a)$ for all $ a \in F$

They are also saying that if $ \alpha, \beta \in E$ is algebraic over $ F$, then all extensions of $ \sigma$  is automorphism, but if it's not then it's only a isomorphism. This really makes my head spin, because it doesn't really make sense. At least for me. Obviously I see that is $ \alpha, \beta \in E$ isn't algebraic over $ F$, then it won't be a part of $ \overline{F}$ and the map  $ \tau : E \rightarrow E' \subseteq \overline{F'}$ can't be an automorphism. However, I do not completly get this and I don't get how there can be more isomorphic mappings than automorphism. Could someone please clarify this with examples, please.

[quote="LydianRain"]It would help if you told us the name of the book where you are reading these statements. :)

One important distinction to make is between isomorphisms, which are in general between different fields, and automorphisms, which are always from one field to itself.  I can't say more because it's unclear how your $ \alpha$ and $ \beta$ are defined.[/quote]

Certinally, I'm using "A first course in Abstract Algebra" by John B. Fraleigh. This stuff is explained mostly in section 49-50. He's talking about index which is the number of isomorphisms of E onto a subfield of $ \overline{F}$ and the order of the group G(E/F), which are only equal if E is a splitting field of finite degree over $ F$. That I feel is hard to understand.

[quote="LydianRain"]Since probably many people here don't own the book, until you ask a specific question (and define all your terms) it's likely that you won't get many responses.

The only specific question I can find in your original post is "I don't get how there can be more isomorphic mappings than automorphism."  But as I already said, an automorphism is a specific type of isomorphism, so this is obvious.  Or did you mean something else?[/quote]
The reason why I can't ask a specific question is because I don't know what I am not getting.

Yes, I meant something else, or I wouldn't be here to ask the question. Let's take the group of all automorphisms of $ E$ onto a subfield of $ \overline{\mathbb{Q}}$ which is  $ G(E \equal{} \mathbb{Q}(\sqrt2, \sqrt3),\mathbb{Q})$ The automorphisms is well defined as
$ i: (1 \plus{} \sqrt2 \plus{} \sqrt3 \plus{} \sqrt 6) \equal{} 1 \plus{} \sqrt2 \plus{} \sqrt3 \plus{} \sqrt 6$
$ \psi_{\sqrt2, \minus{} \sqrt { 2}} (1 \plus{} \sqrt2 \plus{} \sqrt3 \plus{} \sqrt 6) \equal{} 1 \minus{} \sqrt2 \plus{} \sqrt3 \minus{} \sqrt 6$
$ \psi_{\sqrt3, \minus{} \sqrt { 3}} (1 \plus{} \sqrt2 \plus{} \sqrt3 \plus{} \sqrt 6) \equal{} 1 \plus{} \sqrt2 \minus{} \sqrt3 \minus{} \sqrt 6$
$ \psi_{\sqrt3, \minus{} \sqrt { 3}}\psi_{\sqrt2, \minus{} \sqrt { 2}} (1 \plus{} \sqrt2 \plus{} \sqrt3 \plus{} \sqrt 6) \equal{} 1 \minus{} \sqrt2 \minus{} \sqrt3 \plus{} \sqrt 6$

However, the index is the number of isomorphism of $ E$ onto a subfield of $ \overline{F}$. Then why woudn't $ \psi_{\sqrt2,\minus{}\sqrt { 5}}$ be one of the isomorphisms, which it isn't because the index is 4? To be more specific. What makes it part of the set of isomorphisms? Could someone come with an example with some isomorphisms that isn't automorphisms. I tried to define some of the terminology that I used, which could be a bit unclear. For instance $ \overline{F} \equal{}${$ \alpha | \alpha$ is algebraic over $ F$}  is of course the algebraic closure on $ F$.

The definition of index in my book state.
49.9 Definition. Let $ E$ be a finite extension of a field $ F$. The number of isomorphism of E onto a subfield of $ \overline{F}$ leaving $ F$ fixed is the index {E:F} of $ E$ over $ F$

[quote="Camlon"]Let's take the group of all automorphisms of $ E$ onto a subfield[/quote]
Hang on, hang on.  As I explained, an automorphism cannot be "onto" anything, it is always from a field to itself.  I don't know if these are typos but these statements make me think that you are confused about the definitions.

[quote="Camlon"]$ \psi_{\sqrt{2}, \sqrt{\minus{}2}}$[/quote]
Is this a typo?  Do you mean $ \psi_{\sqrt{2}, \minus{}\sqrt{2}}$ perhaps?

[quote="Camlon"]$ \psi_{\sqrt3,\sqrt { \minus{} 3}}\psi_{\sqrt2,\sqrt { \minus{} 2}} (1 \plus{} \sqrt2 \plus{} \sqrt3 \plus{} \sqrt 6) \equal{} 1 \minus{} \sqrt2 \minus{} \sqrt3 \minus{} \sqrt 6$[/quote]
This should be $ \plus{}\sqrt{6}$, of course. :)

[quote="Camlon"]Then why woudn't $ \psi_{\sqrt2,\sqrt { \minus{} 5}}$ be one of the isomorphisms?[/quote]
You never defined this notation.  Are you asking if $ \sqrt{2}$ can be mapped to $ \sqrt{\minus{}5}$ by some automorphism that fixes $ \mathbb{Q}$?  The answer is no; if $ \sigma: E \to E$ is an automorphism then $ (\sqrt{2})^2\minus{}2\equal{}0$ so $ (\sigma(\sqrt{2}))^2\minus{}2 \equal{} 0$, so $ \sigma(\sqrt{2})$ cannot possibly be anything besides $ \pm\sqrt{2}$.

Or did you mean $ \psi_{\sqrt5, \minus{} \sqrt { 5}}$?  In that case, $ \sqrt{5}$ is not even [i]in[/i] $ E$, so actually $ \psi_{\sqrt5, \minus{} \sqrt { 5}} \equal{} i$ in this case. (that is, for any element in $ E$, they give the same result)

[quote="Camlon"]Could someone come with an example with some isomorphisms that isn't automorphisms.[/quote]
One example is $ E\equal{}\mathbb{Q}(\sqrt[4]{2})$.  Then $ \sigma(\sqrt[4]{2}) \equal{}i \sqrt[4]{2}$ defines an isomorphism of $ E$ onto a subfield of $ \overline{\mathbb{Q}}$ (namely $ E' \equal{} \mathbb{Q}(i \sqrt[4]{2})$) that is not an automorphism. (to see this, just notice that all elements of $ E$ are real)

Please just a haaaaair more time proofreading your posts.  Most people will overlook a post if the meaning is not immediately apparent to them.  But I also studied Galois theory in high school, so I'm highly in support. :)

Well an automorphism could be onto something, itself, which is a subfield of $ \overline{F}.$ Actually, it's always onto itself and it was riddiculus of me to mention it. To be onto, the image has to cover the whole co-domain, which is does by definition if it's an automorphism.

I normally do read over my posts, but I didn't really look at the $ \sqrt {2}$ so much. I meant $ \phi_{\sqrt {2}, \minus{} \sqrt {2}}$ I always have a tendency to make silly mistakes making me look stupid. I do small stuff like that all the time. I believe I changed +6 to -6 after I copied, but oh well. I'll change that stuff now.

Not really. I'm asking if $ \sqrt2$ can be mapped isomorphically onto $ \minus{} \sqrt5$. For instance.
$ \phi : Q(\sqrt {2}) \rightarrow Q(\sqrt {5})$ defined by
$ \phi : (1 \plus{} \sqrt {2}) \equal{} 1 \minus{} \sqrt {5}$ Which is an isomorphism that holds Q fixed, because it's one to one, onto, and holds the homomorphism property. It's of course not an automorphism. However, this isomorphism isn't counted in the index of all isomorphisms of  $ Q(\sqrt{2})$ that holds Q fixed.

Thanks for the example. I believe I saw that they were all conjugates. I think that may be the root of my problem and you have helped me a great deal. I do absolutly see that's not an automorphism. I'm sorry for making my posts look bad. How was studying galois theory for you? I find it hard, but very interesting.

Didn't mean to be so harsh about the typos, but after a certain point it just makes it hard to read.  Practice makes perfect.

As I said, $ \sqrt{2}$ cannot be mapped onto $ \sqrt{5}$ by an automorphism.  In fact, not even by a homomorphism, so when you say that $ \phi : (1\plus{}\sqrt{2})\equal{} 1\plus{}\sqrt{5}$ "holds the homomorphism property" it's not quite correct.

Here it is in a little more detail: let $ a\equal{}\sqrt{2}$, then $ a^2\equal{}2$.  Taking $ \phi$ of both sides, we find that $ \phi(a^2)\equal{}\phi(2)\equal{}\phi(1)\plus{}\phi(1)\equal{}2$, so $ (\phi(a))^2\equal{}2$.  If $ \phi(a)\equal{}\sqrt{5}$, then $ (\phi(a))^2\equal{}5$, contradiction.

The general statement is that if $ \sigma$ is some automorphism of $ E$ that fixes $ F$, any polynomial equation in $ F$ is preserved by $ \sigma$, hence $ \sigma$ must permute the roots of any given polynomial.  Since $ \sqrt{2}$ is a root of $ x^2\minus{}2$, and $ \sqrt{5}$ is not, the result follows.

Put another way: $ \sqrt{2}$ and $ \sqrt{5}$ are not conjugates.

As for how Galois theory was, I developed some intuition fairly quickly but I did not follow many of the proofs at the time.  It was a very exciting subject, though. (and still is!)

I'm pretty certain I have got it now and the rest of the stuff I didn't understand is opening up. Thank you for the help and patience. I really mean it.

I need to study this because I'm writing an essay with nearly 4000 words (Extended Essay, IB) about why quintics are not solvable by radicals. It's due christmas this year and is the most important essay I'm going to write.

[quote="randomgraph"]Just a side question: are you writing an article about why the [i]general[/i] quintic is not solvable by radicals, or about why some [i]specific[/i] quintics are not solvable by radicals? If it's up to you, I would encourage you to focus on the latter. It's more concrete, more surprising and a lot more convincing, in my mind, plus it actually requires less machinery and less messy notation.

After going over the fundamental theorems of Galois theory, you can just pick a specific quintic, say one with three real roots, and use a simple argument to show that it's Galois group must be $ S_5$. It's therefore unsolvable by radicals, which means very concretely that it has some roots which are not given by any radical expression over the rationals.[/quote]

I believe that I'm writing about why a specific set of quintics are not solveable by radicals. If some quintics are not solveable by radicals, then there will also be no quintic formula. They are using the argument that the galois group is isomorphic to $ S_5$.

I can choose whatever title I want, and I may change it if I find a better name. It's clearly stated that the research question should match the essay. I will also use large portions of my essay, defining terms and building up the neccesary theory, so there will be no large assumptions and name-dropping. I have written 4 pages allready with about 700 words and I have covered all the neccesary proofs and definitions to extension fields. For instance, field, maximal ideal, etc.


I would need a Linux program or a method to make following diagrams in $ \text{\LaTeX}$: on $ x$-axis there are all integers $ 1,\ldots, 10$ and on $ y$-axis there are integers, say $ 50,\ldots,300$. Then there are data points $ (i,y_i)$ where $ 50\leq y_i\leq 300$ and line segments from $ (i,y_i)$ to $ (i + 1,y_{i + 1})$ for all $ i\in \{ 1,\ldots,9\}$.

Also, I would like to know is the line segment diagram correct term for the diagram of that type.

Use [url=http://www.artofproblemsolving.com/Wiki/index.php/Asymptote:_Getting_Started]Asymptote[/url]. Search and ask on the [url=http://www.artofproblemsolving.com/Forum/index.php?f=519]Asymptote forum[/url] if you have any difficulties.


algebra
polynomial
calculus
integration
Putnam
real analysis
real analysis unsolved

From AACOPS,

Let $ a, b, c, d, e \in \mathbb{R}$ such that

$ a+\frac{b}{2}+\frac{c}{3}+\frac{d}{4}+\frac{e}{5}= 0$

Show that the polynomial $ a+bx+cx^{2}+dx^{3}+ex^{4}$ has at least one real zero.

[quote="edoo"]As for the solution to the problem you posed, you were on the right track.  You just needed to apply Rolle's theorem:

Let $ P(x)=ax+\frac{b}{2}x^{2}+\frac{c}{3}x^{3}+\frac{d}{4}x^{4}+\frac{e}{5}x^{5}$.

Then $ P(1)=0$ by the given data, and obviously $ P(0)=0$.  So just apply Rolle's theorem to get the result.[/quote]

Hehe, yeah my friend pointed out that what I did was invalid b/c it would also result in 0, but then I recognized I could analyze the integral and use Rolle's Theorem as you showed.

It's really the same proof, but a different phrasing of it. Let $ Q(x)$ be the given polynomial. Then $ \int_{0}^{1}Q(x)\,dx=0.$ Since $ Q$ is continuous, the Mean Value Theorem for integrals shows that $ Q$ has a zero somewhere in $ [0,1].$

This was a Putnam problem, I am 100% sure of this, I just cant find the year.

If so, it's an easy one - must be an A1 or B1.


The inequality is equivalent to :
$\sum\frac{1+a^{2}-2bc}{3+a^{2}-2bc}\geq \frac{3}{4}$
By cauchy
$\sum\frac{1+a^{2}-2bc}{3+a^{2}-2bc}\geq\frac{4(2-\sum bc)^{2}}{8-4\sum bc+\sum (1+a^{2}-2bc)^{2}}$ .

Putting $ab+bc+ca=w$ the inequality expanding suffices to show that
$11-20w+5w^{2}+12abc(a+b+c)\geq 0$

By schur we have that $6abc(a+b+c)\geq 2w^{2}+w-1$
so itsuffices to prove that
$11-20w+5w^{2}+2(2w^{2}+w-1)\geq 0$  or $9(w-1)^{2}\geq 0$ which is true

How can by Schur's we get $6abc(a+b+c) \geq 2w^{2}+w-1$  :maybe:
All I can say that the inequality is equivalent with
$\sum_{cyc}(a^{2}+b^{2}-c^{2})(a-b)^{2}\geq 0$

Thx a lot  :)

I think it is equivlent to $\sum a^{2}(a-b)(a-c)\geq 0$ too. :)

Oh.. I see  :)
But I think silouan has recognized that form as a Schur's with $n=2$ without changing into $\sum_{cyc}a^{2}(a-b)(a-c) \geq 0$, hasn't he ??  :roll:
Is there any other "special" forms  ?

No I don't think so ,he just omitted the details.