Divisors of 999...9999 in the "right way"

I studied something after making that crazy thing. This time I will use the Euler's theorem which states that, if two positive integers aa and bb are relatively prime to themselves, then:

aϕ(b)1modba^{\phi(b)}\equiv1\bmod {b}

Where ϕ(b)\phi(b) is the Euler's totient function, which returns the size of the set S\mathbb{S}, where S={xNgcd(b,x)=1 and x<b}\mathbb{S}=\{x\in\mathbb{N}|\text{gcd}(b, x)=1\text{ and }x<b\}

This is true for a=10a=10 and bb is a number that it is not a multiple of 2, nor 5. Therefore:

b10ϕ(b)1=999....999b\mid 10^{\phi(b)}-1=999....999

I should alert anyone reading this that ϕ(b)\phi(b) does not need to be the smallest positive integer that will make this work, let b=3b=3:

310ϕ(3)1=1021=993|10^{\phi(3)}-1=10^2-1=99

But:

39=10113|9=10^1-1

However, we can expand this concept to sequences of other numbers; Writing this in another way, calling ϕ(b)=n\phi(b)=n because I already showed that a "nn" exists under what conditions:

kb=10n1,kNkb=10^n-1, k\in\mathbb{N}^*

I will multiply this by s=1+10n+102n+...+108n=k=0810kns=1+10^{n}+10^{2n}+...+10^{8n}=\sum^8_{k=0}10^{kn}, notice that s is a multiple of 9; This can be proved this way:

k=0810knk=08(109)knk=081knk=08191mod9\sum^8_{k=0}10^{kn}\equiv\sum^8_{k=0}(10-9)^{kn}\equiv\sum^8_{k=0}1^{kn}\equiv\sum^8_{k=0}1\equiv9\equiv1\bmod{9}

Therefore s=9t,tNs=9t, t\in\mathbb{N}^*

Multiplying both the two equations and using telescopic sums:

skb=(10n1)×k=0810knskb=(10^n-1)\times\sum^8_{k=0}10^{kn}

skb=10n×k=0810knk=0810knskb=10^n\times\sum^8_{k=0}10^{kn}-\sum^8_{k=0}10^{kn}

skb=k=1910knk=0810knskb=\sum^9_{k=1}10^{kn}-\sum^8_{k=0}10^{kn}

skb=k=1910knk=0810knskb=\sum^9_{k=1}10^{kn}-\sum^8_{k=0}10^{kn}

skb=109n1=999...999skb=10^{9n}-1=999...999

Remeber that s=9ts=9t

9tkb=999...9999tkb=999...999

tkb=111...111tkb=111...111

Since t,kNt, k \in\mathbb{N}^*, tkNtk\in\mathbb{N}^*; Therefore (b{xN)(2b5b}f,nNfb=k=0n10k)(\forall b\in\{x\in\mathbb{N})(2\nmid b \wedge 5\nmid b\}\exists f,n\in\mathbb{N}^* | fb=\sum^{n}_{k=0}10^k)

Just to make this complete, if 2b2\mid b or 5b5\mid b, let b=2α5βc,2c,5c,cNb=2^\alpha5^\beta c, 2\nmid c, 5\nmid c, c\in\mathbb{N}^*, γ=max(α,β)\gamma=\max(\alpha,\beta)

Multiply everything by z=10γ2α5βz=10^\gamma2^{-\alpha}5^{-\beta}, note that this number is natural;

bz=10γcbz=10^{\gamma}c

Note that cc meets the conditions that allow me do this:

kc=k=0n10kkc=\sum^n_{k=0}10^k

Multiplying by k the first equation:

bzk=10γk=0n10k=k=0n10k+γ=k=γn+γ10kbzk=10^\gamma\sum^n_{k=0}10^k=\sum^n_{k=0}10^{k+\gamma}=\sum^{n+\gamma}_{k=\gamma}10^k

This means I can generalize my result:

bNl,m,nNbl=k=nm10k\forall b\in\mathbb{N}^*\exists l, m, n\in\mathbb{N}|bl=\sum^{m}_{k=n}10^k

I can generalize even more, using another base system:

Remember the Euler's theorem if a and b are co-prime :

aϕ(b)1modba^{\phi(b)}\equiv1\bmod {b}

Rewriting, with ϕ(b)=n\phi(b)=n:

bk=an1=(a1)(a1)(a1)....(a1)(a1)(a1)bk=a^n-1= \overline{(a-1)(a-1)(a-1)....(a-1)(a-1)(a-1)}

Imagine that each (a-1) is a digit;

I will multiply everything by c=k=0a2ankc=\sum^{a-2}_{k=0}a^{nk}, but first I will prove that this a multiple of a1a-1

k=0a2ankk=0a2(a(a1))nkk=0a21nkk=0a21a10moda1\sum^{a-2}_{k=0}a^{nk}\equiv\sum^{a-2}_{k=0}(a-(a-1))^{nk}\equiv\sum^{a-2}_{k=0}1^{nk}\equiv\sum^{a-2}_{k=0}1\equiv a-1\equiv 0\bmod {a-1}

bck=(an1)k=0a2ankbck=(a^n-1)\sum^{a-2}_{k=0}a^{nk}

bck=ank=0a2ankk=0a2ankbck=a^n\sum^{a-2}_{k=0}a^{nk}-\sum^{a-2}_{k=0}a^{nk}

bck=k=1a1ankk=0a2ankbck=\sum^{a-1}_{k=1}a^{nk}-\sum^{a-2}_{k=0}a^{nk}

bck=an(a1)1=(a1)(a1)(a1)....(a1)(a1)bck=a^{n(a-1)}-1=\overline{(a-1)(a-1)(a-1)....(a-1)(a-1)}

As I proved before c=d(a1),dNc=d(a-1), d\in\mathbb{N}^*

(a1)bdk=(a1)(a1)(a1)....(a1)(a1)(a-1)bdk=\overline{(a-1)(a-1)(a-1)....(a-1)(a-1)}

bdk=(111...111)abdk=(111...111)_a

Since dkNdk\in\mathbb{N}^*, I can say:

(b,aN)(gcd(a,b)=1n,fbf=k=0nak)(\forall b, a\in\mathbb{N}^*)(\text{gcd}(a,b)=1\Leftrightarrow\exists n, f|bf=\sum^n_{k=0} a^k)

The other way can be proven by observing:

bf1modabf\equiv1\mod a

This means bfka=1,kNbf-ka=1, k\in\mathbb{N}, with this in mind, I will prove that gcd(a,b)=L\text{gcd}(a,b)=L must be 1:

bL=b,aL=ab'L=b, a'L=a

a,bNa',b'\in\mathbb{N}

Doing a substitution

bLfaLk=1b'Lf-a'Lk=1

L(bfak)=1L(b'f-a'k)=1

As both of the factors are positive integers, both of them are 1

Now I will study the case where gcd(a,b)1\text{gcd}(a,b)\neq1

I will consider the prime factorization of aa:

a=j=1zpjaja=\prod^z_{j=1}p_j^{a_j}

pjp_j is the jj-th prime, aja_j is its exponent, zz is the largest number that makes az0a_z\neq0

I will make b=cj=1npjbjb=c\prod^n_{j=1}p_j^{b_j}, this time (j)(aj0pjc)(aj=0bj=0)(\forall j)(a_j\neq0\Leftrightarrow p_j\nmid c)\wedge(a_j=0\Rightarrow b_j=0)

Let γ=max({xNx=bjajjNaj0})\gamma=\max(\{x\in\mathbb{N}^*|x=\left\lceil\frac{b_j}{a_j}\right\rceil j\in\mathbb{N}\wedge a_j\neq0\})

I will multiply everything by d=aγj=1npjbjd=a^\gamma\prod^n_{j=1}p_j^{-b_j}, notice that this number is a natural number

bd=aγcbd=a^\gamma c

Since gcd(a,c)=1\text{gcd}(a,c)=1, I can say that

ck=j=0najck=\sum^n_{j=0}a^j

Multiplying k on every side of the other equation:

bdk=aγckbdk=a^\gamma ck

Substituting ckck:

bdk=aγj=0najbdk=a^\gamma \sum^n_{j=0}a^j

bdk=aγj=0naj+γbdk=a^\gamma \sum^n_{j=0}a^{j+\gamma}

bdk=j=γn+γajbdk=\sum^{n+\gamma}_{j=\gamma}a^j

Since dkNdk\in\mathbb{N}^* I can say that(finally):

(a,bN)(k,m,nN)(bk=j=nmaj)(\forall a,b\in\mathbb{N}^*)(\exists k,m,n\in\mathbb{N}^*)(bk=\sum^m_{j=n}a^j)

#NumberTheory

Note by Matheus Jahnke
4 years, 2 months ago

No vote yet
1 vote

  Easy Math Editor

This discussion board is a place to discuss our Daily Challenges and the math and science related to those challenges. Explanations are more than just a solution — they should explain the steps and thinking strategies that you used to obtain the solution. Comments should further the discussion of math and science.

When posting on Brilliant:

  • Use the emojis to react to an explanation, whether you're congratulating a job well done , or just really confused .
  • Ask specific questions about the challenge or the steps in somebody's explanation. Well-posed questions can add a lot to the discussion, but posting "I don't understand!" doesn't help anyone.
  • Try to contribute something new to the discussion, whether it is an extension, generalization or other idea related to the challenge.
  • Stay on topic — we're all here to learn more about math and science, not to hear about your favorite get-rich-quick scheme or current world events.

MarkdownAppears as
*italics* or _italics_ italics
**bold** or __bold__ bold

- bulleted
- list

  • bulleted
  • list

1. numbered
2. list

  1. numbered
  2. list
Note: you must add a full line of space before and after lists for them to show up correctly
paragraph 1

paragraph 2

paragraph 1

paragraph 2

[example link](https://brilliant.org)example link
> This is a quote
This is a quote
    # I indented these lines
    # 4 spaces, and now they show
    # up as a code block.

    print "hello world"
# I indented these lines
# 4 spaces, and now they show
# up as a code block.

print "hello world"
MathAppears as
Remember to wrap math in \( ... \) or \[ ... \] to ensure proper formatting.
2 \times 3 2×3 2 \times 3
2^{34} 234 2^{34}
a_{i-1} ai1 a_{i-1}
\frac{2}{3} 23 \frac{2}{3}
\sqrt{2} 2 \sqrt{2}
\sum_{i=1}^3 i=13 \sum_{i=1}^3
\sin \theta sinθ \sin \theta
\boxed{123} 123 \boxed{123}

Comments

There are no comments in this discussion.

×

Problem Loading...

Note Loading...

Set Loading...