• Non ci sono risultati.

# (b) Show that under the additional condition that gcd(a, b

N/A
N/A
Protected

Condividi "(b) Show that under the additional condition that gcd(a, b"

Copied!
1
0
0

Testo completo

(1)

Problem 11863

(American Mathematical Monthly, Vol.122, October 2015) Proposed by Jeffrey C. Lagarias and Jeffrey Sun (USA).

Consider integers a, b, c with 1 ≤ a < b < c that satisfy the following system of congruences:

(a + 1)(b + 1) ≡ 1 (mod c) (a + 1)(c + 1) ≡ 1 (mod b) (b + 1)(c + 1) ≡ 1 (mod a).

(a) Show that there are infinitely many solutions (a, b, c) to this system.

(b) Show that under the additional condition that gcd(a, b) = 1, there are only finitely many solu- tions (a, b, c) to the system, and find them all.

Solution proposed by Roberto Tauraso, Dipartimento di Matematica, Universit`a di Roma “Tor Vergata”, via della Ricerca Scientifica, 00133 Roma, Italy.

(a) For any a ≥ 1, take b = (a + 1)2− 1, c = (a + 1)3− 1 then

(a + 1)(b + 1) = (a + 1)3= c + 1 ≡ 1 (mod c) (a + 1)(c + 1) ≡ (a + 1)4= (b + 1)2≡ 1 (mod b) (b + 1)(c + 1) = (a + 1)5≡ 1 (mod a).

Hence we have an infinite set of solutions

{(1, 3, 7), (2, 8, 26), (3, 15, 63), (4, 24, 124), (5, 35, 215), (6, 48, 342), (7, 63, 511), (8, 80, 728), (9, 99, 999), . . .}.

Note that for these solutions, gcd(a, b) = gcd(a, c) = gcd(b, c) = a.

(b) Assume that gcd(a, b) = 1 and let d = gcd(a, c) then d | a and

(a + 1)(b + 1) ≡ 1 (mod c) ⇒ ab + a + b ≡ 0 (mod c) ⇒ b ≡ ab + a + b ≡ 0 (mod d) ⇒ d | b.

Hence d | gcd(a, b) = 1 and d = 1. In a similar way, we get that gcd(b, c) = 1.

Now the three congruences imply

(a + 1)(b + 1)(c + 1) ≡ 1 (mod c) (a + 1)(b + 1)(c + 1) ≡ 1 (mod b) (a + 1)(b + 1)(c + 1) ≡ 1 (mod a) and since gcd(a, b) = gcd(a, c) = gcd(b, c) = 1, it follows that

m := (a + 1)(b + 1)(c + 1) − 1

abc = 1 +1

a+1 b +1

c + 1 ab + 1

bc+ 1 ac > 1 is an integer. Therefore m ≥ 2. Moreover, a ≥ 1, b ≥ 2 and c ≥ 3 imply that

4abc = (2a)(3b/2)(4c/3) ≥ (a + 1)(b + 1)(c + 1) = mabc + 1 ⇒ 4 − 1

abc≥ m ⇒ m ≤ 3.

If m = 2 then we have (a + 1)(b + 1)(c + 1) = 2abc + 1, which implies that a + 1 ≡ b + 1 ≡ c + 1 ≡ 1 (mod 2) ⇒ a ≡ b ≡ c ≡ 0 (mod 2) in contradiction with the fact that gcd(a, b) = gcd(a, c) = gcd(b, c) = 1.

If m = 3 and a ≥ 2 then b ≥ 3, c ≥ 4 and

3 ≤ (2 + 1)(3 + 1)(4 + 1) − 1 2 · 3 · 4 =59

24 < 3.

Therefore m = 3 and a = 1:

3 = 2(b + 1)(c + 1) − 1

bc ⇒ (b − 2)(c − 2) = 5 ⇒ b = 3, c = 7.

The conclusion is that if gcd(a, b) = 1 then the system has a unique solution: (a, b, c) = (1, 3, 7). 

Riferimenti

Documenti correlati

Cartesian reference system belonging to the triangle

Recently, starting with the work [14] of Manfredi, Parviainen and Rossi, a great attention has been paid to the so-called asymptotic mean value property (AMVP) and its applications

It is submitted that the probable intention of the drafters of the Restatement (Second) was to achieve a balance (in section 187 (2) (a)) between the older reasonable

Solution proposed by Roberto Tauraso, Dipartimento di Matematica, Universit`a di Roma “Tor Vergata”, via della Ricerca Scientifica, 00133 Roma,

For a real number x whose fractional part is not 1/2, let hxi denote the nearest integer

Let ϕ be the Euler

Solution proposed by Roberto Tauraso, Dipartimento di Matematica, Universit`a di Roma “Tor Vergata”, via della Ricerca Scientifica, 00133 Roma,

[r]

Let E be the midpoint of AC, and let F be the midpoint

[r]

[r]

This is a contradiction because a positive integer is the sum of two squares if and only if all the prime factors congruent to 3 mod 4 have an even exponent in

[r]

Trenkler (Germany).. Let a, b, and c be

Let B be obtained from A by replacing one of its rows or one of its columns by

analogously BB ′ and CC ′ are the bisectors of the angles ∠ABC

First of all, for y(0) &gt; 0 the corresponding solution is positive and strictly growing. Suppose that one of these solutions, with initial value y 0 &gt; 0, has maxi- mum forward

X is the amount won or lost and Y is the outcome of the

Some topics on modular functions, elliptic functions and transcendence theory. Sheet of

Dipartimento di Metodi e Modelli, Matematici per le Scienze Applicate, Universit` a di Roma “La Sapienza”,

[r]

(a) In this case the unit tangent vector is constant (it is contained in fixed plane for all t and it makes a constant angle with a fixed vector of that plane ).. This implies that

Vengo- no utilizzati inoltre i dati provenienti dal diario (frequenza e uso delle lezioni e giudizio sul livello di difficoltà delle risorse presentate e del carico