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

learn more… | top users | synonyms

0
votes
0answers
1 views

Determine all the terns of positive integers a,b,c such that …

Determine all the terns of positive integers a,b,c such that
0
votes
1answer
23 views

range of numbers that can be represented with 32 and 64 bit

I have a question about range of number in base 10 that can be represented with 32 and 64 bit. a) binary encoding(base 2) - I assume its 2^32 and 2^62. b) 8 bit ASCII using an even parity bit - I ...
1
vote
0answers
19 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
35 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
45 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
147 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
46 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
23 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
67 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 ...
1
vote
1answer
40 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
48 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
21 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
56 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
36 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
53 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
109 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
27 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
32 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
50 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
99 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
35 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
27 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
57 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
100 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
20 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
39 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
48 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
29 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
47 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
88 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
34 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
15 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 ...
0
votes
1answer
35 views

Show that the solution for the Diophantine equation $x^2 - y^2 = N$ is unique if and only if $|N|$ or $\frac{|N|}{4}$, respectively, is $1$ or prime.

Show that the solution for the Diophantine equation $x^2 - y^2 = N$ is unique if and only if $\mid N \mid$ or $\frac{\mid N \mid}{4}$, respectively, is $1$ or prime. I have an idea of how to show ...
3
votes
1answer
38 views

Prove for any integer $N$ that there exists $n > N$ where $n!-1$ is not a prime

I was thinking about Euclid's proof of the infinitude of primes and the fact that we could make the argument about $n!-1$ instead of $n!+1$ when I wondered if it would be easy to prove that for any ...
0
votes
2answers
54 views

$\mathrm{lcm}(b,c)$ from $\mathrm{lcm}(a,b)$ and $\mathrm{lcm}(a,c)$

Given that lcm$(a,b)=60$ and lcm$(a,c)=270$, find lcm$(b,c)$ I believe you're supposed to use the rule lcm$(a,b)=p_1^{\text{max}(r_1,s_1)}\cdots p_m^{\text{max}(r_m,s_m)}$ Here's my work so far: ...
0
votes
1answer
9 views

“Multivariable” version of this lemma about showing analytically that a number is irrational.

Lemma: let $\alpha \in \mathbb{R}^+$ and $p_1,p_2,\dots, q_1, q_2, \ldots \in \mathbb{N}$ such that $\left|\alpha q_n - p_n \right| \neq 0$ for all $n \in \mathbb{N}$ and $$ \lim_{n \rightarrow ...
3
votes
1answer
59 views

Could someone take a crack at this number theory problem?

The question is stated as follows: If $\mathrm{gcd}(a,m)=1$ and $X$ is a complete residue system $\bmod m$, then the set obtained by multiplying each member of $X$ by $a$ is also a complete residue ...
1
vote
1answer
53 views

Numbers that can be represented by 32 bits

A typical computer 'word' is either 32 or 64 bits long. For each of the following encoding, determine the range of numbers (in base 10) that can be represented with (i) 32 bits and ...
0
votes
1answer
34 views

How to prove $V(5x^2+6xy+2y^2-2yz-z^2)$ is empty

Let $V/\mathbb{Q}$ be the projective variety $V:5x^2+6xy+2y^2=2yz+z^2$. I want to prove $V(\mathbb{Q})$ is empty. Given $[x,y,z]$ in $V$, WLOG assume $x,y,z\in \mathbb{Z}$ and $\gcd(x,y,z)=1$. ...
0
votes
2answers
48 views

Find the number which is the sum of different consecutive integers

Problem: Find $n$ such that $n>200$ $n$ can be written like the sum of of $5$, $6$, and $7$ consecutive integers I'm currently studying modular arithmetic so I tried to solve witusoinh it. ...