Modular arithmetic

>>7653514
>who is Euler
>Legendre
>Jacobi
>fermats little theorem

just off the top of my head from number theory

>>7653514
matlab

I thought that Euler can't help. phi(375) = 200
4^200 mod 375 = 1 ;p

>>7653538
>fermats little theorem
[math] a^{p} \equiv a ~~ \text{mod}(p) [/math] for prime p.

>99
>Prime

>>7653562
you need the generalization of fermat's little theorem called euler's theorem, then its easy

>>7653920
or alternatively use chinese remainder theorem first so that you can use fermat's little theorem later

also>>7653562 you clearly don't understand the use of the theorem

CRT and Euler.

[math]375 = 3*5^3[/math], so first we solve mod 3 and then mod 125. Looking mod 3 it's obvious [math] 4^{99} = 1 mod 3[/math]. Now we have [math]\phi(125) = 25*(5-1) = 100[/math], so [math]4^{100} = 1 mod 5^3[/math] implies [math]4^{99} = 4^{-1} mod 5^3[/math] which is easier to compute. We have [math]4^{-1} = 94 mod 5^3[/math] just by using 4*94 = 1 + 3*125 (I found it by just looking at 1 + k*125 until I found a multiple of 4, but there are more algorithmic methods).

So we patch together [math] x = 1 mod 3[/math] and [math]x = 94 mod 125[/math]. But 94 is already 1 mod 3, so we get [math]x = 94 mod 375[/math] as a final result, and it is unique mod 375 by CRT again.

>>7653973
Oh come on, CRT and Euler combined are overkill, with Euler alone you get 4^99=2^198=2^-2=4^-1 mod 375

>>7653514
We know that ((a mod n)(b mod n)) mod n = ab mod n. We also know that rules for exponents in modular arithmetic are the same as the "normal" rules we already know, in particular, 4^(99)=(4^9)(4^(90)) etc.

This should be enough to get you started.

>>7653514
The technique is called successive squaring. It's pretty cool and worth a look.

>>7653514
so this is one way I did it by simplifying the exponent
4^99 mod 375
>I first simplified the exponent into small numbers for easier to work with answers
99=5*18 + 9
4^99=(4^5)^18 * 4^9
>I then broke the equation down to easier numbers
4^99 mod 375 =
((4^5 mod 375)^18 * (4^9 mod 375)) mod 375

4^5 mod 375 = 274, 4^9 mod 375 = 19
>now I just simplifies until I got to a smaller number
(274^18) * 19) mod 375
((274^3)^6 * 19) mod 375
(20570824^5 * 390845656) mod 375
((20570824 mod 375)^5 * (390845656 mod 375)) mod 375
(199^5 * 31) mod 375
94

this should help but i'm tired so there probably is a better way that I can't think of right now

File: 7c6.png (11KB, 211x246px) Image search: [Google]

11KB, 211x246px

Just use Yooler's tierem

>>7653514
Put into base 374
Add the individual numbers till you have a single digit number (still base 374 here)
Convert said number back to base 10
QED