Questions on congruences, linear diophantine equations, greatest common divisor, divisibility, etc.

learn more… | top users | synonyms

0
votes
1answer
44 views

Solve $9x^8\equiv 8\pmod{17}$

$$9x^8\equiv 8\pmod{17}$$ Is there a way to solve this with out testing all integers $x$ between $1$ and $17$ ?
4
votes
0answers
40 views

Improvement IMO 1988 $f(f(n))=n+1987$

The following problem was given at IMO 1987. Prove that there is no function f from the set of non-negative integers into itself such that $f(f(n)) = n + 1987$ for every $n$. So I generalized ...
1
vote
0answers
10 views

Three different examples of three consecutive triangular numbers whose sum is a perfect square for n > or equal to 20

Three different examples of three consecutive triangular numbers whose sum is a perfect square for n > or equal to 20. (In other words their sum must be greater than or equal to 400 and must be a ...
1
vote
2answers
50 views

The equation $x^4+y^4=z^2$ has no integer solution

The equation $$x^4+y^4=z^2$$ has no integer solution for $(x, y, z), x \cdot y \neq 0 , z >0$. We suppose that there is a solution $(x, y, z)$. We consider the set $$M=\{z \in \mathbb{N} | ...
2
votes
2answers
26 views

Is there are integer solutions for this equation: $ 65x-4y= 129$ [on hold]

My question is: Is there are integer solutions for this equation: $$ 65x-4y= 129$$
3
votes
0answers
23 views

Rationality and triangles

Consider a triangle with angles $\alpha, 5\alpha, 180-6\alpha$. What is the minimum perimeter of that triangle, if it has integer sides and $5\alpha<90$?. Let's call tha sides that face each ...
1
vote
1answer
23 views

A functional equation over integers

I was working in a problem in number theory and I blocked over the problem : Given functions $f:\mathbb{Z}\rightarrow \mathbb{Z}$, $g:\mathbb{Z^2}\rightarrow \mathbb{Z}$ and ...
0
votes
1answer
35 views

If $p^q - 1$ is a prime, then $p=2$ and $q$ is a prime [duplicate]

I was working my way through some number theoretic proofs and being a newbie am stuck on this problem : If $p$ and $q$ are positive integers ($\mathbb{Z}^+$) such that $q \gt 1$ and $(p^q - 1)$ is ...
0
votes
1answer
15 views

How to use totient function here?

I have asked this before, but I had no idea how to use Totient, now I do here is the questions: How many positive integers $< 2013$ cannot be divided by $2, 3, 5$ ?? An advice given was find ...
0
votes
1answer
7 views

Primitive roots and 'equivalent exponents'.

If M is a primitive root mod p and M = $\ N^T$ mod p , then the order of N mod p is also (p-1) is this true?
1
vote
0answers
20 views

For what positive integer values $b,d$ does $(b^2-d)\mid(b^2-1)?$ hold?

I am curious about the answer to the following questions: And hope that you can help me For what positive integer values $b, d$ does $$(b^2-d)|(b^2-1)?$$ hold? Is it correct that the only ...
1
vote
1answer
41 views

Find all primes $p$ with some given conditions.

Find all primes $p$ such that $p^2-p+1$ is a perfect cube. I found out that p is of the form $18n+1$ and $p=19$ is a solution but I am not getting anything further. $p^2-p-(m^3-1)=0$ ...
1
vote
4answers
57 views

The divisibility of $a^p-1$ by $a-1$ and by $(a-1)^2$

I was working my way through some number theoretic proofs and being a newbie am stuck on this problem : Let a $\geq$ 2 and p be any positive integers , then prove that : $(a-1) \mid(a^p - ...
3
votes
2answers
148 views

Prove that any power of a prime is not a perfect number [on hold]

How do I prove: Let $p$ be a prime, and $n$ be a positive integer. Then $p^n$ is not a perfect number. One example is when $p = 2$ and $n = 3$, the question is to show $8$ is not a perfect ...
2
votes
2answers
48 views

Find the $n$ for which $σ(n) = 15$ [on hold]

$σ(n)$ is the sum of the divisors of $n$, including $n$ itself. Find the $n$ for which $σ(n) = 15$, and also how do I prove that $n$ is unique.
2
votes
1answer
24 views

Convert the following decimal number into 32-bit IEEE floating-point form.

I am given a negative decimal -1234.875. I understand the normal process of solving a question like this, except I am uncertain about handling the negative. What I do is find the binary form of 1234 ...
1
vote
3answers
32 views

Proving by contradiction that if $a\in\mathbb Q,b\in \mathbb R\setminus \mathbb Q$ then $a+b\in \mathbb R \setminus \mathbb Q$

I'm trying to prove by contradiction that if $a\in\mathbb Q,b\in \mathbb R\setminus \mathbb Q$ then $a+b\in \mathbb R \setminus \mathbb Q$, I already proved it with contra position and a direct proof ...
7
votes
0answers
68 views

Olympiad-style question about functions satisfying condition $f(f(f(n))) = f(n+1) + 1$

QN: What functions (from non-negative integers to non-negative integers) satisfy the condition $$f(f(f(n))) = f(n+1) + 1$$ Comment: Evidently $f(n) = n+ 1$ is one solution. Equally evidently no ...
2
votes
1answer
42 views

Formula for $\sum_{d|n} \frac {\mu(d)}d$

I feel like I've seen a formula somewhere for $\displaystyle \sum_{d|n} \frac {\mu(d)}d$, but I can't remember what it is and can't find it. Does anybody know of a formula?
6
votes
4answers
51 views

Calculating Euler's totient function values.

I never understood how to calculate values of Euler's totient function. Can anyone help? For example, how do I calculate $\phi(2010)$? I understand there is a product formula, but it is very ...
0
votes
0answers
25 views

Different methods used to show the existence of integer solutions

Let $A_{n},B_{n},C_{n}$ be three sequences of positive integers. I want to know the different methods used to show the existence of integer solutions $x$ and $y$ for the equation: ...
3
votes
1answer
57 views

Find all natural numbers $a,b,c$ such that $abc+ab+c=a^3$

Find all positive integers $a,b,c$ such that $$abc+ab+c=a^3$$ My try: Clearly $c=ak$ $abk+b+k=a^2$ $b=\frac{a^2-k}{ak+1}$ is an integer but I am not getting anything further
0
votes
1answer
38 views

How does the Euler Totient Function apply here?

How many positive integers $< 2013$ are divisible by $2$ Can I somehow use Euler's Totient function to find this?
1
vote
1answer
16 views

On Inequality Concerning Deficient Numbers

By Definition a positive integer $N$ is d-deficient if $\sigma(N)=2N-d$. Am I correct if I say that the inequality $N>d$ always hold for this definition? Here is my attempt to show that it is ...
2
votes
2answers
56 views

How many positive integers less than $2013$ are divisible by none of $2, 3, 4 ,5$?

How many positive integers less than $2013$ are divisible by none of $2, 3, 4 ,5$? This was an olympiad question. I thought of writing a number $x \le 2012$ in the form: $x = 2^{a}3^{b}4^{c}5^{d} = ...
3
votes
2answers
110 views

Is there an obvious reason why $4^n+n^4$ cannot be prime for $n\ge 2$? [duplicate]

I searched a prime of the form $4^n+n^4$ with $n\ge 2$ and did not find one with $n\le 12\ 000$. If $n$ is even, then $4^n+n^4$ is even, so it cannot be prime. If $n$ is odd and not divisible by ...
1
vote
1answer
36 views

For how many integers is this a prime number?

For how many integers $n$ is: $9 - (n-2)^2$ a prime number? I want to try this using a rigorous definition of prime number/ actual problem rather than try-error? Please only give hints, so I can do ...
0
votes
3answers
28 views

Proving if $a,b$ are even and $c$ is odd, then $ax+by=c$ doesn't have any solutions in $\mathbb N$

Let $a,b,c\in \mathbb Z$. Prove that if $a,b$ are even and $c$ is odd, then $ax+by=c$ doesn't have any solutions in $\mathbb N$. I get that sometimes this can acutally be false. Define ...
5
votes
3answers
58 views

Proving that if $a,b,c\in \mathbb N$ and $a^2+b^2=c^2$ then $abc$ is even.

Let $a,b,c\in \mathbb N$ and $a^2+b^2=c^2$ then $abc$ is even. My attempt: If one or two numbers of $a,b,c$ are even then we're done, so we'll have to show that at least one of them is even. ...
0
votes
2answers
33 views

Congruence definitions equivalence

We say that $x$ is congruent to $y$ modulo $z$ when $$x\equiv y\pmod z \iff x \pmod z = y \pmod z$$ Another definition is $$\quad x \equiv y \pmod z \iff \exists k \in \mathbb{Z}: x - y = k z$$ Why ...
0
votes
1answer
16 views

For the following number, state the base represented as t?

$1011 \textrm{(base }t) = 4931 \textrm{(base 10)}$ I have to find $t$, which is the base of 1011. I do the following: $4931 \textrm{(base 10)} = 4 \times 10^3 + 9 \times 10^2 + 3 \times 10^1 + 1 ...
4
votes
2answers
51 views

Suppose $\sqrt2=a/b$, with $gcd(a,b)=1$. Then $3|(a^2+b^2)$ implies that $3|a$ and $3|b$,

Suppose $\sqrt2=a/b$, with $\gcd(a,b)=1$. Then $a^2=2b^2$, so that $a^2+b^2=3b^2$. But $3|(a^2+b^2)$ implies that $3|a$ and $3|b$, a contradiction. I don't understand how $3|(a^2+b^2)$ implies that ...
4
votes
3answers
100 views

Show that $n^4+4$ is not a prime number

How do you show that for all $n ∈ N, n ≥ 2,$ $n^4 + 4$ is not a prime number? My attempt: I see that whatever number $n^4+4$ makes when $n$ is an even number would result to an even number. Thus ...
1
vote
1answer
28 views

I need Sophie Germain primes in the 7-digit range

About a year ago some one asked if there was a list of ALL Sophie Germain primes. One answer pointed the questioner to: vaxasoftware.com/doc_eduen/mat/primsophie_en.pdf. That list only goes up to ...
0
votes
0answers
28 views

Given a positive integer n show that there exists one and only one pair of integers h and k with 0 ≤ h < k such that n = 1/2 k(k − 1) + h.

Given a positive integer $n$ show that there exists one and only one pair of integers $h$ and $k$ with $0 \leq h < k$ such that $n = \frac{k(k-1)}{2}+h$. I don't really know how to approach this ...
0
votes
1answer
37 views

For what natural number $n$ is the following inequality true: $2^n \geq 2\cdot n^2$?

Can you solve this by using induction? The inequality is true for $n = 1$, but is false until $n = 7$. After the induction step I got $$2^n \geq n^2 + 2n + 1.$$ If you take the limit as $n$ ...
2
votes
2answers
23 views

Can someone help me prove that $\tau(n)$ is odd [duplicate]

Can someone help me prove that $\tau(n)$ is odd if and only if $n$ is a perfect square. So basically I have to prove that $\tau(n)$ is odd iff $n = k^2$ for some integer $k$.
0
votes
1answer
28 views

My proof that there are primitive roots modulo $p^2$

Let $p$ be a prime number. I'd like to prove that there are primitive roots modulo $p^2$. Could someone check this argument? Note that if $r\in\mathbb Z$ is a primitive root modulo $p^2$, it must ...
1
vote
4answers
59 views

Show that if $m^2 + n^2 $ is divisible by $4$, then $mn$ is also divisible by $4$.

Show that if $m$ and $n$ are integers such that $m^2 + n^2 $ is divisible by $4$, then $mn$ is also divisible by $4$. I am not sure where to begin.
2
votes
5answers
105 views

Prove that $2^{3^n} + 1$ is divisible by 9, for $n\ge1$

Prove that $2^{3^n} + 1$ can be divided by $9$ for $n\ge 1$. Work of OP: The thing is I have no idea, everything I tried ended up on nothing. Third party commentary: Standard ideas to attack ...
0
votes
2answers
22 views

Congruence with additional conditions. [on hold]

Let $$\left(ac \equiv bc \pmod m\right) \wedge \left(gcd(c,m) = d\right) \implies a \equiv b \pmod {\frac{m}{d}} $$ Is it true? Why? Thanks in advance.
1
vote
2answers
42 views

Proving rigorously that if $3\mid(a+b)$ then $3\mid(a^3+b^3)$ using divisibility definition

Let $a,b\in \mathbb Z$. Prove rigorously using divisibility definition that if $3\mid(a+b)$ then $3\mid(a^3+b^3)$ After a bit of algebra I get that $$3\overset{?}{\mid}(a+b)^3-3ab(a+b)$$ So now how ...
0
votes
1answer
49 views

How many 10 digit numbers are there so the sum of the digits is $2$?

How many 10 digit numbers are there so the sum of the digits is $2$? $abcdefghij$ is the 10 digit number. By default, $a=1$ is a must. $= 1bcdefghij$ Now we need: $bcdefghij = 1$ How can I solve ...
1
vote
1answer
74 views

Using fermats last theorem in a proof

Question: If $x,y,z,n$ are natural numbers, $x,y,z,n>1$, with $x^n +y^n=z^n$ then show that $x,y,z$ are all greater than $n$ Here to prove this i would like to use Fermat's last theorem, to ...
0
votes
1answer
30 views

Sum of divisor powers?

A given number is divisible by 2, 3, and 5, and has altogether 2013 divisors. The smallest such number is $2^N \cdot 3^M \cdot 5^p$ where $N + M + P=$? I would $N + M + P = 2012$ because by a ...
0
votes
2answers
48 views

Smallest integer $x$ for which 10 divides $2^{2013} - x$

Find the smallest integer $x$ for which 10 divides $2^{2013} - x$ Obviously, $x \equiv 2^{2013} \pmod{10}$ But how can I reduce $x$?
0
votes
2answers
32 views

Why $(10^ab+c)^{4d+1}-c \mid 10$?

I came across the following equation: $$x=(10^ab+c)^{4d+1}-c$$ Why is $x$ a multiple of $10$ for any natural number values for $a$, $b$, $c$ and $d$? The only progress I made was that $a$ could be ...
4
votes
1answer
93 views

If $\frac{a+1}{b}+\frac{b}{a}$ is an integer then it is $3$.

If $\frac{a+1}{b}+\frac{b}{a}$ is an integer for positive integers $a,b$ then prove that this integer is $3$. I reduced the to prove that if $\frac{c^2+d^2+1}{cd}$ is an integer then it is $3$ where ...
0
votes
2answers
35 views

$2^{n+1}|2^{2^n}$ and $2^{2^n}+1|2^{2^{n+1}}-1$

$2^{n+1}|2^{2^n}$ and $2^{2^n}+1|2^{2^{n+1}}-1$ I have not been able to show the above. I would greatly appreciate any help.
2
votes
1answer
16 views

Deduce that the number of divisions in the Euclidean algorithm is at most $2n + 1$

Theorem. If $a > 0$ and $b$ is arbitrary, there is exactly one pair of integers $q, r$ such that the conditions $b = qa + r, 0 \leqslant r < a$, hold. Repeated application of this theorem ...