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

learn more… | top users | synonyms (1)

-1
votes
0answers
38 views

A proposed method for further abstracting prime numbers [on hold]

I previously posted this but I framed it as a question and only inserted my results as an edit several days after the original post was created. Ulam's Spiral is a wonderful discovery. Obviously it ...
5
votes
3answers
78 views

Finding all real numbers x such that $x \lceil x \lceil x \lceil x \rceil \rceil \rceil = 88$

Question: Find all real numbers x such that $x \lceil x \lceil x \lceil x \rceil \rceil \rceil = 88$. The notation $\lceil x \rceil$ means: The least integer which is not less than $x$. My ...
4
votes
3answers
47 views

Find the maximum value of the fraction

Let $a$ and $b$ be positive integers satisfying $\frac{ab+1}{a+b}<\frac{3}{2}$. The maximum possible value of $\frac{a^3b^3+1}{a^3+b^3}$ is $\frac{p}{q}$, where $p$ and $q$ are relatively prime ...
1
vote
2answers
23 views

Modular Quadratic Equation

I'm trying to solve that equation: $x^2-3x-5\equiv0\pmod{343}$ I've completed the square as follows: $x^2-3x-5 \equiv x^2+340x-5\equiv(x+170)^2-170^2-5\pmod{343}\\ (x+170)^2 \equiv 93\pmod{343}\\ ...
2
votes
2answers
31 views

Elementary number theory, compute this sum

My first problem is the following: prove that $4|\sigma(4n+3)$ for any positive integer $n$. This is what I tried: if $1\le m\le n$, then $\sigma(n)=\sum_{\gcd(n,m)=m}m;$ Now the sum of all integers ...
0
votes
0answers
13 views

Solving two diophantine equations.

Find at least one 5-tuple of positive integers which satisfy the following two equations $$a^2-d^2=3(b^2-c^2)$$ $$e^2-b^2=3(d^2-c^2)$$ such that no three of the 5 positive integers $a, b, c, d, e$ ...
1
vote
1answer
34 views

Find a recursion (combinatorial)

Consider sequences that consist entirely of $ A$'s and $ B$'s and that have the property that every run of consecutive $ A$'s has even length, and every run of consecutive $ B$'s has odd length. ...
0
votes
3answers
31 views

Difficult nonlinear system based on max value

Let $ (a,b,c)$ be the real solution of the system of equations $ x^3 - xyz = 2$, $ y^3 - xyz = 6$, $ z^3 - xyz = 20$. The greatest possible value of $ a^3 + b^3 + c^3$ can be written in the form $ ...
1
vote
4answers
56 views

remainder of $a^2+3a+4$ divided by 7

If the remainder of $a$ is divided by $7$ is $6$, find the remainder when $a^2+3a+4$ is divided by 7 (A)$2$ (B)$3$ (C)$4$ (D)$5$ (E)$6$ if $a = 6$, then $6^2 + 3(6) + 4 = 58$, and $a^2+3a+4 ...
0
votes
2answers
41 views

Use proof by contradiction to prove that if $a$ and $b$ are odd integers, then $4 \nmid (a^2+b^2)$.

I have been working through the following proof: Use proof by contradiction to prove that if $a$ and $b$ are odd integers, then $4 \nmid (a^2+b^2)$. Below, I have included screenshots of the ...
0
votes
3answers
36 views

Chinese remainder theorem for three equations?

Is there a straightforward approach for solving the Chinese Remainder Theorem with three congruences? $$x \equiv a \bmod A$$ $$x \equiv b \bmod B$$ $$x \equiv c \bmod C$$ Assuming all values are ...
2
votes
1answer
50 views

How to show $n$ is a prime number?

Let $a$ and $n$ be integers greater than 1. Suppose that $a^n-1$ is a prime. Show that $a=2$ and $n$ is a prime. What can you say about primes of the form $2^n+1$? By ...
0
votes
0answers
50 views

Curious GCD Divisibility Relation

In some of my recent work, I have accidentally discovered in an extremely convoluted manner the following result: Suppose $a,b$ are positive integers less than some other positive integer $c$, and ...
0
votes
0answers
13 views

$S=\{1\le a \le n:(a,n)=1,a^{n-1}\not\equiv 1\pmod n\}$, $T=\{1\le b \le n:(b,n)=1,b^{n-1}\equiv 1\pmod n\}$ iwth composite and prime numbers

I have two sets with $n>2$ natural number: $S=\{1\le a \le n:(a,n)=1,a^{n-1}\not\equiv 1\pmod n\}$ $T=\{1\le b \le n:(b,n)=1,b^{n-1}\equiv 1\pmod n\}$ Can anyone explain me if there are prime ...
-7
votes
1answer
26 views

Find the number of 5 digit positive integers that are divisible by 11 [on hold]

Find the number of 5 digit positive integers that are divisible by 11. Options are $9191$ $8180$ $9190$ $8181$
0
votes
5answers
112 views

Why are sums of powers of 2 able to give all numbers?

It is known that If we sum up a combination of numbers that are positive powers of 2(starting from 0 to infinity), we can get any number possible. (Correct me if this is wrong). Can anyone ...
-1
votes
2answers
42 views

The sum of three natural numbers are $111$, and the three numbers are in geometric progression.

Find all triples of natural numbers $(a,b,c)$ such that $a,b$ and $c$ are in geometric progression, and $a+b+c=111$. Any pointers?
0
votes
1answer
24 views

Probability the range is disjoint

Let $A=\{1,2,3,4\}$, and $f$ and $g$ be randomly chosen (not necessarily distinct) functions from $A$ to $A$. The probability that the range of $f$ and the range of $g$ are disjoint is ...
2
votes
1answer
27 views

Given $n>0$, let $S$ be a set whose elements are positive integers $\leq 2n$ such that:

S is a set with the property that for all a,b∈S with $a<b$, a doesn't divide b. What is the maximum number of integers that $S$ can contain ? I thought it was the number of prime numbers smaller ...
0
votes
3answers
65 views

Integer solutions to $\frac{1}{a} + \frac{1}{b} = \frac{1}{12}$.

$$\frac{1}{a} + \frac{1}{b} = \frac{1}{12}$$ I'm trying to find all integer solutions to this equation. I've played with this equation algebraically to see if I can figure out the restrictions on $a$ ...
-3
votes
2answers
49 views

All natural numbers $m, n$ such that $m = \sqrt{\frac{1}3A^2 - 3n^2}$ [on hold]

I have $m = \sqrt{\frac{1}3A^2 - 3n^2}$. A is a known integer. How do I find all solutions for what m and n are if both m and n are naturals (round positive numbers)
20
votes
1answer
252 views

Is $1992! - 1$ prime?

Consider the factorials, defined inductively by $1! = 0! = 1$ and $n! = n\cdot(n-1)!$ for $n \geq 2$. Question: Is $1992!-1$ a prime number? The question is from a book, maybe is contest math ...
3
votes
1answer
41 views

Proof of Cohn's Irreducibility Criterion

I was looking for an elementary (or involving introductory level abstract algebra/analysis) proof of Cohn's Irreduciblity Criterion: If $$ a_0, a_1, \dots, a_n \in \Bbb{Z} $$ and $$ 0 \le ...
2
votes
3answers
88 views

High computation in probability

Six men and some number of women stand in a line in random order. Let $p$ be the probability that a group of at least four men stand together in the line, given that every man stands next to at ...
1
vote
1answer
36 views

Euler's Phi function, elementary number theory

Show that the equation $\phi(n)=2p$ where $p$ is prime and $2p+1$ is composite has no solutions. Using formula for $\phi$ it's quite easy proving $n$ cannot have more than two prime factors in its ...
-1
votes
1answer
35 views

Is 1 coprime to itself? [on hold]

Is $\{1,1\}$ a pair of co-prime numbers? According to the definition, two numbers are coprime if $\gcd(a,b)=1$, and for $\{1,1\}$ it is true that $\gcd(1,1)=1$.
1
vote
0answers
45 views

Prove that $n \in \mathbb{Z}^\star \Leftrightarrow n \mid 1$ and $n-1 \mid 1$ or $n+1 \mid 1$, and $(x-1)/(t-1) \equiv n \pmod {t-1}$

I want to prove the following lemma: Let $F[t,t^{-1}]$ be the ring of the polynomials in $t$ and $t^{-1}$ with coefficients in the field $F$ and assume that the characteristic of $F$ is zero. ...
2
votes
2answers
87 views

Sum of remainders of $2^n$

Hints Only Let $R$ be the set of all possible remainders when a number of the form $2^n$, $n$ a nonnegative integer, is divided by $1000$. Let $S$ be the sum of all elements in $R$. Find the ...
4
votes
2answers
40 views

Number of divisors of the form $(4n+1)$

Find the number of divisors of $$2^2\cdot3^3\cdot5^3\cdot7^5$$ which are of the form $(4n+1)$ I know how to find the total number of divisors. But, to find the number of divisors of the form ...
2
votes
0answers
21 views

$x-y^4= LCM(x, y)$ [duplicate]

This is a very interesting word problem that I came across in an old textbook of mine. So I know its got something to do with the least common multiple, but other than that, the textbook gave no hints ...
-2
votes
1answer
45 views

Describe a fast (polynomial time)algorithm who takes as input the elements $g^a,g^b$ and gives as output the element $g^{a \cdot b}$

Let $q$ prime number, $G$ a cyclic group with order $q$ and $g \in G$. Suppose that you have an algorithm $A$ who takes input the element $g^a$ of $G$ and gives as output the element $g^{a^2}$. ...
3
votes
3answers
54 views

Nonnegative Integer solutions of $x+y-xy=0$

I would like to see other methods, besides the one I use here to find all the nonnegative integer solutions of an equation like $$x+y-xy=0$$. This is the one I used: First we note that for $x=1$ ...
1
vote
0answers
14 views

Maximum bound of number of prime factors

This comes from the proof of theorem 4.2.1 from The Probabilistic Method by Alon and Spencer. Letting $\nu(n)$ be the number of primes $p$ dividing $n$, here's an excerpt verbatim: Let $x$ be ...
1
vote
2answers
22 views

Algorithm for finding prime numbers of specific form

Given the natural number $n$,who is in the form $p^2 \cdot q^2$,with $p$,$q$ prime numbers.Also $φ(n)$ is given.Describe a fast algorithm(polynomial time) that calculates the $p$ and $q$.Apply your ...
3
votes
3answers
69 views

Is it possible to find integer $n$, $m$ so $6n=7m+1$ without manual search?

I was dealing with a childish problem, which eventually led to this: Find integer $n$ and $m$ to fit the equation $6n=7m+1$ I immediately found first numbers by simple enumeration ($n=6$, ...
2
votes
3answers
60 views

Prove that $\sum_{d|n}\phi(d)=n$ where $\phi$ is the Euler's phi function, $n,c\in\mathbb{N}$

Here is a very elementary number theory proof using strong induction. Please mark/grade. Prove that $$\sum_{d|n}\phi(d)=n$$where $\phi$ is the Euler's phi function, $n,d\in\mathbb{N}$ First, ...
2
votes
3answers
82 views

Explain the proof that the root of a prime number is an irrational number

Though the proof of this is done in a previous question i have a doubt in a certain concept so i ask to clear it.In the proof we say that $\sqrt{p} = \frac{a}{b}$. (In their lowest form.) $p = a^2 ...
0
votes
3answers
40 views

What does P|a means?

In the proof for the existence of unlimited prime numbers, i saw the following let n be the number of prime numbers as P1,P2,P3,.......Pn let a = P1P2P3....Pn+1 a > Pn and a is not a prime number a ...
0
votes
1answer
29 views

What does the symbol $N(\mathfrak{p}_{i})=P^{k_i}$ mean in theorem of Dedekind?

When I was reading an article about linear recurrence relations, I saw this notation: $$P=\mathfrak{p}_1^{e_1}\mathfrak{p}_2^{e_2}...\mathfrak{p}_r^{e_r}$$ $$ N(\mathfrak{p}_{i})=P^{k_i}$$ What is ...
2
votes
2answers
48 views

What is $k$ so that $\frac {1001\times 1002 \times … \times 2008} {11^k}$ will be an integer?

I found this question from last year's maths competition in my country. I've tried any possible way to find it, but it is just way too hard. What is the largest integer $k$ such that the following ...
1
vote
1answer
46 views

How to prove that ways of $n$ of the form $a+bd\ $ equals $\ \varphi(n)?\ $ Where $\ n,\ a,\ b,\ d\ \in \mathbb{Z}^+,\ n > 1,\ d \geq a,\ (a,d)=1$.

How to prove that ways of $n$ of the form $a+bd\ $ equals $\ \varphi(n)?\ $ Where $\ n,\ a,\ b,\ d\ \in \mathbb{Z}^+,\ n > 1,\ d \geq a,\ (a,d)=1,\ \varphi(n) \ $is Euler's totient function.
1
vote
0answers
35 views

On Catalan's complete solution to the equation $T^2=U^2+V^2+W^2$

Catalan proved the following: If $t,u,v,w$ are coprime integers such that \begin{equation*} t^2 = u^2 + v^2 + w^2, \end{equation*} then there exist integers $\alpha,\beta,\gamma,\delta$ such that ...
0
votes
3answers
51 views

How to solve this equation with ceiling function?

Given that $x$ is a positive integer, find $x$ in $(E)$. $$\tag{E} j-n=x-n\cdot\left\lceil\frac{x}{n}\right\rceil$$ All $n, j, x$ are positive integers.
0
votes
0answers
47 views

Applying the sum-of-digits operation to $4444^{4444}$ three times [duplicate]

$A$ is the sum of the digits of $4444^{4444}$. $B$ is the sum of the digits of $A$. Then what will be the sum of digits of $B$? I found this in the question paper of Mathematical Tripos Exam of ...
2
votes
2answers
66 views

How to solve “ways of seating around a circular table”

Recently I asked a question about seating, here it is again: The Annual Interplanetary Mathematics Examination (AIME) is written by a committee of five Martians, five Venusians, and five ...
0
votes
2answers
59 views

Velleman's exercise $3.1.7$

Prove that if $a^3>a$ then $a^5>a$. Velleman gives this "hint": $$\text{One approach is to start by completing the following equation:}\ (a^5-a)=(a^3-a) \cdot x$$ I don't understand this ...
-4
votes
1answer
57 views

Prove that there doesn't exist any integer $x \ge 3$ such that $x^2-1$ is prime. [on hold]

Prove that there doesn't exist integer $x \ge 3$ such that $x^2-1$ is prime.
1
vote
2answers
73 views

How many ways to arrange the seating?

The Annual Interplanetary Mathematics Examination (AIME) is written by a committee of five Martians, five Venusians, and five Earthlings. At meetings, committee members sit at a round table with ...
1
vote
1answer
41 views

How many solutions for $(6b)^b\equiv (12b-k)^b\mod p$?

Rephrasing my previous question; If $(6b)^b\equiv (12b-k)^b\mod p$, where $b$ is odd and $p=1+6qb$, and where $p$ and $q$ are prime, are there any solutions for $k$ other than $k\equiv6b\mod p$?
2
votes
4answers
84 views

If $a^b\equiv c^b\mod p$, can we conclude that $a\equiv c\mod p$?

If $a^b\equiv c^b\mod p$, is is true that $a\equiv c\mod p$, where $b$ is odd and $p$ is prime? We know that if $a\equiv c\mod p$, then $a^b\equiv c^b\mod p$. Is the reverse true?