Question

Determine necessary and sufficient conditions on $\mathbf{x}\mathbf{}\mathbf{and}\mathbf{}\mathbf{c}$ so that the following holds: for any$\mathbf{a}\mathbf{,}\mathbf{b}\mathbf{,}$ if $\mathbf{ax}\mathbf{\equiv }\mathbf{bx}\mathbf{}\mathbf{mod}\mathbf{}\mathbf{c}$, then$\mathbf{a}\mathbf{\equiv }\mathbf{bmodc}$ .

Short answer

The necessary and sufficient condition for$\mathrm{x}\mathrm{and}\mathrm{c}$ is$(\mathrm{a}-\mathrm{b})$ must be divisible by$\mathrm{c}$ as the$\mathrm{GCD}(\mathrm{c},\mathrm{x})$ is equal to$1$ .

Step-by-step solution

Introduction

Fermat’s Little Theorem states that for any prime number $\mathrm{x}$and integer $\mathrm{i}$, the number i.e. ${\mathrm{i}}^{\mathrm{x}}–\mathrm{i}$is the factor of $\mathrm{x}$.

Given condition

The given is,

For any$\mathrm{a},\mathrm{b},\mathrm{c}$

If $\mathrm{ax}=\mathrm{bx}\mathrm{modc}$

To prove:$\mathrm{a}=\mathrm{b}\mathrm{mod}\mathrm{c}$

Condition we can define from the given statement 

If$\mathrm{ax}=\mathrm{bx}\mathrm{modc}$

Then,

$\frac{\mathrm{c}}{(\mathrm{a}-\mathrm{b})\mathrm{x}}$

If $\mathrm{a}=\mathrm{bmodc}$,

$\frac{\mathrm{c}}{(\mathrm{a}-\mathrm{b})}$

Explanation

So, here $\mathrm{c}$ divides $(\mathrm{a}-\mathrm{b})\mathrm{x}$ then, $\mathrm{c}$ must divide $(\mathrm{a}-\mathrm{b}).$

For the value of $\mathrm{x}$, the$\mathrm{GCD}(\mathrm{c},\mathrm{x})$ must equal to $1$ that ensure that$(\mathrm{a}-\mathrm{b})\mathrm{x}$ is divisible by $\mathrm{c}$.

Thus, in this case$(\mathrm{a}-\mathrm{b})$ must be divisible by$\mathrm{c}$ as the$\mathrm{GCD}(\mathrm{c},\mathrm{x})$ is equal to $1$.

Therefore, the necessary and sufficient condition for$\mathrm{x}\mathrm{and}\mathrm{c}$ is$(\mathrm{a}-\mathrm{b})$ must be divisible by$\mathrm{c}$ as the$\mathrm{GCD}(\mathrm{c},\mathrm{x})$ is equal to $1$.