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

learn more… | top users | synonyms (1)

0
votes
1answer
15 views

Modular Multiplicative Inverse / Euclidean Algorithm

There's a method of obfuscating programs which is around that turns code like: my_int32 = my_value into ...
1
vote
0answers
11 views

Maximal $n$ such the the additive partition with a given product is unique.

Given $n$, there are many tuples with $a + b + c = n,a < b < c$. For large $n$, different tuples may give the same products. E.g. $2+8+9=19=3+4+12,2\times8\times9=144=3\times4\times12$. What is ...
1
vote
1answer
18 views

Generalization of a Result on Modular Inverses

Yesterday, I attempted to solve the general system of linear congruences (I'm not sure why I've never tried this before.) \begin{align*} x &\equiv a \pmod{A} \\ x &\equiv b ...
1
vote
0answers
40 views

Find positive integer x,y,z such that $2x^{2x}-1=y^{z+1}$

Find all positive integer x,y,z such that $2x^{2x}-1=y^{z+1}$ I have tried to use LTE lemma but it didn't work. I think my problem is $z+1$. I can not control it. When I use LTE lemma, the purpose ...
0
votes
1answer
27 views

Prove that $\sum_{t \vert n} d^3(t) = (\sum_{t \vert n}d(t))^2$ for all $n \in \mathbb{N}$ [duplicate]

here $d(n)$ counts the number of positive divisors of $n$. I've tried 2 things: Using Bell series. But then again it just showed me that the bell series of the square of a function is not the ...
0
votes
5answers
109 views

Why is reminder of $8^{30} / 7$ same as that of $1^{30} / 7$

I am not able to figure out why the reminder of $8^{30} / 7$ is same as that of $1^{30} / 7$. I know Euclid division $a=bq+r$ but I don't know modular arithmetic, so please explain without referring ...
-1
votes
0answers
60 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 ...
6
votes
2answers
181 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
2answers
63 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
25 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
3answers
44 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 ...
1
vote
1answer
27 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$ ...
2
votes
1answer
56 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
37 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
58 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
42 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
47 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
55 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
29 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
113 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 ...
-2
votes
2answers
44 views

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

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
66 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
50 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)
21
votes
1answer
392 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
43 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
37 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
46 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
41 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
56 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
73 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
61 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
83 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
41 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
30 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
49 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
48 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 ...