Number theory. numbers of the form 111 111.

[cap.r]

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 let's 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.

 

[Petek]

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

 

[cap.r]

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 = P₁^k₁*...*P_r^k_r so now m=((10^P₁^k₁)^..^P_r^k_r-1)/9

since m is prime...

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

 

[Dick]

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.