# modular arithmetic and prime number

• Jun 6th 2012, 07:04 AM
snseng
modular arithmetic and prime number
Hi,
I have spent hours on this question:- For what positive integers n is 4n+ 7 2n+1 + 103n-1 aprime number?.... no clue on how to tackle it. I appreciate if someonecould help.
• Jun 6th 2012, 07:33 AM
Sarasij
Re: modular arithmetic and prime number
Quote:

Originally Posted by snseng
Hi,
I have spent hours on this question:- For what positive integers n is 4n+ 7 2n+1 + 103n-1 aprime number?.... no clue on how to tackle it. I appreciate if someonecould help.

I claim that the sum S = 4n + 72n+1 + 103n-1 is always divisible by 3 for any n and is not a prime for all natural number n.

Proof:
4n is of the form 3x + 1 i.e. 4n = 3x + 1
72n+1 = (3x2 + 1)2n+1 = 3y + 1 &
103n-1 = (3x3 + 1)3n-1 = 3z + 1

So S = (3x+1) + (3y+1) + (3z+1) = 3(x + y + z + 1) => 3|S.

Hence proved.
• Jun 6th 2012, 08:12 AM
snseng
Re: modular arithmetic and prime number
Hi Sarasij,

Thanks so much for your speedy response.

In fact, I got the similar outcome that the expression is dividable by 3. This question was given by the school to my kid. I have spent a morning to learn from scratch about Modular Arithmetic and not much confidence on it. At the same time, I do not expect such a 'naughty' question as I presumed 'n' shall exist some positive integers... keep on trying. Ha Ha, interesting!

Have a good night/day.
• Jun 6th 2012, 11:59 AM
Deveno
Re: modular arithmetic and prime number
modular arithmetic is the perfect tool for investigating things concerning divisibilty (and thus about primes, for example).

the nice thing about it is that:

a (mod n) + b (mod n) = a+b (mod n), and:
(a mod n)(b mod n) = ab (mod n)

so it doesn't matter if you reduce mod n before or after adding (or multiplying).

so we have:

4 = 1 (mod 3)
7 = 1 (mod 3)
10 = 1 (mod 3)

therefore:

4n + 72n+1 + 103n-1

≡ (1)n + (1)2n+1 + (1)3n-1 (mod 3)

≡ 1 + 1 + 1 (mod 3)

≡ 0 (mod 3), thus we have 4n + 72n+1 + 103n-1 is divisible by 3.

one can also attempt an induction proof, that 4n + 72n+1 + 103n-1 is divisible by 3 for all natural numbers n.

base case: n = 1:

4 + 73 + 102 = 4 + 343 + 100 = 447 = 3*149.

assume that:

4k + 72k+1 + 103k-1 = 3x, for some positive integer x.

then:

4k+1 + 72k+3 + 103k+2 =

(4k+1 - 4k) + (72k+3 - 72k+1) + (103k+2 - 103k-1) + 4k + 72k+1 + 103k-1

= 4k(4 - 1) + 72k+1(72 - 1) + 103k-1(103 - 1) + 3x <---by our induction hypothesis

= 4k(3) + 72k+1(48) + 103k-1(999) + 3x

= 3[4k + (72k+1)(16) + (103k-1)(333)] + 3x

= 3y + 3x = 3(y + x), for y = 4k + (72k+1)(16) + (103k-1)(333)

and is therefore true for all n.
• Jun 6th 2012, 08:13 PM
Sarasij
Re: modular arithmetic and prime number
Quote:

Originally Posted by Deveno
modular arithmetic is the perfect tool for investigating things concerning divisibilty (and thus about primes, for example).

the nice thing about it is that:

a (mod n) + b (mod n) = a+b (mod n), and:
(a mod n)(b mod n) = ab (mod n)

so it doesn't matter if you reduce mod n before or after adding (or multiplying).

so we have:

4 = 1 (mod 3)
7 = 1 (mod 3)
10 = 1 (mod 3)

therefore:

4n + 72n+1 + 103n-1

≡ (1)n + (1)2n+1 + (1)3n-1 (mod 3)

≡ 1 + 1 + 1 (mod 3)

≡ 0 (mod 3), thus we have 4n + 72n+1 + 103n-1 is divisible by 3.

one can also attempt an induction proof, that 4n + 72n+1 + 103n-1 is divisible by 3 for all natural numbers n.

base case: n = 1:

4 + 73 + 102 = 4 + 343 + 100 = 447 = 3*149.

assume that:

4k + 72k+1 + 103k-1 = 3x, for some positive integer x.

then:

4k+1 + 72k+3 + 103k+2 =

(4k+1 - 4k) + (72k+3 - 72k+1) + (103k+2 - 103k-1) + 4k + 72k+1 + 103k-1

= 4k(4 - 1) + 72k+1(72 - 1) + 103k-1(103 - 1) + 3x <---by our induction hypothesis

= 4k(3) + 72k+1(48) + 103k-1(999) + 3x

= 3[4k + (72k+1)(16) + (103k-1)(333)] + 3x

= 3y + 3x = 3(y + x), for y = 4k + (72k+1)(16) + (103k-1)(333)

and is therefore true for all n.

Hi Devono,
Actually I don't know how to write the congruent modulo sign here. So that's why I explained the logic to him using only division algorithm. But it becomes much more simpler if I use this operator(congruent modulo). Can you please tell me how to use it in this forum?
• Jun 7th 2012, 05:20 PM
Deveno
Re: modular arithmetic and prime number
there are two ways:

1. Use a unicode-based symbol (which you could do by copying and pasting this: ≡)

2. use latex (on this forum the latex tag is [tex ][/tex] (but without the space). in latex, the code for the modulus congruence sign is: \equiv such as:

$2 \equiv 6\ \text{mod }4$

what is inside the latex tags is:

2 \equiv 6\ \text{mod }4
• Jun 7th 2012, 10:25 PM
Sarasij
Re: modular arithmetic and prime number
Quote:

Originally Posted by Deveno
there are two ways:

1. Use a unicode-based symbol (which you could do by copying and pasting this: ≡)

2. use latex (on this forum the latex tag is [tex ][/tex] (but without the space). in latex, the code for the modulus congruence sign is: \equiv such as:

$2 \equiv 6\ \text{mod }4$

what is inside the latex tags is:

2 \equiv 6\ \text{mod }4

Thank you so much Devono.