Tagged Questions
0
votes
2answers
63 views
Smallest $k$ such that $4900$ divides $600k$
(A) Express 600 as the product of its prime factors.
(B) Given $4900=2^2 \cdot 5^2 \cdot 7^2$, find the highest common factor of $600$ and $4900$
(C) Given that $600k$ is a multiple of ...
4
votes
3answers
57 views
If a prime $p$ is divided by 30, remainder is either prime or 1
Show that if a prime number $p$ is divided by 30, then the remainder is either a prime or 1.
I did the sum sum but cannot complete it.
I took $p=6k+1$ and $p=6k-1$ form.
now for any $k=5m$ we get ...
4
votes
1answer
86 views
Show $3^m + 3^n +1$ cannot be a perfect square for $m,n$ being positive integers.
So, I decided to work with mod $8$ to help develop some intuition on how to generalize the proof. I noticed that taking $a^2$ to clearly be a perfect square, $a^2$ is always congruent to $0,1,-4,4 ...
1
vote
2answers
58 views
Proof that any polynomial with a positive leading coefficient is eventually positive?
The exact theorem I've been asked to prove is the following:
Suppose $f(x)=a_n x^n + a_{n-1}x^{n-1} + ...+a_0$ is a polynomial of degree $n>0$ and suppose $a_n>0$. Then there is an integer $k$ ...
0
votes
3answers
53 views
difference between 2 prime numbers
We have to prove that if the difference between two prime numbers greater than two is another prime,the prime is $2$.
It can be proved in the following way.
1)$Odd -odd =even$.
Therefore the ...
2
votes
2answers
42 views
Greatest Common Divisor of two numbers
If $ab=600$ how large can the greatest common divisor of $a$ and $b$ be?
I am not sure if I should check for all factor multiples of $a$ and $b$ for this question. Please advise.
2
votes
4answers
44 views
proving congruence of a number modulo 17
We need to prove that $3^{32}-2^{32}\equiv0\pmod{ 17}$.How can we do that?
I tried to express them modulo $17$ in such a way that both cancel out.Really has not helped much.A little hint will be ...
3
votes
4answers
121 views
prime factors of $3^{32}-2^{32}$
The question asks to find 4 prime factors of $3^{32}-2^{32}$ under $100$.
My take:I factorized it and the obvious ones are $5, 97$ and $13$.I cannot find the last one ,however.I was wondering if we ...
1
vote
2answers
39 views
Proving divisibility of numbers
Let us take a two digit number and add it to its reverse.We have to prove that it is divisible by 11.
Same way,if we subtract the larger number from the other,it is divisible by 9.How can we explain ...
0
votes
1answer
14 views
Question involving Legendre symbols
Let r,p,q be distinct odd primes. Let 4r divide p-q. Show that
(r/p) = (r/q)
Where (a/b) is the Legendre symbol.
I'm sure we are suppose to use the law of quadratic reciprocity. I don't think this ...
0
votes
2answers
33 views
Finding a palindromic number which is the difference of two palindromic numbers
Let $X$ and $Y$ be two 4-digit palindromes and $Z$ be a 3-digit palindrome. They are related in the way $X-Y=Z$. How can we figure out $Z$?
2
votes
0answers
84 views
Prime numbers problem - discrete math [duplicate]
Show that natural numbers of the form $n^2+1$ are not divisible by primes of the form $p=4k-1$.
I can't really find a place to start.
Thank you very much in advance,
Yaron.
3
votes
1answer
71 views
Minimum number of coconuts
Three friends namely $A$, $B$ and $C$ collected coconuts with the help of monkey and fell asleep. At night, $A$ woke up and decided to have his share. He divided coconuts into three shares, gave the ...
0
votes
2answers
169 views
RSA: Prove that all messages encrypt to itself
RSA: Prove that all messages encrypt to itself if $p=5$, $q=17$, $e=33$.
4
votes
2answers
50 views
positive Integer value of $n$ for which $2005$ divides $n^2+n+1$
How Can I calculate positive Integer value of $n$ for which $2005$
divides $n^2+n+1$
My try:: $2005 = 5 \times 401$
means $n^2+n+1$ must be a multiple of $5$ or multiple of $401$
because ...
5
votes
4answers
99 views
Prove or disprove the following statements involving greatest common divisor
Help with prove or disproving either of these statements would be really appreciated, one or the other is fine, I just need a start or a solution to one and I'm sure I could probably figure the other ...
3
votes
2answers
60 views
How to show: if $b \mid a$ and $c \mid a$ and $\mathrm{gcd}(b,c) = 1$, then $bc \mid a$? [duplicate]
A little stumped on this problem, any help would be greatly appreciated.
Show that for all $a,b,c \in \mathbb{Z}$, if $b \mid a$ and $c \mid a$ and $\mathrm{gcd}(b,c) = 1$, then $bc \mid a$.
2
votes
1answer
69 views
Total no. of ordered pairs $(x,y)$ in $x^2-y^2=2013$
Total no. of ordered pairs $(x,y)$ which satisfy $x^2-y^2=2013$
My try:: $(x-y).(x+y) = 3 \times 11 \times 61$
If we Calculate for positive integers Then $(x-y).(x+y)=1.2013 = 3 .671=11.183=61.33$
...
3
votes
3answers
79 views
Sum of two squares in a $\Bbb Z/p\Bbb Z$
I need to show that every element in $\Bbb Z/p\Bbb Z$ can be written as a sum of two squares. The case $p=2$ is trivial and $0$ is always $0^2 + 0^2$. So all I have to do is show that every element of ...
1
vote
1answer
76 views
Showing that $45083 $is prime
The question is:
Does $\;x^2 + 10x + 15 = 0\pmod{45083}\;$ have a solution?
I can rearrange this to $(x+5)^2 = 10\pmod {45083} \;$ so if I can show that $10$ has a square root mod 45083, I'm done.
...
3
votes
3answers
73 views
Determine number of non-negative integer solutions for both equalities
$$x_1 + x_2 + x_3 = 6$$
$$\dbinom{3+6-1}{6} = \dbinom{8}{6} = 28 \text{ possible integer solutions} $$
$$x_1 + x_2 + x_3 + x_4 + x_5 = 15$$
$\dbinom{5+15-1}{15} = \dbinom{19}{15} = 3876 \text{ ...
1
vote
3answers
71 views
Show that any non-negative integer can be expressed as sums of 2 and 5
$n \ne 1$ and $n \ne 3$, where $n = \{0,1,2,3,...\}$. You cannot use $-2$ or $-5$. For example, $14$ can be expressed as $5 + 5 + 2 + 2$.
I feel like this could be proved inductively using two ...
1
vote
1answer
93 views
Prove or disprove: There exists an integer $k\geq 4$ such that $2k^2 -5k+2$ is a prime number
Prove or disprove: There exists an integer $k\geq 4$ such that $2k^2 -5k+2$ is a prime number.
If true (which I'm pretty sure it isn't), then the proof needs to be in either contradiction or ...
1
vote
3answers
149 views
Prove that if $a, b, c$ are positive odd integers, then $b^2 - 4ac$ cannot be a perfect square.
Prove that if $a, b, c$ are positive odd integers, then $b^2 - 4ac$ cannot be a perfect square.
What I have done:
This has to either be done with contradiction or contraposition, I was thinking ...
5
votes
1answer
89 views
Express an even number as a sum of primes
Show that every even natural number grater than $2$ can be expressed as a sum of two prime numbers.
No idea how to prove this. Can you help? thanks
1
vote
3answers
66 views
question in number theory
Let $p$ is an odd prime and $n$ is an even natural number. It is clear that $2$ divides $p^n+1$. I would like to know Is the following claim true?
$4$ does not divides $p^n+1$.
1
vote
2answers
73 views
Strategies to solve congruence problems
Which strategy is best to use when solving problems of the following sort? $$x^{29} \equiv 3\pmod {184}$$
3
votes
1answer
45 views
Proof involving division algorithm
I'm trying to prove the following.
Let $\text{m}$ and $\text{n}$ be positive integers, $\text{n} \gt
\text{m}$. Prove that if $\text{n}$ divided by $\text{m}$ leaves
remainder $\text{r}$, then ...
4
votes
0answers
65 views
Determine the least prime $p$ for which $2^{p-1} \equiv 1 \pmod {p^2}$.
Determine the least prime $p$ for which $2^{p-1} \equiv 1 \pmod {p^{2}}$ .
3
votes
2answers
58 views
solution set for congruence $x^2 \equiv 1 \mod m$
if $m$ is an integer greater than 2, and a primitive root modulo $m$ exists, prove that the only incongruent solutions of $x^2 \equiv 1 \mod m$ are $x \equiv \pm 1 \mod m$.
I know that if a primitive ...
4
votes
2answers
61 views
$(p-2)!-1 \neq p^k$ for any $k\in \mathbb{N}$, $p$ is a prime.
$(p-2)!-1 \neq p^k$ for any $k\in \mathbb{N}$, $p>5$, $p$ is a prime.
How to solve this?
0
votes
2answers
63 views
Is 1 bigger than 0.99999… or they are equal? [duplicate]
Here is question which always disturbs me. Could somebody help me?
Is 1 bigger than 0.99999...... or they are equal?
Thanks for your help.
0
votes
1answer
19 views
Congruence proof using gcd concepts
Anyone can help me? The problem is:
We have that $a \equiv b (\mod p)$, $x|a, x|b$, and $x$ and $p$ are relative primes, $\gcd(x,p)=1$. How to show that $\dfrac{a}{x} \equiv\dfrac{b}{x} (\mod p)$?
...
1
vote
1answer
44 views
Finding $\gcd$ in the ring of integers
Let $p$ be a prime number, $p\neq 2,13$. Suppose that $p$ divides an integer of the form $a^2+13b^2$, where $a,b$ are integers and coprime.
I want to show that $p=\gcd(p^2,a^2+13b^2)$.
I think ...
32
votes
6answers
2k views
Is $2^{218!} +1$ prime?
Prove that $2^{218!} +1$ is not prime.
I can prove that the last digit of this number is $7$, and that's all.
Thank you.
2
votes
1answer
48 views
Calculate or bound infimum
Let $a_1, \ldots, a_n \in\mathbb R$ and nonnegative let $b\geq1$ and $c\in [0,1]$.
Calculate or bound from above
$$
\inf \left\{d>0: \sum_{i=1}^n \ln ...
4
votes
2answers
80 views
$m$ is a perfect square iff $m$ has an odd number of divisors?
Is this proof that $m$ is a perfect square iff $m$ has an odd number of divisors correct?
$\Rightarrow)$ If $m$ is a perfect square there is an $x$ such that $x = m/x$. The rest of the divisors ...
5
votes
2answers
130 views
How to prove that for all $m,n\in\mathbb N$, $\ 56786730 \mid mn(m^{60}-n^{60})$?
How to prove $\forall m,n\in\mathbb N$:
$$ 56786730 \mid mn(m^{60}-n^{60})?$$
Thanks in advance.
0
votes
3answers
210 views
Proving that every $x \in \mathbb Z_{20}$ satisfies $x^4 - 10x^2 + 9 \equiv 0 \mod 20$
Could you help me with the problem below?
Prove that for every $x \in \mathbb{Z}_{20}$ we have $x^4 - 10x^2 + 9 \equiv 0 \mod 20$.
Thank you.
6
votes
1answer
72 views
How to prove $\sum_{i=1}^{n-1}\frac{1}{\operatorname{lcm}(a_i,a_{i+1})}\lt1$ where $a_i\in\mathbb N$ and $a_i\lt a_{i+1}$?
Let $a_1,a_2,\ldots ,a_n\in\mathbb N$ and $a_1\lt a_2\lt\cdots\lt a_n$. Then how to prove $$\sum_{i=1}^{n-1}\frac{1}{\operatorname{lcm}(a_i,a_{i+1})}\lt1$$
Thanks in advance
1
vote
1answer
108 views
Finding All Integers in such that $\phi(n)=80$
I don't know where to start with this problem so please help. The problem is:
Find all integers n such that $\phi(n) = 80$.
0
votes
2answers
44 views
Proving two Complexes' Numbers Properties
I'm having problem working with complex number on this question and was wondering if someone can walk through with me their reasoning on how to solve this/these types of questions. Thanks in advance!
...
3
votes
1answer
46 views
$\gcd\left(a+b,\frac{a^p+b^p}{a+b}\right)=1,~~ \text{or}~~p$
Let $p$ be prime number ($p\gt2$) and $a,b\in\mathbb Z$ ,$a+b\neq0$ ,$\gcd(a,b)=1$ how to prove that $$\gcd\left(a+b,\frac{a^p+b^p}{a+b}\right)=1~~\text{or}~~ p$$
Thanks in advance .
4
votes
2answers
90 views
For any integer $a$, $a^{37} \equiv a \left( \text{mod } 1729\right)$
For any integer $a$, $a^{37} \equiv a \left( \text{mod } 1729\right).$
We're asked to use Euler's Theorem to prove this.
What I've tried:
$\phi(1729)=\phi(7)\phi(13)\phi(19)=1296$.
If ...
2
votes
0answers
60 views
Show that if $1+\frac {1}{2}+\frac{1}{3}+\cdots +\frac {1}{p-1}=\frac {a}{b}$then a is divisible by $p^2$ [duplicate]
Here $p$ is a prime number, grater than 3.
I can not understand how do I start.Actually I found this problem from Herstein of page 112.I need some hints plz..
Edit : The original post said ...
1
vote
2answers
66 views
When are both fractions integers?
The sum of absolute values of all real numbers $x$, such that both of the fractions $\displaystyle \frac{x^2+4x−17}{x^2−6x−5}$ and $\displaystyle \frac{1−x}{1+x}$ are integers, can be written as ...
11
votes
4answers
119 views
how to solve $1!+2!+3!+…+x!=y^{z+1}$where $x,y,z\in \mathbb N$?
how to solve the following equation where $x,y,z\in \mathbb N$ $$1!+2!+3!+...+x!=y^{z+1}$$
Thanks in advance
1
vote
4answers
144 views
Modulo and euclidean division - Is Wikipedia correct or not?
In the Wikipedia article describing the Modulo operation, Raymond T. Boute introduces the Euclidean Definition, where the remainder is always positive and therefore consistent with Euclidean Division. ...
1
vote
1answer
49 views
Why is this fact about the totient function true? [duplicate]
$\displaystyle \sum_{k<n}_{gcd(k,n)=1}k = \frac{1}{2} n \phi(n)$
This is a homework problem. I would ideally like to get to the final proof on my own. But at the moment I can't even decide how to ...
0
votes
1answer
38 views
A congruence in multiple variables
The following was a question on a homework assignment that has already been submitted/collected.
Show that the following equation has no integer solutions.
...
