home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #18 / NN_1992_18.iso / spool / sci / math / 10422 < prev    next >
Encoding:
Internet Message Format  |  1992-08-19  |  2.9 KB
  1. Path: sparky!uunet!dtix!darwin.sura.net!jvnc.net!nuscc!bhonsle!bhonsle
  2. From: bhonsle@bhonsle.iss.nus.sg (Shailendra K Bhonsle)
  3. Newsgroups: sci.math
  4. Subject: Re: u(v^n)w prime puzzle - HINTS
  5. Message-ID: <1992Aug20.043232.5087@nuscc.nus.sg>
  6. Date: 20 Aug 92 04:32:32 GMT
  7. References: <1992Aug19.194149.24353@wri.com>
  8. Sender: bhonsle@bhonsle (Shailendra K Bhonsle)
  9. Organization: Institute of Systems Science, NUS, Singapore
  10. Lines: 101
  11.  
  12. In article <1992Aug19.194149.24353@wri.com>, roach@bikini.wri.com (Kelly Roach) writes:
  13. |> 
  14. |> 
  15. |> 
  16. |>       Prove or disprove:  There are three non-empty
  17. |>       strings of digits u,v,w such that all the
  18. |>       numbers in
  19. |>            L = {u(v^n)w | n is a natural number}
  20. |>              = {uw, uvw, uvvw, uvvvw, uvvvvw, ...}
  21. |>       are prime numbers.
  22. |> 
  23. |> 
  24. |>             HINT TIME!!!
  25. |> 
  26. |>      This is the puzzle I posted Monday.  Today I'll
  27. |> give out some hints.  On Friday, I'll explain the
  28. |> solution if I can't get anyone to solve the problem
  29. |> before then.
  30. |> 
  31. |>      HINTS:
  32. |>       
  33. |>      (1) Fermat's Little Theorem says
  34. |>      
  35. |>      c^(p-1) = 1 (mod p)
  36. |> 
  37. |> if p is prime and (c,p)=1.
  38. |>      (2) Let a=|v|=length of v, b=|w|=length of w.
  39. |> Then
  40. |> 
  41. |>      u(v^n)w = u*10^(a*n+b) + v*Sum[10^(a*i+b),{i,0,n-1}] + w
  42. |> 
  43. |> Consider the two pieces
  44. |> 
  45. |>      u*10^(a*n+b) + w
  46. |>      
  47. |>      v*Sum[10^(a*i+b),{i,0,n-1}]
  48. |> 
  49. |> separately.
  50. |>      (3) If prime number p does not divide 10, then
  51. |>      
  52. |>      10^(a*i+b) (mod p)
  53. |> 
  54. |> is a periodic function of i.
  55. |>      (4) If uw is not a prime, there is not much to prove.
  56. |> Might as well assume uw is a prime number.
  57. |> 
  58. |> 
  59. |> 
  60.  
  61. -- 
  62. As I mentioned in my last article let us take prime p="uw".
  63.  
  64. Let's call the first piece as I and the second piece as J.
  65.  
  66. step 1: p=u*10^(b)+w
  67.         I=u*10^(b)*10^(a*n) + w
  68.      ==> I= u*10^(b) +w +u*10^(b)*{10^(an) -1}
  69.      ==> I= p + u*10^(b)*{10^(an) -1} 
  70.  
  71. step 2: Either 10^(a)==1(mod p) or choose n such that n=p-1
  72.    ==> p divides I
  73.        and  10^(an) == 1(mod p)    { Fermat's Little Theorem }
  74.  
  75.  
  76.  
  77. step 3:
  78.        J=  v*Sum[10^(a*i+b),{i,0,n-1}]
  79.       ==> J= v*10^b [ 1 + 10^a + 10^(2a) + ... + 10^((n-1)a)]
  80.       ==> J= [v*10^b {10^(an) -1}]/[10^a - 1]
  81.        Since from step 2 10^(an) -1 is divisible by p
  82.       ==> If 10^a-1 is not divisible by p then J is divisible by p
  83.  
  84.  
  85. So we have proved so far that if p does not divide 10^a - 1 then pdivides J.
  86. And in this case it is not possible to have such triples {u,v,w}.
  87.  
  88. Now we show that p cannot divide 10^a -1 to complete the proof.
  89.  
  90.  
  91.  
  92. step 4:
  93.         Assume p divides 10^a - 1
  94.        p= u*10^b +w
  95.  
  96.  
  97.     case 1: b > a
  98.            let b=l* a + k   k<b
  99.             ==> 10^b== 10^k (mod p)
  100.             ==> p divides u*10^k +w
  101.            But this is not possible since u*10^k + w < u*10^b + w =p
  102.            So in this case p does not divide 10^a - 1
  103.     
  104.      case 2: b <= a
  105.              SIMPLE, Can you do it ?
  106.  
  107. So we complete the proof.
  108.  
  109.  
  110.  
  111.  
  112. Shailendra
  113.