# DCP-527: Modular Inverse Back to All Problems

Easy Math > Number Theory

Modular inverse of a number **a** (mod **m**) is **b** such that `` a*b=1 (mod m) `` where **0 &le; a,b &lt; m** we write **a <sup>-1</sup>=b (mod m)** or **b <sup>-1</sup>=a (mod m)** which means **a** and **b** are modular inverse of each other in mod **m**. Note that , modular inverse of a number is not always exist. In particular modular inverse of a number **a** (mod **m**) exist if and only if ```gcd(a,m)=1``` . Here gcd means greatest common divisor. In this problem you have to find modular inverse of **2** modulo **m**. In other word given **m** , ( 2 < m <2<sup>64</sup> ), find a number **a** such that ``` (2*a)=1 mod(m) ``` or report it does not exist. Input: ------ Input starts with an positive integer **T &le; 10<sup>5</sup>** , denoting the number of test cases. Each case contains an integer **m** ( 2 < m <2<sup>64</sup> ) in a line Output: ------- For each test case print a integer **a** **(0 &le; a &lt; m)**, such that a is modular inverse of 2 (mod **m**), if no such **a** exist print **-1**. Sample Input ------------ 2 3 4 Sample Output ------------- 2 -1

### Problem Limits

 Language Time Limit (seconds) C 0.50 C++ 0.50 C++14 0.50 C# 1.00 Go 1.00 Java 1.00 JavaScript 1.00 Objective-C 1.00 Perl 1.00 PHP 1.00 Python 1.00 Python3 1.00 Ruby 1.00 VB.Net 1.00

# 57/336

Solve/Submission

### Ranking

# User Language Timing
01 tariqiitju Cpp 0.03s
02 ehsan_sshuvo96 Cpp 0.03s
03 mhiceiuk Cpp 0.03s
04 shamiul93 Cpp 0.03s
05 pulak_ict_mbstu Cpp 0.03s
06 kabbya Cpp 0.04s
07 leenaiitju Cpp 0.04s
08 shishir09 Cpp14 0.04s
09 mash02 Cpp 0.04s
10 Rajan_sust Cpp 0.04s
11 Not_Found0001 Cpp 0.04s
12 Tahseen Cpp 0.04s
13 feodorv C 0.04s
14 shamimjucse Cpp 0.04s
16 L1nK1n Cpp 0.04s
17 dot0 Cpp 0.04s
18 rayhan50001 Cpp14 0.04s
19 S_Saqib Cpp 0.07s
20 kakarotto Cpp 0.08s
21 Bisnu039 Cpp 0.13s
22 prateepm Cpp14 0.13s
23 deloar1 Cpp 0.13s
24 Silent_Warrior Cpp 0.18s
25 nasib_mbstu Cpp 0.18s
26 joty_ict Cpp 0.18s
27 fayedanik Cpp 0.18s
28 Log_out Cpp 0.18s
29 subhashis_cse Cpp 0.18s
30 hmsayem Cpp 0.18s
31 rabbycse Cpp 0.18s
33 unknown420 Cpp 0.18s
34 prodipdatta7 Cpp14 0.18s
35 t0whid Cpp 0.18s
37 Shakil_Mahmud Cpp 0.19s
38 AlaminJust Cpp 0.19s
39 st3inum Cpp 0.35s
40 Riaz_BSMRSTU Cpp 0.36s
41 obujgalib Cpp 0.37s
42 we7d Python3 0.49s
43 sabertooth Python3 0.57s
Feedback