Summation with Number theory

by fungarwai, May 23, 2019, 12:59 PM

Summation of divisor

$\sum_{1\le d\le n\atop d|n} d^x=\prod_{i=1}^m \sum_{j=0}^{k_i} p_i^{jx}=
\begin{cases} \prod_{i=1}^m (1+k_i) & x=0\\
\prod_{i=1}^m \frac{p_i^{(k_i+1)x}-1}{p_i^x-1} & x>0\end{cases}$

Summation of coprime set

Refer Page 25 from Introduction to Analytic Number Theory (A.J. Hildebrand)

$\displaystyle\sum_{1\le m\le n\atop (m,n)=1}f(m)
=\sum_{1\le m\le n}f(m)e((m,n))
=\sum_{1\le m\le n}f(m)\sum_{d|(m,n)}\mu(d)$
$\displaystyle
=\sum_{d|n}\mu(d)\sum_{1\le m\le n\atop d|m}f(m)
=\sum_{d|n}\mu(d)\sum_{1\le k\le \frac{n}{d}}f(dk)$

where $e(n)=\begin{cases}1 & n=1\\0 & \text{otherwise}\end{cases}$

$\varphi(n)=\sum_{1\le m\le n\atop (m,n)=1}1=n\prod_{p|n}\left(1-\frac{1}{p}\right)$

Proof

$\sum_{1\le m\le n\atop (m,n)=1}m=\frac{n}{2}\left(e(n)+\varphi(n)\right)$

Proof

$\displaystyle\sum_{1\le m\le n\atop (m,n)=1}m^2
=\frac{n}{6}\prod_{p|n}(1-p)+\frac{n^2}{2}e(n)+\frac{n^2}{3}\varphi(n)$

Proof

Summation of GCD or LCM

$\sum_{n=1}^N (n,N)=\prod_{i=1}^m p_i^{k_i-1}(p_i+k_i(p_i-1))$

Proof

Example

$\sum_{n=1}^N [n,N]=\frac{N}{2}\left(1+\prod_{i=1}^m\frac{p_i^{2k_i+1}+1}{p_i+1}\right)$

Proof

Example
This post has been edited 4 times. Last edited by fungarwai, Apr 22, 2024, 11:18 AM

Comment

0 Comments

Notable algebra methods with proofs and examples

avatar

fungarwai
Shouts
Submit
  • Nice blog!

    by Inconsistent, Mar 18, 2024, 2:41 PM

  • hey, nice blog! really enjoyed the content here and thank you for this contribution to aops. Sure to subscribe! :)

    by thedodecagon, Jan 22, 2022, 1:33 AM

  • thanks for this

    by jasperE3, Dec 3, 2021, 10:01 PM

  • I am working as accountant and studying as ACCA student now.
    I graduated applied mathematics at bachelor degree in Jinan University but I still have no idea to find a specific job with this..

    by fungarwai, Aug 28, 2021, 4:54 AM

  • Awesome algebra blog :)

    by Euler1728, Mar 22, 2021, 5:37 AM

  • I wonder if accountants need that kind of math tho

    by Hamroldt, Jan 14, 2021, 10:55 AM

  • Nice!!!!

    by Delta0001, Dec 12, 2020, 10:20 AM

  • this is very interesting i really appericate it :)

    by vsamc, Oct 29, 2020, 4:42 PM

  • this is god level

    by Hamroldt, Sep 4, 2020, 7:48 AM

  • Super Blog! You are Pr0! :)

    by Functional_equation, Aug 23, 2020, 7:43 AM

  • Great blog!

    by freeman66, May 31, 2020, 5:40 AM

  • cool thx! :D

    by erincutin, May 18, 2020, 4:55 PM

  • How so op???

    by Williamgolly, Apr 30, 2020, 2:42 PM

  • Beautiful

    by Al3jandro0000, Apr 25, 2020, 3:11 AM

  • Nice method :)

    by Feridimo, Jan 23, 2020, 5:05 PM

  • This is nice!

    by mufree, May 26, 2019, 6:40 AM

  • Wow! So much Algebra.

    by AnArtist, Mar 15, 2019, 1:19 PM

  • :omighty: :omighty:

    by AlastorMoody, Feb 9, 2019, 5:17 PM

  • 31415926535897932384626433832795

    by lkarhat, Dec 25, 2018, 11:53 PM

  • rip 0 shouts and 0 comments until now

    by harry1234, Nov 17, 2018, 8:56 PM

20 shouts
Tags
About Owner
  • Posts: 859
  • Joined: Mar 11, 2017
Blog Stats
  • Blog created: Sep 15, 2018
  • Total entries: 18
  • Total visits: 5839
  • Total comments: 8
Search Blog
a