# Tagged Questions

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

48 views

### There exists a number expressible as the sum of $2015$ $2014$th powers in at least two ways

Prove that there exists a positive integer that can be written as the sum of $2015$ $2014$th powers of distinct positive integers $x_1 <x_2 <\ldots <x_{2015}$ in at least two ways. How can I ...
75 views

### Find $n$ when given $12.3 + 16.4(n-1) - 4.1\left\lfloor\frac{n-1}{5}\right\rfloor$

Pardon me if this question has been posted incorrectly here. My question is pretty simple. I am designing a timer in Arduino and the number of counts required to go for $n$ number of seconds vary ...
74 views

### For which values of $n$ can $x^n+y^n$ be a perfect square?

Let $x, y$ and $n$ be positive integers. Using Fermat's Last Theorem we can show that $x^n+y^n$ can't be a perfect square if $n$ is divisible by $4$, but when $n=3$ we have some simple solutions like ...
80 views

### Ramanujan's conjecture

If $p(n)$ is the number of ways in which the number $n$ can be expressed as a sum of positive integers then find $p(200)$. [I know that] $p(1) = 1$, $p(2) = 2$, $p(3) = 3$, $p(4) = 5$, $p(5) = 7$, ...
44 views

### Chinese Remainder Theorem for $x\equiv 0 \pmod{y}$

Can anyone solve the following system of congruences using CRT step-wise, without skipping any part? $$\begin{cases} x\equiv 3 \pmod{7}\\ x\equiv 3 \pmod{13}\\ x\equiv 0 \pmod{12}\end{cases}$$ The ...
103 views

### Solving an equation $\pmod {13}$

Suppose: $$1 + \frac12 +\frac13 + \dots + \frac1{23} = \frac{a}{23!}$$ I would like to find $a \pmod {13}$. My attempt: I'm attempting to use Wilson's theorem which states: $$(n-1)!= -1 \pmod n$$ ...
30 views

### factoring zero in modulo n

Let $m,n\in \mathbb{N}$. How many different classes $\overline{y}\in\mathbb{Z}_n$ are there, so that $$\overline{m}\cdot \overline{y}=\overline{0}$$ Each element is either invertible or a factor of ...
96 views

### Prove that every number $n \geq 12$ is the sum of two composite numbers

Prove that any natural number greater than or equal to 12 is the sum of two composite numbers.
116 views

### Stuck when tackling the computation of $\Phi_n(\zeta_8)$

My current way of calculation of $\Phi_n(\zeta_8)$ where $\Phi_n(x)$ is the $n$-th cyclotomic polynomial and $\zeta_8=\cos(\frac{2\pi}{8})+i\sin(\frac{2\pi}{8})$ leave me now stuck at the problem of ...
57 views

### Condition such that $ax + by = c$ with real coefficients has exactly one integer solution

What conditions must $a,b \in \mathbb R$ satisfy in order for $$ax + by = c, \; c \in \mathbb R^*_+$$ to have exactly one integer solution $(x_0,y_0)$?
21 views

### Prove the following conditional divisibility

If $gcd(a,b)=1$ and $n$ is a prime number,then prove that $\frac{(a^n + b^n)}{(a+b)}$ and $(a+b)$ have no factors in common unless $(a+b)$ is a multiple of $n$. I don't know how to establish the ...
65 views

### Extension of Fermat's Little Theorem

I just read about Fermats little theorem and was wondering if the following relationship is an extension of this: $7^{8n+3}+2$ = 5p where p is an real integer. If so can you show me how/why this is? ...
55 views

### Proving infinitely many primes (or none) for a given polynomial, e.g. $n^4+4$

I've recently started self-studying through Niven's Introduction to the Theory of Numbers and had questions on a few of the problems. In particular, I'm not sure how to show that $n^4+4$ is composite ...
63 views

### Simple Division Proof

Prove that for every three integers i, j, and k, if i $\nmid$ jk, then i $\nmid$ j We've just started proofs and I am at a complete loss for how to go about doing it. I've tried proving through ...
29 views

### How many solutions are there to $ad\equiv bc \bmod p$

Suppose that $0\leq a,b,c,d\leq p-1$, where $p$ is a prime. Then how many solution are there to $ad\equiv bc \bmod p$? We can work out the case $p=2$. Suppose that $p>2$. My approach is this: ...
48 views

### If $a^2+2b+c$, $b^2+2c+a$, and $c^2+2a+b$ are all perfect squares

Let $a,b,c$ (with $a,b,c>1$) be postive integers,and such that $\color{#0a0}{\text{$a^2+2b+c$}}$, $b^2+2c+a$, and $c^2+2a+b$ are all perfect squares. Show that: $$a+b+c=276$$ We note that ...
94 views

### Sum of Two Squares Why not others

So why can some integers be written as the sum of two squares: For example: $5 = 4 + 1$ and $100 = 64 + 36$. Why aren't some others like these. Why 7, 19, and 1295 are not the sums of squares. Can ...
67 views

### How to prove a quadratic Diophantine equation has no solution?

Take the equation $3x^2-5y^2+7z^2 = 0$. If we take this $mod \: 4$ we get: $3x^2+3y^2+3z^2 \equiv 0 \: mod \: 4$ All of the squares modulo $4$ are either $0$ or $1$. $3x^2+3y^2+3z^2$ will never be ...
67 views

### Prove the existence of a prime $p$ such that $2^p -1$ is composite, without trial and error

In my discrete mathematics book under existence proofs it has Prove that there exists a prime $p$ such that $2^p -1$ is composite. It then goes on to say by trial and error we find $2^{11}-1$ ...
152 views

### Even/Odd Binomial Coefficients

I was wondering if there's a nice general solution for the following problem: How many numbers in the $n^\text{th}$ row of Pascal's triangle are even? How many are odd?
50 views

### polynomials such that $P(k)=Q(l)$ for all integer $k$

In a book I have read this problem: Given $P\in \mathbb{R}[X]$, if $P(X)$ takes at every integer, a value which is the $k$-th power of an integer, then $P(X)$ itself is the $k$-th power of a ...
109 views

### For an odd prime $p$, prove that the quadratic residues of $p$ are congruent modulo $p$ to the integers

For an odd prime $p$, prove that the quadratic residues of $p$ are congruent modulo $p$ to the integers $$1^2,2^2, 3^2,\ldots, \left(\dfrac{p-1}{2}\right)^2$$ I know Euler's criterion but not sure ...
84 views

### Generalization of Euler's totient theorem (aka Fermat–Euler theorem)

I am solving some math competition questions, and I realized that I do not know of a rigorous solution for this problem: What is the units digit of $2^{2015}$? We can easily see that the units ...
60 views

### Existence of two primes satisfying the given conditions

I want to know whether the equation $x^a-x=y^b-y$ has a solution or not satisfying the conditions that $x$ and $y$ are distinct odd primes, $a$ and $b$ are integers both greater than $1$.
65 views

### Finding Smallest x and y to Satisfy Equation

Find the smallest natural numbers $x$ and $y$ such that $$7^2x=5^3y$$ I'm unsure how to proceed with this question. Could someone explain the process for determining the answer? Added from the ...
42 views

### $S=\{0,1,2,…,q^2-1\}$, is there a way to figure out how many elements contained in $S$ can be written as the sum of $2$ squares?

I'm currently working on a proof, and have broken it down into a series of problems. I've had success with every part except one. My question is (and it may be really easy; it's getting late): 'Let ...
67 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 ...
84 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 ...
481 views

### Collatz conjecture: Largest number in sequence with starting number n

This question is inspired by a CS course, and it only tangentially relates to the actual content of the exercise. Say in a hailstone sequence (Collatz conjecture) you start with a number n. For any ...
75 views

### Prove that the quotient of a nonzero rational number and an irrational number is irrational

$0\neq a\in \mathbb Q, b\in \mathbb R \setminus\mathbb Q \text{ (b is irrational)}$ Prove that $\frac a b$ is irrational. From defintion $a=\frac m n$ such that $m,n\in \mathbb Z, n\neq 0$. ...
39 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 ...
54 views

### Solve diophantine using modulus

Find all pairs of positive integers $(m, n)$ that satisfy, $mn + 3m - 8n = 59$ Using Modular arithmetic. Okay, this is a diophantine equation, where can I begin?
93 views

84 views

### Consecutive cubes equal to a square $\frac{1}{8}ab(a^2+b^2-1) = y^2$, and Pythagorean triples

If we wish that the sum of $b$ consecutive cubes with initial cube $c=\tfrac{1}{2}(1+a-b)$ is equal to a square, then we have the rather simple equation, $$F_k=\tfrac{1}{8}ab(a^2+b^2-1) = y^2$$ It ...
109 views

### Pythagorean Triples Recursion

I know that all the primitive Pythagorean triples can be generated from the $(3,4,5)$ triangle by using the three linear transformations $T1$, $T2$, $T3$ below: $T1$ : $(a−2b+2c,2a−b+2c,2a−2b+3c)$ ...
194 views

### prime factors of number with a particular form

I try to factorize this huge number $2^{3^{5^{7}}}$+ $7^{5^{3^{2}}}$ .but i have no idea,the only thing i know is that it's not divisible by 7 and 11. can you help me find some prime factors of this ...
81 views

Suppose a city has license plates assigned to cars with 7 digits $a_1$ to $a_7$ and a checksum calculated by the following algorithm: ($m_k$ are integers) $$m_1a_1+m_2a_2+\cdots+m_7a_7\mod 28$$ (which ...
226 views

### How many prime number factors are there for 420(base 6)?

I don't know the actual approach. I did it this way: $2\cdot210=420$ (base 6) $2\cdot103=210$ (base 6) $3\cdot21=103\;$ (base 6) Now $21$ (base 6) $= 13$ (base 10) = prime So, the total number of ...
69 views

### Does this proof work?

let $a,b \in \mathbb{Q^c}$ and define $b> a$ prove that there exists a rational number x where $b>x>a$ I have seen this proof done in a few ways some in textbooks others on this site form ...
30 views

### A possible defining characteristic of primitive roots.

If $n$ is a primitive root $\bmod p$ ($p$ is an odd prime ) does there always exist a least residue $t$ such that $n^t \equiv t \pmod p$ ?
I am given $A$ and $B$. I have to find out sum of $(m+n)$ for all pairs of numbers where $m\leq n$, $\gcd(m,n)=B$ and $\operatorname{lcm}(m,n)=A$ For $A=72$, $B=3$ Possible pairs will be - $(3,72)$, ...
### Find the greatest integer $N$ such that no two of its digits are equal and each digit is also its factor
$N$ is a positive integer such that no two of its digits are equal and each digit is also its factor. What is the largest value of $N$? So far, I've determined that $0$ cannot be the last digit, and ...