# Number theory. numbers of the form 111 111.

## Homework Statement

consider the number m=111...1 with n digits, all ones. Prove that if m is Prime, then n is prime

## Homework Equations

def of congruence. fermat's and euler's theorem. can also use σ(n): the sum of all the positive divisors of n, d(n): the number of positive divisors of n, φ(n): Euler's totient function φ, counting the positive integers coprime to (but not bigger than) n

## The Attempt at a Solution

I managed to prove that every odd prime except 5 divides on of these numbers.

3|111 so lets look at P>5 which do not divide 10.
now all such numbers can be represented by $$\frac{10^(^P^-^1^)-1}{9}$$ using fermat's theorem I can say this is congruent to 0(mod P). so now every prime P that i plug into this will give me a one of these numbers. obviously it doesn't work with non primes since we used fermat's little theorem.

so now i don't know what to do exactly.... if m is prime then i know it's not one of these numbers and the sum of it's digits is odd. but i am stuck.

## Answers and Replies

Petek
Gold Member
Your attempted solution ("I managed to prove that every odd prime except 5 divides on of these numbers." and so on) doesn't really address what you need to prove. Try a proof by contradiction. Observe that

$$m = \frac{10^n - 1}{9}$$

The hypothesis is that m is prime. Now assume that n is composite and derive a contradiction.

Let me know if this suggestion isn't clear, or if you'd like more help.

Petek

I am afraid I don't see it... here is what I have the critical step is missing.

let $$m = \frac{10^n - 1}{9}$$ assume m is a prime with n digits.
now i assume n is not prime so n = P1k1*...*Prkr so now m=((10^P1k1)^..^Prkr-1)/9

since m is prime...

sorry i couldn't get it to show up right in latex.

Dick
Science Advisor
Homework Helper
Look at it this way. If n is not prime, then there is a k that divides n. Then doesn't 11...1 with k ones divide m? You can write out the factorization.