Do the factors of a triangular number "plus 1" always end in 1 or 9?

You can also get away with a simple use of the Legendre symbol and quadratic reciprocity. The question is does 5n^2+5n+1 = 0 mod p imply p = +/-1 mod 5 when p is a prime.

Write 5n^2 + 5n = -1 mod p then multiplying both sides by 4 and adding 5 gets 5(4n^2+4n+1) = 1 mod p, or 5(2n+1)^2 = 1 mod p, which is always solvable when the Legendre symbol (5/p) =1 (just raise both sides to the (p-1)/2 power and note that (5/p) = 5^{(p-1)/2} mod p.

By quadratic reciprocity (5/p) = (p/5), and (p/5) =1 only when p = +/-1 mod 5 (just hand check solutions to x^2 = +/-1 and +/-2 mod 5).

Clearly since 5n(n+1)+1 is odd you don't need to worry about p =2.

Edited version owing a lot to Josh Swanson's suggestions.

Let T_n = n(n+1)/2. You want to know whether all factors of 10 T_n + 1 are of the form (10 q + 1) or (10 q + 9)

The answer is yes.

Look at 20*(10 T_n + 1) = 20*(5n^2 + 5n + 1) = 100 n^2 + 100 n + 20 = (10 n + 5)^2 - 5.

It is enough to show that this number has no prime factor of the form (10 q + 3) or (10 q + 7).

We shall actually show it for any number of the form N^2 - 5.

In fact we'll show that no prime number of the form 10 q + 3 or 10 q + 7 can be a factor of a number of the form N^2 - 5.

Suppose this is not true and that such prime numbers exist. Call a the smallest of them all and let N such that a | N^2 - 5.

Working mod a, we can replace N by its residue or equivalently assume that N < a.

Set N^2 - 5 = ab. Then ab < N^2 < a^2, hence b < a.

By the definition of a, since b < a, b has no prime factor of type 10 q + 3 or 10 q + 7. Hence N^2 - 5 has exactly one prime factor of the form 10 q + 3 or 10 q + 7, namely a.

In order to reach a contradiction we just need to prove the following:

If a number N^2 - 5 has one prime factor of the form (10 q + 3) or (10 q + 7), then it has at least 2 such prime factors (possibly equal)

Write N^2 - 5 = PQ where P carries possible powers of 2 and 5 in the decomposition of N^2 - 5, and Q carries the rest.

Let us show that Q = +1 or -1 mod 10.

We consider 4 cases to get the form of Q, according to whether 5 | N or 2 | N.

1/ N = 10 q: then N^2 - 5 = 100 q^2 - 5 = 5 (20q^2-1) So P = 5 and Q = 20q^2 - 1.

2/ N = 5(2q+1) then N^2 - 5 = 100 q^2 + 100 q + 20 = 20 (5q^2 + 5q + 1). So Q = 10 T_q + 1.

3/ N is even and 5 does not divide N. So N^2 ends as a 4 or 6 an Q = N^2 - 5 is of the form 10 q + 1 or 10 q -1

4/ N is odd and 5 does not divide N. So N = 2q + 1.

N^2 - 5 = 4q^2 + 4q + 1 - 5 = 4(q^2 + q - 1)

Since N^2 - 5 and 5 are coprime and q^2 + q - 1 is odd, Q = q^2 + q - 1.

Mod 10 the values of q^2 + q are (0,2,6,2,0,0,2,6,2,0).

When the value is 6, q^2 + q - 1 = Q is a multiple of 5 which is excluded. Hence if N and 5 are coprime

Q = q^2 + q - 1 = +1 or -1.

This covers all 4 cases.

Observe that since Q and 10 are coprime, none of the prime factors of Q are of the form 10q + k for k=0, 2, 4, 6, 8, or 5, leaving only those the form 10q + k for k=1, 3, -3, and -1".

It follows from Q = +- 1 mod 10 that the product of all prime factors (with powers) of Q of the form (10 q + 3) or (10 q - 3 ) is of the form 10 q +-1. So there can't be just one such factor. This yields the contradiction and completes the proof.

The problem statement is equivalent to proving that 5n^2 + 5n + 1 only has integer factors of the form 5m + 1 and 5m - 1, where n and m are positive numbers.

As Josh has shown above, a number only ends with the units digit of 1 if two integers multiplying to equal that number ends in 1 and 1, 3 and 7, or 9 and 9. It suffices to show that none of the factors will have units digit of 3 or 7. Since a factor with units digit of 3 implies the existence of another factor with units digit 7, it suffices to show 5n^2 + 5n + 1 has no factor with units digit 7.

Hence, we shall try to prove that no prime factor of 5n^2 + 5n + 1 is of the form 5k + 2 -- since this will prove that no factor of 5n^2 + 5n + 1 is of the form 5k + 2.

Assume for the sake of contradiction that 5n^2 + 5n + 1 is divisible by 5k + 2.

Note that k is odd. This should be pretty obvious, but I'll provide a "proof" later.

5n^2 + 5n = -1 (mod 5k + 2)

5n^2 + 5n = 15k + 5 (mod 5k + 2)

n^2 + n = 3k + 1 (mod 5k + 2)

(2n + 1)^2 = 12k + 5 (mod 20k + 8)

Due to trouble with notation, we shall use f(a,n) to denote the Kronecker symbol.

f(a,n) = 0 if n divides a.

f(a,n) = -1 if a is not a quadratic residue mod n.

f(a,n) = 1 if a is a quadratic residue mod n.

f(12k + 5,20k + 8) = f(12k + 5,5k + 2) * (f(12k + 5,2))^2 * (f(12k + 5,1) =

f(12k + 5,5k + 2) = f(2k + 1,5k + 2) = f(5k + 2,2k + 1) * (-1)^[ (5k + 1)(k) / 2 ] =

f(k,2k + 1) * (-1)^[ (5k + 1)(k) / 2 ] =

f(2k + 1,k) * (-1)^[ (k)(k - 1) / 2 ] * (-1)^[ (5k + 1)(k) / 2 ] =

f(1,k) * (-1)^[ (k)(k - 1) / 2 ] * (-1)^[ (5k + 1)(k) / 2 ] =

1 * (-1)^[ k(6k) / 2 ] = (-1)^[ 3k^2 ] = -1

f(12k + 5,5k + 2) = -1.

Thus, (12k + 5) is not a quadratic residue mod (5k + 2) and thus there is a contradiction.

By this fact, all factors will end in 1 or 9.

I've pretty much never used the Legendre/Jacobi/Kronecker symbol before, so there is a high chance there are some errors I'm not catching here. But, to my knowledge, this solution is fine.

Further elaboration on some workings:

a. 5n^2 + 5n = 15k + 5 (mod 5k + 2)

n^2 + n = 3k + 1 (mod 5k + 2)

Note that 5k + 2 and 5 are coprime, thus this is valid.

b. f(12k + 5,20k + 8) = f(12k + 5,5k + 2) * (f(12k + 5,2))^2 * (f(12k + 5,1) -- Look at the Kronecker symbol page for the formula used

c. f(2k + 1,5k + 2) = f(5k + 2,2k + 1) * (-1)^[ (5k + 1)(k) / 2 ] -- Look at the Jacobi symbol for the law used. This is the Law of Quadratic Reciprocity. You can see that I've used this law twice.

d. The Law of Quadratic Reciprocity requires that the two arguments be odd and coprime. Both the times they were used, the arguments are in fact coprime and odd.

e. k is odd. This is because 5n^2 + 5n + 1 is odd and thus 5k + 2 is not even, which implies k is odd. This fact has been used quite a number of times.

Edit:

@Steiner: All I did was add by 15k + 6, which is clearly divisible by 5k + 2 (and thus the same as adding by 0).

-1 + (15k + 6) = 15k + 5

For the nth triangular number, append 1 to the end and say it factors into the product p*q. Algebraically,

10*n(n+1)/2 + 1 = p*q

Taking this equation mod 10, we get p*q = 1 (mod 10). From modular arithmetic, the only possible values for p and q are 1, 3, 7, and 9 [since 1*1 = 3*7 = 9*9 = 1 (mod 10) are the only ways to get 1]. So, we have to see if 3*7 never occurs. Let p = 10*k + 3 and q = 10*j + 7, so we have

p*q = (10k + 3)(10j + 7)

= 100kj + 70k + 30j + 21

= 10(10kj + 7k + 3j + 2) + 1

= 10*n(n+1)/2 + 1

so

10kj + 7k + 3j + 2

= n(n+1)/2

So, your problem basically reduces to finding (or disproving the existence of) positive solutions of this Diophantine equation. Multiply it by 2 to get

20kj + 14k + 6j + 4 = n^2 + n

Write the ugly factor on the left as C = 20kj + 14k + 6j + 4, giving the quadratic

n^2 + n - C = 0

From the quadratic equation,

n = [-1 +/- sqrt(1 + 4C)] / 2

Since n is an integer, we need the sqrt() term to give an (odd) integer. That is,

1 + 4C = m^2, so

m^2 = 80kj + 56k + 24j + 17

This equation has a solution in positive integers if and only if some triangular number with 1 appended to the end has a factor which ends in digits different from 1 and 9. I have very little experience with Diophantine equations; perhaps someone who does could quickly settle whether or not this has solutions. Taking it modulo the first 1000 integers doesn't result in a contradiction (though the left-hand side is pretty highly restricted; for instance, it must be 1 mod 8). I'll look a little further on a computer later....

Edit: I verified that my equation has no solutions for 0 <= k, j <= 10,000.

Further edit:

Suppose j = k + l for an integer l. My equation becomes

m^2 = 80k(k+l) + 56k + 24(k+l) + 17

= 80(k^2 + kl) + 80k + 24l + 17

= 80(k^2 + k(l+1)) + 24l + 17

= 80[(k+(l+1)/2)^2 - (l+1)^2/4] + 24l + 17

= 80(k+(l+1)/2)^2 - 25(l+1)^2 + 24l + 17

Letting K = k+(l+1)/2 and L = -(-25(l+1)^2 + 24l + 17) = 25l^2 + 26l + 8, we have

m^2 = 80K^2 - L, or

m^2 - 80K^2 = -L

Supposing l is odd, K is an integer, and this is a generalized form of Pell's equation. It has a solution if and only if the original version had a solution (where L is restricted to the values of the relevant quadratic in l), since given L we can solve for l (eg. using the quadratic equation) and given K in addition we can solve for k, from which it is easy to find j. If l is even, I imagine this can be reduced to the preceding case, though I haven't thought long about it.

So, it appears that the solution of this particular Diophantine equation implies quite a bit about a number of generalized Pell's equations.

Yes, the factors of 10T__n +1 always end in

1 or 9.

The proofs given above are all very nice.

However, I have a question about Denis's proof.

He wrote

5n^2 + 5n = -1 (mod 5k + 2)

5n^2 + 5n = 15k + 5 (mod 5k + 2),

but I don't see how he got the second line.

Anyway, here's my solution.

Notation:

If (a,m)=1, I'll use 1/a(mod m) to represent a^-1 (mod m).

Let p be a prime and suppose p = 5k + 2 or 5k + 3.

We have

10T_n +1 = 10n(n+1)/2 + 1 ≡ 0(mod p)

5n^2 + 5n ≡ -1(mod p)

n^2 + n ≡ -1/5(mod p)

4n^2 + 4n ≡ -4/5(mod p)

(2n+1)^2 ≡ 1/5(mod p).

i.e.,

5u^2 ≡ 1(mod p)

Multiply by 5 and let x = 5u to get

x^2 ≡ 5(mod p)

Now let's use the law of quadratic reciprocity:

Let (a/p) denote the Legendre symbol.

If p = 5k+2 then

(5/5k+2) = (5k+2/5) = (2/5) = -1

If p = 5k+3 then

(5/5k+3) = (5k+3/5) =(3/5) = -1

and both cases give a contradiction.