how to find the remainder when a polynomial $p(x)$ is divided my another polynomial $q(x)$

i was solving the question from the book IIT FOUNDATION AND OLYMPIAD - X and i was solving the problems of polynomials-III. so on the page number 136, there is a question (question 17) given below:

The remainder when $x$^100 is divided by $x^2-3x+2$ is:

a) $(2$^100$-1)x + (-2$^100$ +2) $

b) $(2$^100$+1)x + (-2$^100$ -2) $

c) $(2$^100$-1)x + (-2$^100$ -2) $

d) none

as far as i tried to find the remainder, i tried long division method but it was getting more and more complicated, then i used systematic method of division but i can't get the corret option
what is the correct option. please explain me how did you find the remainder. thanks

and yes its answer is option (a)

Answer

Hint Write $x^{100}= (x^2-3x+2)q(x) + ax+b$. Now plug $x=1$ and $x=2$ to find $a$ and $b$.

combinatorics - Combinatorial reasoning for the identity $left ( sum_{i=1}^n i right )^2 = left ( sum_{i=1}^n i^3 right ) $

There is the interesting identity:

$$\left ( \sum_{i=1}^n i \right )^2 = \left ( \sum_{i=1}^n i^3 \right ) $$
which holds for any positive integer $n$.

I know several was of proving this (finite differences, induction, algebraic tricks etc..), but even so I still find it "weird" that it is even true.

Is there a very nice intuitive way to prove this using some kind of combinatorial argument? (Like the why the sum of the volume of the first $n$ cubes should be the area of ... not sure here?)

If you have any pretty different proof that could be enlightening I would love to see it.

Thanks a lot!

calculus - Exponential of complex square root

Is there any way to simplify any further the exponential of a complex square root, as in the following expression:

$$ e^{ a + \sqrt{x + i\cdot y}}, $$

where $a>0, x >0$ and $y<0$. If I were to select the principal square root, I could define $ r = \sqrt{x^2 + y^2}$ and $\theta = \arctan {x/y}$. Then,

$$ e^{ a + \sqrt{r}\cdot(\cos(\theta/2) + i\cdot \sin(\theta/2) )}. $$

Is there a way to get a friendlier or simplify? I have to later on integrate this expression with respect to $y$ and it doesn't seem easy to integrate.

Answer

The integration does not seem to be very difficult.

Let
$$\sqrt{x+i y}=t \implies y=i \left(x-t^2\right)\implies dy=-2it\,dt$$
$$\int e^{a+\sqrt{x+i y}}\,dy=-2i e^a\int t e^{\sqrt{t^2}}\,dt$$ Simplify and use one integration by parts.

number theory - Arithmetic progression divisibility

Suppose $b|a$ and $\frac{a}{b} \neq \frac{v}{y}$, $a, b, v, y \in \mathbb{N}$ arbitrary. Is there a nice clean intuitive proof to show that it is never true that $b+yk|a+vk$ for all $k \in \mathbb{N}$? Or is it true sometimes after all (I strongly feel like not)?

Answer

Assume for contradiction that for all $k\in \Bbb N$, $a+vk|b+yk$ and consider the sequence $u_k\in \Bbb Z$ such that $u_k(a+vk) = b+yk$. Then since $u_k = {b+yk\over a+vk} \to {y\over v}$ as $k$ goes to $+\infty$, $u_k$ approaches ${y\over v}$ arbitrary close, which therefore must be an integer, and thus $v|y$. Let $u \in \mathbb{Z}$ be such that $y = vu$. Then for all $k\in \Bbb N$ we have $a+vk |b+vuk$ and therefore also $a+vk |b-au$. However since $a+vk$ is unbounded and $b-au$ does not depend on $k$, what follows is that $b-au = 0$, which rewrites as ${a\over b} = {v \over y}$.

The contrapositive of this is your statement.

elementary number theory - Prove that if $gcd( a, b ) = 1$ then $gcd( ac, b ) = gcd( c, b ) $

I know it might be too easy for you guys here. I'm practicing some problems in the textbook, but this one really drove me crazy.
From $\gcd( a, b ) = 1$, I have $ax + by = 1$, where should I go from here? The extra $ac$ is so annoying. Any hint?

Thanks,
Chan

Answer

Setup: Let $d_1 = \gcd(c,b)$ and $d_2 = \gcd(ac,b)$.

So we have $cx_1 + by_1 = d_1$, $acx_2 + by_2 = d_2$, and $ax + by = 1$.

Step 1: Multiply $ax+by = 1$ by $d_1$ (using $d_1 := cx_1 + by_1$) and rearrange to show that $d_2|d_1$.

$$\begin{aligned}
d_1 (ax+by &= 1)\\

\implies ax(cx_1 + by_1) + bd_1y &= d_1 \\
\implies a c (x x_1) + b(a x y_1 + d_1 y) &= d_1
\end{aligned}$$

Since we know that $d_2 = \gcd(ac,b)$ divides any integer linear combination of $ac$ and $b$, we have $d_2 | d_1$.

Step 2: By a similar argument, multiply $ax+by = 1$ by $d_2$ (using $d_2 := acx_2 + by_2$) and rearrange to show that $d_1|d_2$.

$$\begin{aligned}
d_2 (ax+by &= 1) \\

\implies ax(acx_2 + by_2) + bd_2y &= d_2 \\
\implies c (a^2 x x_2) + b(a x y_2 + d_2 y) &= d_2
\end{aligned}$$

Since we know that $d_1 = \gcd(c,b)$ divides any integer linear combination of $c$ and $b$, we have $d_1 | d_2$.

Conclusion: Finally, because we have $d_1 | d_2$, $d_2 | d_1$, and $d_1$ and $d_2$ are non-negative (since they are the gcd of two integers), we conclude that $d_1 = d_2$. Thus, $gcd(ac,b)=gcd(c,b)$.

sequences and series - Trigonometric proof stuck with induction step

I am trying to prove:
$$\sum_{s=0}^{\infty}\frac{1}{(sn)!}=\frac{1}{n}\sum_{r=0}^{n-1}\exp\left(\cos\left(\frac{2r\pi}{n}\right)\right)\cos\left(\sin\left(\frac{2r\pi}{n}\right)\right)$$

We know that $$\begin{align}\exp\left(\cos\theta+i\sin\theta\right)&=e^{\cos\theta}\times e^{i\sin\theta}\\& =e^{\cos\theta}\left(\cos(\sin\theta)+i\sin(\sin\theta)\right)\end{align}$$

We therefore have the equivalent:
$$\begin{align}\sum_{s=0}^{\infty}\frac{1}{(sn)!}&=\frac{1}{n}\sum_{r=0}^{n-1}\Re\left\{\exp\left(e^{\frac{2r\pi}{n}i}\right)\right\}\\n\sum_{s=0}^{\infty}\frac{1}{(sn)!}& = \sum_{r=0}^{n-1}\Re\left\{\exp\left(e^{\frac{2r\pi}{n}i}\right)\right\}\end{align}$$

Where $\Re\{\}$ denotes the real part.

Attempt at induction:
Assume true for $n=k$ Try to prove as a consequence it is true for $n=k+1$

$$\begin{align}\frac{1}{k+1}\sum_{r=0}^{(k+1)-1}\Re\left\{\exp\left(e^{\frac{2r\pi}{k+1}i}\right)\right\}&=\frac{1}{k+1}\sum_{r=0}^{k-1}\Re\left\{\exp\left(e^{\frac{2r\pi}{k+1}i}\right)\right\}+\frac{1}{k+1}\Re\left\{\exp e^{\left(\frac{2(k+1)\pi}{k+1}i\right)}\right\}\\& =\frac{1}{k+1}\sum_{r=0}^{k-1}\Re\left\{\exp\left(e^{\frac{2r\pi}{\color{red}{k+1}}i}\right)\right\}+\frac{1}{k+1}\exp(1)\end{align}$$

Am I along the right lines here?
I having concerns given the highlighted term in red. Specifically if this was $\color{red}{k}$ I might have a chance at the induction step.

I have taken this from a question marked as difficult with a $\dagger$ and so wanted to complete it naturally. (I'm preparing to teach harder material). Unfortunately there are no answers and so I can't even see if I'm on the right lines.

Any help would be gratefully appreciated.

Answer

An idea: the RHS is (the real part of) the average of the exponentials of $n$th-roots of unity. The LHS is a kind of lacunary series related to the exponential series. Maybe, by expanding each exponential in the RHS, many terms vanish and only one every $n$ remains.

Credible, since every $n$th term has a $n$th power of a $n$th root of unity, that is, $1$. The other corresponding terms of each series may give a permutation of the $n$th roots of unity, whose sum is zero.

---

To develop this idea, rewrite the RHS using $\omega_n=\exp(2i\pi/n)$, a primitive $n$th root of unity, for integer $n>0$.

First, your RHS is $\mathrm{Re}(S_n)$, with

$$S_n=\frac1n\sum_{r=0}^{n-1}\exp(\omega_n^r)=\frac1n\sum_{r=0}^{n-1}\left(\sum_{k=0}^\infty \frac{\omega_n^{rk}}{k!}\right)=\frac1n\sum_{k=0}^\infty\left(\frac{1}{k!} \sum_{r=0}^{n-1}\omega_n^{rk}\right)$$

(since the double sum above is absolutely convergent, you can exchange the summations)

The inner sum is, with $e_{n,k}=\omega_n^k$,

$$\sum_{r=0}^{n-1}\omega_n^{rk}=\sum_{r=0}^{n-1}e_{n,k}^r$$

If $e_{n,k}\neq1$, then the sum is

$$\frac{e_{n,k}^n-1}{e_{n,k}-1}=\frac{(\omega_n^n)^k-1}{e_{n,k}-1}=0$$

And if $e_{n,k}=1$, the sum is simply $n$.

Now, $e_{n,k}=1$ iff $\omega_n^k=1$, iff $k=pn$ for some integer $p$.

Thus, the entire sum is

$$S_n=\frac{1}{n}\sum_{k=0}^\infty \frac{u_{n,k}}{k!}$$

Where $u_{n,k}=n$ if $k=pn$ and $0$ otherwise, that is

$$S_n=\sum_{p=0}^\infty \frac{1}{(pn)!}$$

And finally,

$$\sum_{s=0}^\infty \frac{1}{(sn)!}=\frac1n\sum_{r=0}^{n-1}\exp(\omega_n^r)$$

By the way, taking the real part is not necessary, as we have also proved that $S_n$ is a real number.

---

In a comment above, I mention an interesting integral. Actually, the RHS is trivially a Riemann sum, and by letting $n\to\infty$ and estimating the rest of the LHS after the first term (which is always $1$), you get

$$\int_0^{2\pi} \exp(\cos x) \cos(\sin x) \mathrm{d}x=2\pi$$

Since we have also proved the imaginary part of $S_n$ is zero, you also get

$$\int_0^{2\pi} \exp(\cos x) \sin(\sin x) \mathrm{d}x=0$$

But this one was actually trivial: the integrand is both odd and periodic, so its integral on a period must be $0$.

Now, thinking again about this integral, putting together the real and imaginary parts, it can be rewritten $\displaystyle{\int_\Gamma \frac{e^z}{iz}\mathrm{d}z}$ ($\Gamma$ being the unit circle), and this integral is immediately $2\pi$ by the residue theorem, so it's not that interesting.

real analysis - Find all continuous functions in $0$ that $2f(2x) = f(x) + x $

I need to find all functions that they are continuous in zero and
$$ 2f(2x) = f(x) + x $$

About

I know that there are many examples and that forum but I don't understand one thing in it and I need additional explanation. (Nowhere I see similar problem :( )

My try

I take $ y= 2x$ then
$$f(y) = \frac{1}{2}f\left(\frac{1}{2}y\right) + \frac{1}{4}$$
after induction I get:
$$f(y) = \frac{1}{2^n}f\left(\frac{1}{2^n}y\right) + y\left(\frac{1}{2^2} + \frac{1}{2^4} + ... + \frac{1}{2^{2n}} \right)$$
I take $\lim_{n\rightarrow \infty} $
$$ \lim_{n\rightarrow \infty}f(y) = f(y) = \lim_{n\rightarrow \infty} \frac{1}{2^n}f\left(\frac{1}{2^n}y\right) + y\cdot \lim_{n\rightarrow \infty} \left(\frac{1}{2^2} + \frac{1}{2^4} + ... + \frac{1}{2^{2n}} \right)$$

$$f(y) = \lim_{n\rightarrow \infty} \frac{1}{2^n} \cdot f\left( \lim_{n\rightarrow \infty} \frac{1}{2^n}y \right) + \frac{1}{3}y$$

Ok, there I have question - what I should there after? How do I know that $$f(0) = 0 $$?
I think that it can be related with " continuous functions in $0$ " but
function is continous in $0$ when
$$ \lim_{y\rightarrow 0^+}f(y)=f(0)=\lim_{y\rightarrow 0^-}f(y)$$
And I don't see a reason why $f(0)=0$

edit

• Ok, I know why $f(0) =0$ but why I need informations about "Continuity at a point $0$ " ? It comes to
  $$\lim_{n\rightarrow \infty}f\left(\frac{1}{2^n}y\right) = f\left( \lim_{n\rightarrow \infty} \frac{1}{2^n}y \right)$$ ?

Answer

A powerful method to solve these kinds of problems is to reduce to a simpler equation. In this case we want to eliminate the $x$ in the right hand side. Set $g(x)=f(x)+ax$, with $a$ to be found later. Note that $f$ is continuous if and only if $g$ is. Then the equality becomes
$$2(g(2x)-a(2x))=g(x)-ax+x$$
$$2g(2x)=g(x)+x(1+3a)$$
Therefore setting $a=-\frac13$ the equality simplifies to
$$g(2x)=\frac12g(x).$$
Now plugging zero gives $g(0)=0$. You can now prove by induction that for every $x$

$$
g\left(\frac{x}{2^n}\right)=2^ng(x).\tag{1}
$$
If $g$ is not identically zero, say $g(x_0)\neq 0$, then we find a contradiction. Indeed by continuity in zero (which is still true for $g$) $g(\frac{x_0}{2^n})$ should converge to zero, while by $(1)$ it does not.

Therefore we conclude that $g$ must be identically zero, or equivalently $f(x)=\frac13 x$.