-1

I have looked in some of my old books and found an exericse that I do not know how to solve. It seems pretty simple though.

The question is as follows:

Which of these integers are prime?:

111
111.1
111.111
111.111.11
111.111.111
111.111.111.1
111.111.111.111

I remember one rule of thumb saying that if the sum of integers mod 9 were 0,3 or 9, then you could know for sure that the not number was NOT prime.

But for numbers such as this, is there any way of checking whether the number is actually prime?

Grazosi
  • 101
  • 3
    Hint: There is something similar for multiples of eleven – JMoravitz Jan 31 '22 at 22:46
  • 1
    Hint: another necessary condition is that the number of $1$'s itself is prime. Say, $111,111=111\times 1001$ –  Jan 31 '22 at 22:53
  • 1
    Also, you can exclude. $6\pmod 9.$ – Thomas Andrews Jan 31 '22 at 22:59
  • 3
    This is very strange notation. Usually, we add the commas like 1,111 or 111,111,111. If you are not doing anything unusual, why write this way? – Thomas Andrews Jan 31 '22 at 23:00
  • hm, im a bit unsure as to what "number of 1's itself is prime" means. So I can know that 1234 is not prime because there are four digits? – Grazosi Jan 31 '22 at 23:03
  • @JMoravitz youre probably right, but I can't see how they are related – Grazosi Jan 31 '22 at 23:04
  • @Grazosi "number of 1's itself is prime" was in reference very specifically to numbers of the form $\underbrace{11111\cdots 1}{\text{nothing but 1's}}$, and the proof is constructive, that if you had a composite number $a\cdot b$ of $1$'s then you would have $\underbrace{111\cdots 1}{a\cdot b~1's} = \underbrace{11\cdots 1}{a~1's}\cdot \underbrace{\overbrace{10\cdots00}^{a-1~0's}\overbrace{10\cdots00}^{a-1~0's}\cdots \overbrace{10\cdots00}^{a-1~0's}\overbrace{1}}{b~\text{blocks}}$ – JMoravitz Feb 01 '22 at 00:49
  • Note that the repunits (the name of numbers of this form) are usually difficult to be checked for primality. What helps is (as mentioned) that $\frac{10^n-1}{9}$ (in decimal expansion this is just $n$ ones) can only be prime if $n$ is prime. Only a few primes of this form are known. – Peter Feb 01 '22 at 11:55

2 Answers2

0

The check for divisibility by eleven is to alternately add and subtract the digits of the number from right to left starting with adding. The result will be the same modulo 11 as the original number.

For example, just picking a number at random $316833\mapsto -3+1-6+8-3+3=0$ therefore $316833$ is a multiple of eleven. ($11\cdot 28803$)

On the other hand, $545657\mapsto -5+4-5+6-5+7 = 2$ so $545657$ is two more than a multiple of eleven. ($11\cdot 49605+2$)

If the sum is too large, just repeat it again until it becomes small enough: $506070809\mapsto 5-0+6-0+7-0+8-0+9=35\mapsto -3+5=2$ so $506070809$ is two more than a multiple of eleven. ($11\cdot 46006437+2$)

All of your numbers here have either a multiple of three number of $1$ digits (and nothing else) and so is a multiple of three, or has an even number of $1$ digits (and nothing else) and so have alternating sums of $(-1+1)+(-1+1)+\dots=0+0+\dots=0$ and so is a multiple of $11$.

JMoravitz
  • 79,518
  • This seems like an economic approach. I do have a couple of questions for your it though. So you collect all the digits alternating between subtracting them and adding them. It is unclear to me why doing this proves whether or not it is a multiple of 11? – Grazosi Jan 31 '22 at 23:28
  • and the numbers 28803 and 49605, where do they ciome from? – Grazosi Jan 31 '22 at 23:31
  • it does seem to check out, but I can't find anywhere online about this method of checking for multiples of 11, can you link it to me? – Grazosi Jan 31 '22 at 23:43
  • "Where do they (28803 49605) come from?" Found via a calculator, performing 316833/11 as verification of the claim that 316833 was a multiple of eleven. As for proof of the statement, it follows from $1,100,10000, \dots, 10^{2k+1},\dots$ all being one more than multiples of eleven (seen quickly by looking at $99\cdot 10101\cdots01$) and $10,1000,\dots,10^{2k},\dots$ being one less than multiples of eleven. https://math.stackexchange.com/questions/4261965/proof-of-the-divisibility-rule-of-11 – JMoravitz Feb 01 '22 at 00:43
0

$\underbrace {111\cdots 1}_{n-times} = \frac {10^n-1}{9}$

If $n$ is composite, i.e. $n = ab$ then $10^a - 1|10^n-1$ and $10^b-1|10^n-1.$ That is $10^n-1 = (10^a - 1)(10^{n-a} + 10^{n-2a} + \cdots + 10^{a} + 1)$

This all goes to say

$\underbrace {111\cdots 1}_{n-times}$ can only be prime is $n$ is prime.

user317176
  • 11,017