Thread: modular arithmetic and prime number

Hi,
I have spent hours on this question:- For what positive integers n is 4ⁿ+ 7 ²ⁿ⁺¹ + 10^3n-1 aprime number?.... no clue on how to tackle it. I appreciate if someonecould help.

Originally Posted by snseng

Hi,
I have spent hours on this question:- For what positive integers n is 4ⁿ+ 7 ²ⁿ⁺¹ + 10^3n-1 aprime number?.... no clue on how to tackle it. I appreciate if someonecould help.

I claim that the sum S = 4ⁿ + 7²ⁿ⁺¹ + 10^3n-1 is always divisible by 3 for any n and is not a prime for all natural number n.

Proof:
4ⁿ is of the form 3x + 1 i.e. 4ⁿ = 3x + 1
7²ⁿ⁺¹ = (3x2 + 1)²ⁿ⁺¹ = 3y + 1 &
10^3n-1 = (3x3 + 1)^3n-1 = 3z + 1

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

Hence proved.

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.

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:

4ⁿ + 7²ⁿ⁺¹ + 10^3n-1

≡ (1)ⁿ + (1)²ⁿ⁺¹ + (1)^3n-1 (mod 3)

≡ 1 + 1 + 1 (mod 3)

≡ 0 (mod 3), thus we have 4ⁿ + 7²ⁿ⁺¹ + 10^3n-1 is divisible by 3.

one can also attempt an induction proof, that 4ⁿ + 7²ⁿ⁺¹ + 10^3n-1 is divisible by 3 for all natural numbers n.

base case: n = 1:

4 + 7³ + 10² = 4 + 343 + 100 = 447 = 3*149.

assume that:

4^k + 7^2k+1 + 10^3k-1 = 3x, for some positive integer x.

then:

4^k+1 + 7^2k+3 + 10^3k+2 =

(4^k+1 - 4^k) + (7^2k+3 - 7^2k+1) + (10^3k+2 - 10^3k-1) + 4^k + 7^2k+1 + 10^3k-1

= 4^k(4 - 1) + 7^2k+1(7² - 1) + 10^3k-1(10³ - 1) + 3x <---by our induction hypothesis

= 4^k(3) + 7^2k+1(48) + 10^3k-1(999) + 3x

= 3[4^k + (7^2k+1)(16) + (10^3k-1)(333)] + 3x

= 3y + 3x = 3(y + x), for y = 4^k + (7^2k+1)(16) + (10^3k-1)(333)

and is therefore true for all n.

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:

4ⁿ + 7²ⁿ⁺¹ + 10^3n-1

≡ (1)ⁿ + (1)²ⁿ⁺¹ + (1)^3n-1 (mod 3)

≡ 1 + 1 + 1 (mod 3)

≡ 0 (mod 3), thus we have 4ⁿ + 7²ⁿ⁺¹ + 10^3n-1 is divisible by 3.

one can also attempt an induction proof, that 4ⁿ + 7²ⁿ⁺¹ + 10^3n-1 is divisible by 3 for all natural numbers n.

base case: n = 1:

4 + 7³ + 10² = 4 + 343 + 100 = 447 = 3*149.

assume that:

4^k + 7^2k+1 + 10^3k-1 = 3x, for some positive integer x.

then:

4^k+1 + 7^2k+3 + 10^3k+2 =

(4^k+1 - 4^k) + (7^2k+3 - 7^2k+1) + (10^3k+2 - 10^3k-1) + 4^k + 7^2k+1 + 10^3k-1

= 4^k(4 - 1) + 7^2k+1(7² - 1) + 10^3k-1(10³ - 1) + 3x <---by our induction hypothesis

= 4^k(3) + 7^2k+1(48) + 10^3k-1(999) + 3x

= 3[4^k + (7^2k+1)(16) + (10^3k-1)(333)] + 3x

= 3y + 3x = 3(y + x), for y = 4^k + (7^2k+1)(16) + (10^3k-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?
I also admire your inductive trick based proof.

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:



what is inside the latex tags is:

2 \equiv 6\ \text{mod }4

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:



what is inside the latex tags is:

2 \equiv 6\ \text{mod }4

Thank you so much Devono.