Number theory. numbers of the form 111 111.

  • Thread starter cap.r
  • Start date
  • #1
67
0

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 [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.
 

Answers and Replies

  • #2
Petek
Gold Member
364
9
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.

Petek
 
  • #3
67
0
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.
 
  • #4
Dick
Science Advisor
Homework Helper
26,260
619
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.
 

Related Threads on Number theory. numbers of the form 111 111.

  • Last Post
Replies
2
Views
1K
Replies
5
Views
1K
Replies
9
Views
1K
  • Last Post
Replies
1
Views
1K
  • Last Post
Replies
2
Views
718
  • Last Post
Replies
4
Views
939
  • Last Post
Replies
2
Views
1K
  • Last Post
Replies
2
Views
967
  • Last Post
Replies
5
Views
865
Top