1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: Number theory. numbers of the form 111 111.

  1. Oct 20, 2009 #1
    1. The problem statement, all variables and given/known data
    consider the number m=111...1 with n digits, all ones. Prove that if m is Prime, then n is prime

    2. Relevant 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

    3. 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 [tex]\frac{10^(^P^-^1^)-1}{9}[/tex] 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.
  2. jcsd
  3. Oct 20, 2009 #2
    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

    [tex]m = \frac{10^n - 1}{9}[/tex]

    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.

  4. Oct 20, 2009 #3
    I am afraid I don't see it... here is what I have the critical step is missing.

    let [tex]m = \frac{10^n - 1}{9}[/tex] 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.
  5. Oct 20, 2009 #4


    User Avatar
    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.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook