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

learn more… | top users | synonyms

1
vote
0answers
4 views

Find the $n$ for which $σ(n)$

$σ(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.
0
votes
1answer
14 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
29 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
64 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 ...
4
votes
3answers
35 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
54 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
13 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
52 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
108 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
35 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
24 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
56 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
96 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
27 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
34 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
26 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
55 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
97 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
38 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
85 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
33 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
44 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. ...
3
votes
1answer
55 views

Relationship between increasing integer sequences

Suppose that $\mathcal X\cap \mathcal Y=\emptyset$, that $\mathcal X\cup \mathcal Y=\Bbb N$ and that $X(n),\;Y(n)$ are increasing surjections $\Bbb N\to \mathcal X$ respectively $\Bbb N\to \mathcal ...
0
votes
2answers
36 views

How to solve this quartic congruence?

Given $x^4 + 36x^3 - 19x^2 + 11x - 14 \equiv 0 \pmod{5}$. How would one go about solving such an congruence equation? Maybe it's possible to reduce this to a quadratic congruence? I can't figure it ...
1
vote
2answers
36 views

Let $t_n$ denote the $n$th triangular number. For what values of $n$ does $t_n$ divide $t_1^2+t_2^2+ \cdots +t_n^2$

Let $t_n$ denote the $n$th triangular number. For what values of $n$ does $t_n$ divide $t_1^2+t_2^2+ \cdots +t_n^2$. The hint says that because $t_1^2+t_2^2+ \cdots +t_n^2 = t_n(3n^3 + 12n^2 + 13n + ...
1
vote
2answers
35 views

Criteria for the existence of zero-divisors and idempotent elements in the integers modulo $n$

I need help in establishing or at least deciding the validity of the following two criteria: There are in the ring $Z_n$ non-trivial zero divisors if only if $n$ is divisible with some square. ...
7
votes
4answers
71 views

Proof: if p is prime, and 0<k<p then p divides ${p \choose k}$

Question : IF p is prime, and 0< k< p show that $ p | {p \choose k}$ ${p \choose k}$ can be rewritten as: $${p(p-1)(p-2)... (p-(k-1))(p-k)! \over (p-k)! k(k-1)(k-2)...3.2.1}$$ Now the (p-k)! ...
1
vote
4answers
69 views

Solve $3x \equiv 17 \pmod{2014}$

Solve $$3x \equiv 17 \pmod{2014}$$ So first I suppose $3^{-1} \pmod{2014}$ $2014 = 671(3) + 1 \implies 1 = 2014 - 671(3)$ But this gives $3^{-1} = 1 \pmod{2014}$ which is incorrect?
0
votes
3answers
28 views

Find the Inverse Modulus using Euclid's algorithm

I asked this before, but unfortunately, I didnt know the methods, nor was the questions phrased properly. Find the inverse of $4258 \pmod{147}$ Using Euclidean Extended Algorithm. Begin By Stating ...