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

learn more… | top users | synonyms (1)

2
votes
1answer
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 ...
2
votes
3answers
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 ...
2
votes
1answer
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 ...
2
votes
2answers
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$, ...
2
votes
3answers
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 ...
2
votes
2answers
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$$ ...
2
votes
3answers
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 ...
2
votes
1answer
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.
2
votes
2answers
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 ...
2
votes
1answer
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)$?
2
votes
1answer
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 ...
2
votes
2answers
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? ...
2
votes
1answer
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 ...
2
votes
2answers
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 ...
2
votes
2answers
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: ...
2
votes
1answer
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 ...
2
votes
1answer
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 ...
2
votes
1answer
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 ...
2
votes
3answers
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$ ...
2
votes
2answers
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?
2
votes
1answer
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 ...
2
votes
1answer
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 ...
2
votes
1answer
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 ...
2
votes
1answer
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$.
2
votes
2answers
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 ...
2
votes
1answer
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 ...
2
votes
1answer
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 ...
2
votes
1answer
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 ...
2
votes
3answers
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 ...
2
votes
1answer
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$. ...
2
votes
1answer
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 ...
2
votes
2answers
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?
2
votes
1answer
93 views

How many ordered triples $(a, b, c)$ exist?

How many ordered triples $(a, b, c)$ of positive integers exist with the property that $abc = 500$? Breaking it up, $500 = 2^2\cdot5^3$ $abc = 2^2 \cdot 5^3 = 2\cdot 2 \cdot 5 \cdot 5 \cdot ...
2
votes
2answers
104 views

Calculating $2^{9999 }$ mod $100$ using Fermats little Theorem

By a modified version of the Fermat's little theorem we obtain that $a^{\phi(n)} \equiv 1$ mod $n$ whenever $(a,n)=1$. But my professor accidentally gave this question to calculate $2^{9999 }$ mod ...
2
votes
1answer
157 views

Checking the IBAN and dividing large numbers mod 97. Why does it work?

What's the reason (or is there an easy explanation) of why it is possible to calculate the division mod $97$ of a large number by first calculating it for the first $9$ (or $6$?) leftmost digits and ...
2
votes
1answer
101 views

Proving the existence of a bijection between $U_{mn}$ and $U_m \times U_n$ where $(m,n)=1$ , there by proving Euler $\phi$ is multiplicative

Without proving before hand that Euler's phi $(\phi)$ function is multiplicative , can we prove that there is a bijection between $U_{mn}$ and $U_m \times U_n$ , for any pair of relatively prime ...
2
votes
2answers
145 views

For every natural number $n$, $ 3^{3n} - 1$ is divisible by $26$.

Use induction to prove that for every natural number $n$, $ 3^{3n} - 1$ is divisible by $26$. I can see that for $n=1$, $ 3^{3} -1=26\cdot 1$. As for inductive step, assuming that the statement ...
2
votes
1answer
176 views

Number of equivalence classes of binary sequences which differ only by finitely many elements.

This question rose up when i was reading a problem the author used to argue against the axiom of choice. Consider the set of all (infinite) sequences of 0's and 1's. Q1) How many such sequences are ...
2
votes
2answers
140 views

How to find the numbers of Bezout identity for two numbers

I'm having troubles finding two numbers a,b such that $ 288a+177b=3=gcd(177,288) (1) $ I've been writing the equations of the Euclids algorithm one over another many times to get any pair that verify ...
2
votes
1answer
73 views

Insight into Abel's impossibility theorem

Let 's consider the polynomial of degree $7$:$$f(x)=x^7-28x^6+ 322x^5-1960x^4+6769x^3-13132x^2+13068x-5040 $$ I am trying to get some insights into Abel's impossibility theorem. Does this theorem ...
2
votes
1answer
65 views

Improving the inequality $x\sigma_1(x) \leq \sigma_1(x^2)$ for $x \in \mathbb{N}$

Let $\mathbb{N}$ be the set of positive integers. For $x \in \mathbb{N}$, $\sigma_1(x)$ gives the sum of the divisors of $x$. (For example, $\sigma_1(3) = 1 + 3 = 4$.) We call the ratio $I(x) = ...
2
votes
2answers
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 ...
2
votes
1answer
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)$ ...
2
votes
2answers
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 ...
2
votes
2answers
81 views

Cracking license plate checksum

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 ...
2
votes
2answers
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 ...
2
votes
2answers
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 ...
2
votes
1answer
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$ ?
2
votes
1answer
146 views

Find sum of possible pairs for given LCM and GCD

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)$, ...
2
votes
1answer
154 views

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 ...