Brahmagupta Fibonacci identity states that the product of two numbers each of which is a sum of 2 squares can be represented as sum of 2 squares in 2 different forms.
Mathematically,
If a = p^2 + q^2 and b = r^2 + s^2
then a * b can be written in two
different forms:
= (p^2 + q^2) * (r^2 + s^2)
= (pr – qs)^2 + (ps + qr)^2 …………(1)
= (pr + qs)^2 + (ps – qr)^2 …………(2)
Some Examples are:
a = 5(= 1^2 + 2^2)
b = 25(= 3^2 + 4^2)
a*b = 125
Representation of a * b as sum of 2 squares:
2^2 + 11^2 = 125
5^2 + 10^2 = 125
Explanations:
a = 5 and b = 25 each can be expressed as a sum of 2 squares and their product a*b which is 125 can be expressed as sum of 2 squares in two different forms. This is according to
the Brahmagupta Fibonacci Identity and satisfies the identity condition.
a = 13(= 2^2 + 3^2)
b = 41(= 4^2 + 5^2)
a*b = 533
Representation of a * b as sum of 2 squares:
2^2 + 23^2 = 533
7^2 + 22^2 = 533
a = 85(= 6^2 + 7^2)
b = 41(= 4^2 + 5^2)
a*b = 3485
Representation of a * b as sum of 2 squares:
2^2 + 59^2 = 3485
11^2 + 58^2 = 3485
26^2 + 53^2 = 3485
37^2 + 46^2 = 3485
Below is a program to verify Brahmagupta Fibonacci identity for given two numbers which are sums of two squares.
C++
// CPP code to verify // Brahmagupta Fibonacci identity#include <bits/stdc++.h>using namespace std;void find_sum_of_two_squares(int a, int b){ int ab = a*b; // represent the product // as sum of 2 squares for (int i = 0; i * i <= ab; i++) { for (int j = i; i * i + j * j <= ab; j++) { // check identity criteria if (i * i + j * j == ab) cout << i << "^2 + " << j << "^2 = " << ab << "\n"; } }}// Driver codeint main(){ // 1^2 + 2^2 int a = 1 * 1 + 2 * 2; // 3^2 + 4^2 int b = 3 * 3 + 4 * 4; cout << "Representation of a * b as sum" " of 2 squares:\n"; // express product of sum of 2 squares // as sum of (sum of 2 squares) find_sum_of_two_squares(a, b);} |
Java
// Java code to verify Brahmagupta// Fibonacci identityclass GFG { static void find_sum_of_two_squares(int a, int b){ int ab = a * b; // represent the product // as sum of 2 squares for (int i = 0; i * i <= ab; i++) { for (int j = i; i * i + j * j <= ab; j++) { // check identity criteria if (i * i + j * j == ab) System.out.println(i + "^2 + " + j +"^2 = " + ab); } }}// Driver codepublic static void main(String[] args){ // 1^2 + 2^2 int a = 1 * 1 + 2 * 2; // 3^2 + 4^2 int b = 3 * 3 + 4 * 4; System.out.println("Representation of a * b " + "as sum of 2 squares:"); // express product of sum // of 2 squares as sum of // (sum of 2 squares) find_sum_of_two_squares(a, b);}}// This code is contributed // by Smitha Dinesh Semwal |
Python 3
# Python 3 code to verify# Brahmagupta Fibonacci identitydef find_sum_of_two_squares(a, b): ab = a * b # represent the product # as sum of 2 squares i=0; while(i * i <= ab): j = i while(i * i + j * j <= ab): # check identity criteria if (i * i + j * j == ab): print(i,"^2 + ",j,"^2 = ",ab) j += 1 i += 1 # Driver codea = 1 * 1 + 2 * 2 # 1^2 + 2^2b = 3 * 3 + 4 * 4 # 3^2 + 4^2print("Representation of a * b as sum" " of 2 squares:")# express product of sum of 2 squares# as sum of (sum of 2 squares)find_sum_of_two_squares(a, b)# This code is contributed by# Smitha Dinesh Semwal |
C#
// C# code to verify Brahmagupta// Fibonacci identityusing System;class GFG { static void find_sum_of_two_squares(int a, int b) { int ab = a * b; // represent the product // as sum of 2 squares for (int i = 0; i * i <= ab; i++) { for (int j = i; i * i + j * j <= ab; j++) { // check identity criteria if (i * i + j * j == ab) Console.Write(i + "^2 + " + j + "^2 = " + ab + "\n"); } }}// Driver codepublic static void Main(){ // 1^2 + 2^2 int a = 1 * 1 + 2 * 2; // 3^2 + 4^2 int b = 3 * 3 + 4 * 4; Console.Write("Representation of a * b " + "as sum of 2 squares:\n"); // express product of sum of // 2 squares as sum of (sum of // 2 squares) find_sum_of_two_squares(a, b);}}// This code is contributed // by Smitha Dinesh Semwal |
PHP
<?php// PHP code to verify // Brahmagupta Fibonacci identityfunction find_sum_of_two_squares($a, $b){ $ab = $a * $b; // represent the product // as sum of 2 squares for ($i = 0; $i * $i <= $ab; $i++) { for ($j = $i; $i * $i + $j * $j <= $ab; $j++) { // check identity criteria if ($i * $i + $j * $j == $ab) echo $i ,"^2 + ", $j , "^2 = " , $ab ,"\n"; } }}// Driver code// 1^2 + 2^2$a = 1 * 1 + 2 * 2; // 3^2 + 4^2$b = 3 * 3 + 4 * 4; echo "Representation of a * b ". "as sum of 2 squares:\n";// express product of sum of // 2 squares as sum of (sum // of 2 squares)find_sum_of_two_squares($a, $b);// This code is contributed by aj_36?> |
Javascript
<script>// JavaScript program to verify Brahmagupta// Fibonacci identity function find_sum_of_two_squares(a, b){ let ab = a * b; // represent the product // as sum of 2 squares for (let i = 0; i * i <= ab; i++) { for (let j = i; i * i + j * j <= ab; j++) { // check identity criteria if (i * i + j * j == ab) document.write(i + "^2 + " + j +"^2 = " + ab + "<br/>"); } }}// Driver code // 1^2 + 2^2 let a = 1 * 1 + 2 * 2; // 3^2 + 4^2 let b = 3 * 3 + 4 * 4; document.write("Representation of a * b " + "as sum of 2 squares:" + "<br/>"); // express product of sum // of 2 squares as sum of // (sum of 2 squares) find_sum_of_two_squares(a, b); // This code is contributed by code_hunt.</script> |
Representation of a * b as sum of 2 squares: 2^2 + 11^2 = 125 5^2 + 10^2 = 125
Time complexity : O(a*b)
Auxiliary Space : O(1)
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!