Let p and a be positive integers and suppose that p|a2. a) Show that p|(ra + sp)2 for all integers r; s. b) Use part a), the definition of prime integer, and Theorem 15.1.1 to construct a proof by induction that p|a. [Hint: If a (< or =) p consider p = qa + r, where 0 (< or =) r < a. If p < a consider a = qp + r, where 0 (< ...continues
please give the missing digit : it is a three by three puzzles, the first row has a 9and 7 ,but missing a first number, the second row has a 4, missing the first and third number and the last row is empty. the second thre by three square has a 3 in the first row,second row is empty, and third row has a 7 in the first box and ...continues
Show that if and , then . (This shows that the function g is well-defined from to ) Note: g is defined as follows: g: Where is the multiplicative inverse of m1 modulo m2 and conversely. Please see the attached file for the fully formatted problems.
Linear Congruences : Chinese Remainder Theorem
The idea of this problem is to investigate solutions to x2≡1(mod pq) where p and q are distinct odd primes. (a) Show that if p is an odd prime, then there are exactly two solutions modulo p to x2≡1(mod p). (b) Find all pairs (a,b) Є Zp x Zq such that a2≡1(mod p) and b2≡1(mod q). (c) Let p=17 an ...continues
Number Theory : Show that for every positive integer n, 8n+1 is not prime.
Show that for every positive integer n, 8n+1 is not prime.
An integer n is called k-perfect if σ(n) = kn (note that a perfect number is 2-perfect). (a) Show that 120 = 23• • • 3 • • • 5 is 3-perfect. (b) Show that if n is 3-perfect and gcd(3, n) = 1, then 3n is 4-perfect.
In order to solve the congruence 2x + 6 ≡ 4 (mod 8), your friend Phil Lovett wrote down the following steps: 2x+6 ≡ 4 (mod 8) x+3 ≡ 2 (mod8) x ≡ −1 (mod 8) From here, Phil concludes that the solution set to 2x + 6 ≡ 4 (mod 8) is {x; x ≡ −1 (mod 8)}. (a) Is Phil’s ...continues
The identification number for a bank printed on a check consists of eight digits x1 . . . x8, followed by a ninth check digit x9, with x9 ≡ 7x1 +3x2 + 9x3 + 7x4 + 3x5 + 9x6 + 7x7 + 3x8 (mod 10). (a) What is the check digit following the eight-digit identification number 00185403 for a bank? (b) Will this scheme d ...continues
Show that if gcd(a, b) = 1, then gcd(ac, b) =gcd(b, c).
Proof using the Euler Function and Fermat's Theorem
Prove or disprove: If m|n, then ø(m,n)=mø(n).
