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

learn more… | top users | synonyms

1
vote
1answer
13 views

existence of solution to congruence $x^4 \equiv -4 \pmod p$

I stuck with the following question: For which $p$ (prime numbers) there is a solution for the following congruence: $x^4 \equiv -4 \pmod p$ I would greatly appreciate any help
0
votes
2answers
20 views

Splitting sum into two sums

Assuming that $f$ is a multiplicative arithmetic function. Let $n_1,n_2\in \mathbb{N}$ with $gcd(n_1,n_2)=1$. Consider the sum $$\large S=\sum_{a\mid n_1n_2}f(a).$$ Can I split the sum $S$ into two ...
0
votes
1answer
24 views

Definable real numbers

Reading this Wikipedia page I found this definition: A real number $a$ is first-order definable in the language of set theory, without parameters, if there is a formula $\phi$ in the language ...
1
vote
3answers
24 views

Difficult proof about coprime and factors of numbers!

I am attempting a proof but it is driving me insane as I cannot see what I should do. Given that $a$ is coprime to be $b$ and that $a|c$ and $b|c$ prove $ab|c$. I simply wrote down what I know and ...
2
votes
1answer
31 views

What is the point of big Oh notation when it is used for estimation?

I'm reading a book on number theory at the moment that assumes familiarity with big Oh notation...and while I think I do understand the notation I cannot understand the point of it. For instance let ...
4
votes
2answers
67 views

A puzzle about a sum and product of two numbers

The Gray Man wants to test The Hardy Boys. He says to them, "I've selected 2 positive integers, both bigger than one." He then proceeds to reveal their total and product to Frank and Joe ...
1
vote
1answer
16 views

Understanding the zeta function as it is used in the first step of a proof for Dirichlet's Theorem

I am reading through M. Ram Murty's Problems in Analytic Number Theory and have the following question regarding the first step in his proof of Dirichlet's Theorem. Given this definition for the zeta ...
1
vote
1answer
20 views

If $x$ is a square modulo two primes, then it is a square modulo their product

$a, b$ be integers, $p, q$ primes. If $x \equiv a^2 $ (mod $p$) and $x \equiv b^2$ (mod $q$), then $x \equiv c^2$ (mod $pq$) for some interger $c$. I attempted to use Chinese Remainer Theorem, ...
0
votes
0answers
16 views

Positive solutions of a diophantine equation

When looking at the positive solutions on $x,y \in \mathbb{Z}$ of the equation: $$ax+by=c$$ with $a,b \in \mathbb{N}$ Granted that $g = gcd(a,b)$ divides c, we found that the inequality: ...
2
votes
1answer
40 views

Existence of solution to Congruence relation $(x^2-2)(x^2-6)(x^2-3) \equiv 0\pmod p$

I'm taking the final exam in "Number Theory" tomorrow and stuck with: Prove that $\,\,\forall p\in\mathbb{Z}_p\,$ the congruence relation: $$(x^2-2)(x^2-6)(x^2-3) \equiv 0\pmod p$$ has a ...
0
votes
3answers
37 views

Is this mod equality true?

I wish I could add my thoughts here, but I've really couldn't figure out anything interesting myself. $(a \mod C + b \mod C)\mod C = (a+b) \mod C$
4
votes
1answer
52 views

Prove that there are no positive integers $a, b$ and $n >1$ such that $a^n – b^n$ divides $ a^n + b^n$.

Prove that there are no positive integers $a$ , $b$ and $n>1$ such that $a^{n}–b^{n}$ divides $a^{n}+b^{n}$. Can someone provide me a proof of this and explain it to me please.
1
vote
1answer
17 views

If $r$ is a primitive root of odd prime $p$, prove that $\text{ind}_r (-1) = \frac{p-1}{2}$

If $r$ is a primitive root of odd prime $p$, prove that $\text{ind}_r (-1) = \frac{p-1}{2}$ I know $r^{p-1}\equiv 1 \pmod {p} \implies r^{(p-1)/2}\equiv -1 \pmod{p}$ But some how I feel the ...
0
votes
2answers
11 views

Representing number $X$ in base $r$

In general, let $X = (X_{n−1}X_{n−2}...X_0)_r$ be an n-digit number in base r. Give an algorithm or explain in English how to represent $X$ in base $r^2$. I ...
0
votes
1answer
27 views

Natural numbers not expressible as $x+s(x)$ nor $x+s(x)+l(x)$

For positive integers $x$, let $s(x)$ denote the sum of the digits of $x$, and $l(x)$ denote the number of digits of $x$. It seems that other than $n=1$ and $n=20$, there always exist $x$ such that ...
0
votes
1answer
20 views

Number Theory: Finding specific new square-triangular numbers given that (m, n) satisfied n^2=m(m+1)/2

Ok, so I've been making my way through my beginning number theory homework, and I've come to this problem. In all honesty, I don't even know where to start, so I would greatly appreciate any advice ...
1
vote
1answer
30 views

If $p$ is a prime and $p$ divides $a^3$ then $p$ divides $a$ [on hold]

I have to either give a proof or provide a counterexample for this question. $a, b$ are non-zero intergers. If $p$ is a prime and $p|a^3$ then $p|a$ I think this is true but do not know how to go ...
0
votes
1answer
54 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
72 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 tried to ...
1
vote
4answers
36 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
64 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} | ...
3
votes
2answers
31 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$$
4
votes
0answers
42 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
25 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
36 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
18 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
8 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
22 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 ...
2
votes
1answer
45 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
150 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 ...
3
votes
2answers
51 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
26 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
33 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
70 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
44 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?
7
votes
4answers
57 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
26 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
18 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
59 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
113 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
59 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
17 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
53 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 ...