Number theorem Flashcards
Don’t divide by a potential negative number without flipping the inequality
x-1 > 6/x
square both sides or draw diagram, cant times by x as could be zero or negative
f(-x) = -f(x) therefore
odd function
3^4^x has last digit
3^4 = 81
therefore last digit 1
a^b^c has last digit =
last digit of a^b
a = 1 mod(n) therefore
a^k = 1^k mod(n) = 1 mod(n)
Zeroes in n! =
n/5 + n/25…n/5^x
for 5^x <= n
Divisible by 3
sum of digits is a multiple of 3
divisible by 4
last two digits are multiples of 2
divisible by 6
divisible by 3 and 2
divisible by 7
double the last digit and subtract from rest of the digits. If 0 or multiple of 7 then divisible otherwise repeat to get smaller number
divisible by 8
last three digits divisible by 8
divisible by 11
alternating sum of digits is divisible by 11 or equals zero
divisible by 12
number divisible by 3 and by 4
A number is the square if
the powers in its prime factorisation are even
A number is cube if
its powers are divisible by 3
Number of factors a number has
by adding one to each power
Square rooting gives
two possible solutions
(2^7) * 5^4 =
(2*5)^4 * 8
Approximate the value of an expression when variables become large.
The key here is that constant values become inconsequential when combined with a growing variable
Number of factors =
prime factorization + 1 timesed together
geometric mean <
arithmetic mean
A number is a square if and only if
the powers in its factorization are even
a number is a cube if and only if
its powers are divisible by 3
To find the number of factors a number has
do prime factorisation, add one to each power, times all new powers together
Arithmetic mean ___ geometric mean
>
x^2…
> 0
6^(x+y) x 12^(x-y) =
(32)^(x+y) x (22*3)^(x-y)
1/a^x is an integer for
x<=0
if 3(root3) > 4 then to prove
square both sides
27 > 16
Two numbers, a and b, are coprime or relatively prime if
a and b share no common factors
LCM(a,b) = ab,
(a, b) = 1
K and k+1 are coprime because
suppose k had some factor q, k+1 must have a remainder of 1 when divided by q so is not divisible by q
k-1 and k+1 are coprime if k is
even
Perfect square =
square number
Number of zeros
via prime factorisation (2’s and 5’s and 10’s)
Number of zeros on the end of n!
n/5^x
Every two consecutive numbers are even,
every three are divisible by 3
a/x + b/y = c –>
(cx-a)(cy-b)=ab
Integer solutions of divisions tip
put variables in denominator only
remeber negative
factors
If you have two consecutive factors i.e. (n)(n+1) then we can say
they are coprime and thus share no factors
moduluo arithmetic allows:
addition, multiplication, powers
If x divided by y gives remainder z, then
x-z is divisible by y
Show that if 2+2(1+12n^2)^0.5 is an integer then it is a perfect square
First note that the question says IF [..] is an integer, THEN it is a square. We need to start with the assumption, and reason towards the conclusion – don’t be tempted to prove the opposite. If it is an integer, then we can say that the bit in the root is a perfect square, since the square root has to be an integer, and that it is odd. We can therefore rewrite the root as (2k+1)^2. We can rearrange this to 3n^2 = k(k+1). The RHS are coprime, one is square the other is three times a square. If k+1 was a multiple of 3, then by modular arithmetic, k couldn’t be square. Therefore k+1 is a square, and k is three times a square
Let n=ab, m = abc
Represent n and m in terms of single digits
n = 10a + b m = 100a + 10b + c
if p is prime and a is any integer such that a is not a multiple of p then fermats little theorem states:
a^p-1 = 1(modp)
A square chessboard of sides 2^n is tiled with L-shapes, each of three square, such that tiles do not overlap. Show that you will always have one square on the chessboard left untiled
We are finding the remainder when we divide (2^n)^2 = 4^n by 3
4=1 (mod3)
So 4^n = 1^n = 1 (mod3)
Show that x^2 - y^2 = 2002 has no integer solutions
x = 0, 1, 2, 3 (mod4) x^2 = 0, 1 (mod4) as is y^2
So all possibilities of x^2 - y^2 = 0, 1, 3 (mod4)
However 2002 = 2 (mod4)
Thus there can be no integer solutions
List all the prime numbers that are one less than a square number
Let p be a prime number, p+1 = n^2 p=n^2 – 1 = (n+1)(n-1) for p to be prime one bracket must be a one, the other must be p, as p>1 we can say n-1 = 1, n=2m therefore one solution when p=3
List all primes that are one more than a cubed number
Let p be a prime number, p-1=n^3 p=n^3+1 = (n+1)(n^2-n+1) therefore n+1 = p or 1, but as n cant equal zero then n+1 =p, n^2-n+1 = 1 therefore n(n-1) = 0, therefore n=1 therefore p=2
Can K^3 + 2k^2 +2k +1 ever be a cubed number for any positive integer k
K^3 + 2k^2 +2k +1 = n^3 we can say that n^3 > K^3 n^3 = (k+1)^3 + k^2 + k therefore n^3
