wwwmathucsdeduasa 177 unreadelahel 337 x G Chegg Study l Gu

www.math.ucsd.edu/-asa ×· (177 unread)-elahel 337 x G Chegg Study l Guided So X -)C Dwww.math.ucsd.edu/~asalehig/math109-f-15-PracticeFinal.pdf 4 Basic arithmetic. 1. Write down the Division theorem and prove it. 2. Prove that no integer of the form 7k +3 (where k 3. Prove that 2 i=0 ai Z) is a perfect square. 3. Prove that _0ai 10\'-_0ai (mod 9) 4. Let a, b, n E Z+ . Prove that ax b (mod n) has a solution if and only if gcd(a, n) b. 5. Find an integer solution of 2015.x + 273y-gcd(2015,273). (This is from Professor Sorense\'s exam.) 6. Let f : {0, 1, . . . ,7) × {0, 1, . . . ,7) {0, 1, , 7),f(x,y) xy (mod 8). Write an 8 × 8 table where the i, j entry is f(i - 1,j-1). In which rows is there a 1? 7. Find the remainder of 916 divided by 13 8. Suppose a b (mod n). Prove that gcd(a, n) = gcd(b, n) 9. Suppose p is prime. Prove that plab if and only if either pla or plb 10. Suppose gcd(a, b)-1. Prove that albc if and only if alc. Look at the last problem set for more related problems PTFP11Qu... 8:09 PM 12/7/2015 Search the web and Windows www.mat... PTFP10Cli... final exam...

Solution

we are given

gcd(a,b)=1

ma +nb =1

we have to prove

a|bc : bc =m*a

if and only if

a|c : c=n*a

ma +nb =1

c+nb=1

gcd(b,c)=1

so, we will get

gcd(a,bc)=1

hence ,

a|bc..............Answer