<abstract xmlns="http://www.w3.org/1999/xhtml"> K. Bibak et al. [arXiv:1503.01806v1 [math.NT],March 5 2015] proved that congruence ax ≡ b (mod n) has a solution x0 with t = gcd(x0, n) if and only if gcd <inline-formula><alternatives><inline-graphic xmlns:xlink="http://www.w3.org/1999/xlink" xlink:href="graphic/Untitled-4.jpg"></inline-graphic></alternatives></inline-formula> thereby generalizing the result for t = 1 proved by B. Alomair et al. [J. Math. Cryptol. 4 (2010), 121-148] and O. Grošek et al. [ibid. 7 (2013), 217-224]. We show that this generalized result for arbitrary t follows from that for t = 1 proved in the later papers. Then we shall analyze this result from the point of view of a weaker condition that gcd <inline-formula><alternatives><inline-graphic xmlns:xlink="http://www.w3.org/1999/xlink" xlink:href="graphic/Untitled-5.jpg"></inline-graphic></alternatives></inline-formula>. We prove that given integers a, b, n ≥ 1 and t ≥ 1, congruence ax ≡ b (mod n) has a solution x0 with t dividing gcd(x0, n) if and only if gcd <inline-formula><alternatives><inline-graphic xmlns:xlink="http://www.w3.org/1999/xlink" xlink:href="graphic/Untitled-6.jpg"></inline-graphic></alternatives></inline-formula> divides gcd <inline-formula><alternatives><inline-graphic xmlns:xlink="http://www.w3.org/1999/xlink" xlink:href="graphic/Untitled-7.jpg"></inline-graphic></alternatives></inline-formula>.</abstract>

K. Bibak et al. [arXiv:1503.01806v1 [math.NT],March 5 2015] proved that congruence ax ≡ b (mod n) has a solution x0 with t = gcd(x0, n) if and only if gcd  thereby generalizing the result for t = 1 proved by B. Alomair et al. [J. Math. Cryptol. 4 (2010), 121-148] and O. Grošek et al. [ibid. 7 (2013), 217-224]. We show that this generalized result for arbitrary t follows from that for t = 1 proved in the later papers. Then we shall analyze this result from the point of view of a weaker condition that gcd . We prove that given integers a, b, n ≥ 1 and t ≥ 1, congruence ax ≡ b (mod n) has a solution x0 with t dividing gcd(x0, n) if and only if gcd  divides gcd .

New solvability conditions for congruence ax≡b (mod n)

Institute of Computer Science Academy of Sciences of the Czech Republic Pod Vodárenskou věží 2 182 07 Praha 8–Libeň CZECH REPUBLIC

Tatra Mountains Mathematical Publications

This work is licensed under the Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 License.

{"article-title":"New solvability conditions for congruence ax≡b (mod n)"}

K. Bibak et al. [arXiv:1503.01806v1 [math.NT],March 5 2015] proved that congruence ax ≡ b (mod n) has a solution x0 with t = gcd(x0, n) if and only if gcd ...

New solvability conditions for congruence ax≡b (mod n)

Published Online: Feb 19, 2016

Page range: 93 - 99

Received: Nov 22, 2015

DOI: https://doi.org/10.1515/tmmp-2015-0044

Keywords
linear congruence, the greatest common divisor, number of solutions

© 2016

This work is licensed under the Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 License.

New solvability conditions for congruence ax≡b (mod n)

Published Online: Feb 19, 2016

Page range: 93 - 99

Received: Nov 22, 2015

DOI: https://doi.org/10.1515/tmmp-2015-0044

Keywordslinear congruence, the greatest common divisor, number of solutions

© 2016

This work is licensed under the Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 License.

Keywords
linear congruence, the greatest common divisor, number of solutions