# Thread: modular arithmetic and prime number

1. ## 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.

2. ## Re: modular arithmetic and prime number

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.

3. ## 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.

4. ## 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.

5. ## Re: modular arithmetic and prime number

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?

6. ## 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

7. ## Re: modular arithmetic and prime number

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.