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

learn more… | top users | synonyms

1
vote
1answer
26 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
52 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
44 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
58 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
20 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
20 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
67 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
23 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
35 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
34 views

Prove elements of a set are not uniquely representable.

Let $E = \{2k: k \in \Bbb{N}\}$, and let $M = \{m = (2r)(4a + 2) : r, a \in \Bbb{N}\}$. Prove that some elements in $E$ are not uniquely representable as products of elements of $M$, e.g. ...
0
votes
1answer
56 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
77 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 ...
3
votes
2answers
43 views

Suggestion to a book with lots of number theory problems

What I am looking for is a book that contains "infinitely many problems", starts from the easiest to high level(that can be found in national and even international olympiads). Are there such books, ...
1
vote
4answers
37 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
70 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
33 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$$
5
votes
1answer
77 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 the sides that face each ...
1
vote
1answer
26 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 ...
1
vote
1answer
10 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
23 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
2answers
64 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$ ...
0
votes
5answers
101 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 ...
2
votes
2answers
59 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
31 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
76 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 ...
0
votes
2answers
53 views

Show that there exists no integer $x$ such that $3x$ is congruent to 5 (modulo 6)

So far my approach was to rewrite the congruency to $5-3x=6t$ for some integer $t$. My problem is I get stuck in trying to show how $5-3x$ is never divisible by $6$.
2
votes
1answer
45 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
58 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
27 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
58 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
22 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
60 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
114 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
29 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
61 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
55 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
101 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$ ...