1. Not finding help here? Sign up for a free 30min 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!

Prove for all n

  1. May 17, 2006 #1
    Prove for all n that:

    [tex]19.14^n + 1 [/tex]

    is not prime.

    I know I cant do it by induction.
     
  2. jcsd
  3. May 17, 2006 #2
    Maybe this isn't the direction that they wanted to go, but I find it sufficient to prove that the decimal 0.14^n will never end in 0 (without adding trailing 0's)
     
  4. May 18, 2006 #3
    It depends on what you want to prove.

    Do you want to prove that [itex]19*14^{n}+1[/itex] is not prime for all [itex]n[/itex]?

    or

    Do you want to prove that [itex]19*14^{n}+1[/itex] is not prime for any [itex]n[/itex]?

    If you have to prove the first part, you can assume that the expression is prime for all values of [itex]n[/itex] and find a contradiction.

    I think its the second part that you want to prove (thats why you're invoking induction).
     
  5. May 18, 2006 #4

    Curious3141

    User Avatar
    Homework Helper

    I'm confused. What do you mean by "for all n". Do you mean prove that some 'n' value exists where that expression is composite?

    That doesn't need contradiction, just a counterexample : (19)(14^1) + 1 = (3)(89):confused:

    I'm pretty sure that what's required is a proof of the latter proposition (any n).
     
    Last edited: May 18, 2006
  6. May 18, 2006 #5
    Well if I say that "prove that the number is not prime for all n", your strategy should basically be to find some value of n for which the number is not prime. This means that the statement "the number is prime for all n" is false since you have found a value of n for which it does not hold. And if it doesn't hold for at least one value, it obviously doesn't hold for all values. Do you see what I mean?

    As for the second question "prove that the number is not prime for ANY n", you have to have an exhaustive proof which proves the statement for all possible values of n. This is the tricky one.

    Feel free to get this clarified if there is any doubt...

    EDIT: the contradiction I have given (for n = 1 or 2 for example) is what you're calling the counterexample Curious3141 :approve:
     
  7. May 18, 2006 #6

    George Jones

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    Hint:

    [tex]19.14 = \frac{1914}{100}.[/tex]

    Regards,
    George
     
  8. May 18, 2006 #7

    Curious3141

    User Avatar
    Homework Helper

    Wait, wait, wait.

    Does the OP mean (integer) 19 *times* 14^n plus one

    or

    (the decimal) 19.14^n + 1 ?:uhh:

    I always assumed the former.

    BTW, I've always found that '.' = times shorthand in math to be one of the dumbest, most unnecessary sources of confusion. :grumpy:
     
  9. May 18, 2006 #8

    George Jones

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    I think you're absolutely correct. :blushing:

    I thought that since the OP went to the trouble of texing the expression,
    that \cdot would have been used for multiplication.

    Regards,
    George
     
  10. May 18, 2006 #9

    Curious3141

    User Avatar
    Homework Helper

    Actually, it's very easy to prove this by induction. Induce on odds and evens separately.

    Note that for the first few odd values of n, the number is divisible by 3. For the first few even values of n, the number is divisible by 5. We want to prove that the pattern holds true for all odd and even n separately.

    First consider the odd values of n

    Prove it for n = 1 : (19)(14) + 1 = (89)(3)

    Inductive hypothesis, for some k, 3 divides [tex](19)(14^{2k+1}) + 1[/tex], that is, [tex](19)(14^{2k+1}) + 1 = 3m[/tex] where m is an integer.

    Induction step
    [tex](19)(14^{2k+3}) + 1 = (3724)(14^{2k+1}) + 1 = (3705)(14^{2k+1}) + (19)(14^{2k+1}) + 1 = (3)((5)(247)(14^{2k+1}) + m)[/tex]

    Observe that 3705 = (3)(5)(247). Using the inductive hypothesis, that whole expression is divisible by 3.

    Do the same thing for evens.

    Prove it for n = 0 : 19+1 = 20 which is divisible by 5.

    Inductive hypothesis, for some k, 5 divides [tex](19)(14^{2k}) + 1[/tex], that is [tex](19)(14^{2k}) + 1 = 5p[/tex] where p is an integer.

    Induction step
    [tex](19)(14^{2k+2}) + 1 = (3724)(14^{2k}) + 1 = (3705)(14^{2k}) + (19)(14^{2k}) + 1 = (5)((3)(247)(14^{2k}) + p)[/tex]

    Observe that 3705 = (3)(5)(247). Using the inductive hypothesis, that whole expression is divisible by 5.

    We're done now.
     
    Last edited: May 18, 2006
  11. May 18, 2006 #10

    shmoe

    User Avatar
    Science Advisor
    Homework Helper

    When completely lost, don't be afraid to do some calculations. Factor this expression for say n=0, 1, 2, ..., 5 (or higher if need be). Do you see any pattern appearing in the factors? You should be able to make a conjecture based on this, then try to prove it.

    edit-ahh well nevermind, the answer is laid out for you now, despite you having shown no work. by the way, it's not necessary to use induction, and of course there's nothing unusual about performing induction on sequences of integers.
     
    Last edited: May 18, 2006
  12. May 18, 2006 #11

    George Jones

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    There are probably lots of ways of showing this. I spit it up into even and odd n. When n is even, I write 19 = 20 - 1 and show using induction that the original expression is divisible 5. This can also be shown by looking at last digits.

    When n is odd, I write 19 = 18 + 1 and show using induction that the original expression is divisible 3.

    Regards,
    George
     
  13. May 18, 2006 #12
    I just connected again and I couldnt believe all the responses. Thanks for all of them.
    it was to prove that for all n
    [tex] 19*14^n [/tex]
    is a not prime number.

    A hint was to use [tex]
    \equiv \bmod 3,mod5 [/tex]

    I knew there were different ways to work this out at first but I couldnt find any with induction. I have always difficulties with finding patterns.
     
    Last edited: May 18, 2006
  14. May 19, 2006 #13

    HallsofIvy

    User Avatar
    Staff Emeritus
    Science Advisor

    Oh, c'mon! You corrected the "19.14" versus "19*14" confusion but you forgot the "+ 1"!! Of course, 19*14n is never prime for n a positive interger- it's divisible by 19!

    You want to show that 19*14n+ 1 is never a prime number. You might want to look at what happens for n even and n odd separately.

    For example, 19*141+ 1= 267= 3(89) and so is divisible by 3 (i.e. is congruent to 0 mod 3). Can you show that if 19*142n+1+ 1 is divisible by 3 then so is 19*142(n+1)+1+1?
     
  15. May 19, 2006 #14
    sorry I did forget +1
     
    Last edited: May 19, 2006
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?