Question

for n=195, by Fermat's theorem an-2​

Answer 1

Answer:

am taking number theory and have hit a roadblock taking the next logical step in one of my proofs. I am told that n=195=3⋅5⋅13. I am asked to show that an−2≡na,∀a∈Z.

The previous part of the problem was relatively straight-forward, but this one has me stuck. So far, I have established the trivial result by considering

n|a⇒n|an−2

thus,

an−2≡n0≡na.

At which point, I'd be finished. To show that this holds for all results, it seems I need to consider the congruences mod 3,5,and 13 and show that an−3=a192 is congruent to 1 for each prime factor. The problem is that I can't assume that p∤a for p∈{3,5,13} to be able to invoke Fermat's without loss of generality.

Could someone please point me in the right direction? I feel like I'm missing an easy (albeit fundamental) step here. Thanks!

Step-by-step explanation:

Answer 2

Given:

we are only if $n=195$.

Find:

we have to search out $a^{n-2}$ by using Fermat's theorem.

Fermat's theorem:

Fermat's theorem, also referred to as Fermat's little theorem and Fermat's primality test, in number theory, the statement, first given in 1640 by French mathematician Pierre de Fermat, that If $p$ could be a prime and $a$ is any integer not divisible by $p,$ then $a^{p-1}-1$ is divisible by $p.$

that is $a^{p-1}-1\equiv 0(\mod p)$ or $a^{p-1}\equiv 1(\mod p)$.

Solution:

The prime factorization of $n=195$ is $195=3\times 5\times 13$

Now, we shall write $n-2=193$ by using $3-1=2,5-1=4$ and $13-1=12$

that is

$193=2\times 96+1\\193=4\times 48+1\\193=12\times 16+1$

Then $a^{193}$ is written as follows

$a^{193}=a^{2\times 96+1}=(a^{2})^{96}a\\a^{193}=a^{4\times 48+1}=(a^4)^{48}a\\a^{193}=a^{12\times 16+}=(a^{12})^{16}a$

comparing the above equations wih fermat's theorem we've got

$p=3$ for $a^{193}=(a^2)^{96}a$

$p=5$ for $a^{193}=(a^4)^{48}a$

$p=13$ for $a^{193}=(a^{12})^{16}a$

Then the equation will be written as

$a^{193}=(a^2)^{96}a\equiv a(\mod 3)\\a^{193}=(a^4)^{48}a\equiv a(\mod 5)\\a^{193}=(a^{12})^{16}a\equiv a(\mod 13)$

Hence, $a^{193}=(a^2)^{96}a\equiv a(\mod 3,5,13)$

Since the LCM of $3,5$ and $13$ is $195$, we have

$a^{193}\equiv a(\mod 3,5,13\\a^{193}\equiv a(\mod 195)$

that is $a^{195-2}\equiv a(\mod 195)$

Therefore, $a^{n-2}\equiv a(\mod n)$

Hence, by Fermat's theorem $a^{n-2}\equiv a(\mod n)$.

#SPJ2