Skip to content

Instantly share code, notes, and snippets.

@mmun

mmun/math

Last active August 29, 2015 14:07
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save mmun/156c3763901db807645b to your computer and use it in GitHub Desktop.
Save mmun/156c3763901db807645b to your computer and use it in GitHub Desktop.
Download ZIP
math
Raw
math
## Problem
Let $b_0 = 1, b_{n+1} = b_n$. What is $b_n \bmod 10^k?$
## Solution (partial)
Let $\varphi_0 = 10^k$ and $\varphi_{n+1} = \varphi(\varphi_n)$.
Let $d_n = \gcd(b, \varphi_n)$ and $t_n = \varphi_n / d_n$.
$b_{n+1} \bmod = b^{b_n} \bmod \varphi_0$
$b_{n+1} \bmod = (d_0^{b_n} \bmod \varphi_0) (t_0^{b_n} \bmod \varphi_0) \bmod \varphi_0$
$b_{n+1} \bmod = (d_0^{b_n} \bmod \varphi_0) (t_0^{b_n \bmod \varphi_1} \bmod \varphi_0) \bmod \varphi_0$
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment