# Using Congruences - Wilson's and Fermat's Thms

• Oct 14th 2012, 08:32 AM
ncshields
Using Congruences - Wilson's and Fermat's Thms
This seems like a relatively simple computational problem (in fact I know how to do it for 2^91 divided by 7) but I am not sure how to apply the same process here.

My question: What is the remainder when 314^162 is divided by 7? (using congruences)
• Oct 14th 2012, 08:44 AM
MaxJasper
Re: Using Congruences - Wilson's and Fermat's Thms
$\displaystyle 314^{162}\equiv 314^{3*54}\equiv 2^{3*54}*157^{3*54}\equiv N*2^3\equiv N*8$

$\displaystyle N*8\equiv 1 \bmod 7$
• Oct 14th 2012, 10:04 AM
ncshields
Re: Using Congruences - Wilson's and Fermat's Thms
So N = 157^54. Why can you substitute N in to the congruence and just consider 8 (mod 7)?
• Oct 14th 2012, 10:09 AM
MaxJasper
Re: Using Congruences - Wilson's and Fermat's Thms
It is irrelevant what N is in value...it becomes just a multiplier to the congruent remainder resulting in the same remainder.
• Oct 26th 2012, 03:27 AM
Salahuddin559
Re: Using Congruences - Wilson's and Fermat's Thms
I will explain a bit. I think he did not get the direct steps, and skipping. For all these questions, you take the bases modulo first. In case of 2^91 or something, you first raise it to sufficient power that you can take a different modulus than 2, namely, you raise to power 3, it becomes 2 * (2^3)^30 = 2 * 8^30. Since now, 8's modulo is 1 w.r.t 7, then we have, 2 * 8^30 = 2 * 1^30 = 2 (mod 7). Similarly, with 314^162, first take remainder of 314 w.r.t 7, which gives 6 or -1. If you raise this remainder to 162, which is an even number, that will give 1 as the remainder.

Salahuddin
Maths online