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

learn more… | top users | synonyms (1)

1
vote
1answer
16 views

Can it be determined for what $N$ a sum of $k$th powers $\sum_{n=1}^N n^k$ is equal to an $m$th power of an integer?

Can it be determined in some form of closed presentation (e.g. a quick test that can be applied to $N$, or a formula for $N$) for what $N$ a sum of first $N$ $k$th powers $\sum_{n=1}^N n^k$ is equal ...
3
votes
3answers
23 views

How many pairs of positive integers $(n, m)$ are there such that $2n+3m=2015$?

I know that $m$ must be odd and $m\le671$. Also, $n\le1006$. I can't go any further, any help?
2
votes
0answers
24 views

Why do we keep the LCM modulo in the Chinese Remainder Theorem?

I'm doing my homework and I'm struggling to get an answer. I'm taking number theory and we're working on a problem to solve congruences. We've got: $ x\equiv 1 \pmod{5}\\ x\equiv 3 \pmod{8}\\ x\equiv ...
0
votes
2answers
16 views

Let $a,x \in \mathbb{Z}$ and $n \in \mathbb{N}$. Suppose that $ax ≡ 1 \mod n$. Prove that $a$ is coprime to $n$

Let $a,x \in \mathbb{Z}$ and $n \in \mathbb{N}$. Suppose that $ax ≡ 1 \mod n$. Prove that $a$ is coprime to $n$. I have shown that $1=ax-ny$ for some $y \in \mathbb{Z}$ but I don't know if ...
1
vote
0answers
14 views

Question about inclusion exclusion and gcd

For $d_1,\ldots,d_k\in\mathbb{N}$ define $$ L(d_1,\ldots,d_k) = \sum_{j=1}^k (-1)^{j+1}\sum_{1\leq i_1<\ldots<i_j\leq k} gcd(d_{i_1},\ldots,d_{i_j}). $$ Given two integers $n,m$ let $[n,m]$ ...
1
vote
1answer
15 views

Number of primitive polynomial with limited coefficients

We cal a polynomial $f=a_0+a_1x+\ldots+a_nx^n\in\mathbb Z[x]$ primitive iff the greatest common divisor of $a_0, a_1,\ldots, a_n$ is 1. Let $d$ and $m$ be positive integrs and let ...
0
votes
3answers
30 views

prime numbers and divisibility question - number theory

I have a fairly short and straightforward question I would like to ask. Suppose $p_{1},p_{2},...,p_{n}$ are prime numbers. Suppose $X = p_{1}p_{2}...p_{n} + 1$. If $X$ comes out to be a composite ...
0
votes
2answers
35 views

Congruence equation, I have no idea how to do it.

I have here this equation: $10x^{84} + 3x + 7 ≅ 0 (mod 35) $ I can't really do $y=x^{84}$ since I have a simple $x$ too, any other ideas? Thanks! :)
5
votes
5answers
55 views

Prove that for $n \gt 6$, there is a number $1 \lt k \lt n/2$ that does not divide $n$

My nine year old asked this question at lunch today: Is there a number that is divisible by everything that is half or less than the number? I immediately answered, "No. I mean, 6. But not for any ...
2
votes
4answers
47 views

Subtraction of a number

I have a number $x$. If I remove the last digit, I get $y$. Given $x-y$, how can I find $x$? For example x=34 then y=3 given 34-3=31, I have to find 34. if x=4298 then y=429 , given 4298-429 = 3869 . ...
1
vote
0answers
41 views

What are the reduced elements of $\mathbb Q(\sqrt{30})$?

What are the reduced elements of $\mathbb Q(\sqrt{30})$ ? From the definition; An element $\beta\in\mathbb Q(\sqrt{d})$ is said to be reduced, if $\beta>1$ and $-1<\beta'<0$ and ...
0
votes
0answers
29 views

diophantine-equations

Why there are no solutions in positive coprime integers for the following diophantine equation $$2x^3 + y^2 = z^k$$ where, (x,y,z) are (pairwise) positive coprime integers, and k is positive integer ...
0
votes
1answer
17 views

How do I prove this statement about $n^\text{th}$-power residues?

I am studying A Classical Introduction to Modern Number Theory by Ireland and Rosen, and the authors leave the proof of the following proposition (4.2.2) as "an exercise" ... Suppose that $a$ is ...
0
votes
2answers
46 views

If $a$ is prime to $b$, prove that $a^2+b^2$ is prime to $a^2b^2$.

Prove that if $\gcd(a,b)=1$, then $\gcd(a^2+b^2, a^2b^2)=1$. My attempt: If $a$ is prime to $b$ the $gcd(a,b)=1$. Assume that $a^2+b^2$ and $a^2b^2$ are not prime to each other. Let ...
0
votes
1answer
18 views

The divisor function and number of divisors.

Prove $\sigma$(n) $\equiv$ $d(n)$ mod 2 where $\sigma(n)$ is the divisor function and $d(n)$ is the number of divisors of n. So, this is equivalent to saying that $\frac{\sigma(n)}{d(n)}$ $\equiv$ 1 ...
0
votes
2answers
19 views

Number of ways to write n as a sum of consecutive integers [duplicate]

Allow $d(n)$ to be the number of divisors of $n$. Show that there are $d(m)$ ways to write $n$ as the sum of consecutive integers where $m$ is the largest odd divisor on $n$. I have absolutely no idea ...
3
votes
5answers
262 views

Solve $12x^2 – 25x \equiv -2 \pmod{11}$

Solve $12x^2 – 25x \equiv -2 \pmod{11}$ I have no idea what to do.
1
vote
0answers
38 views

How to find Triangular Numbers

I read that Gauss's Eureka Theorem says that any positive integer can be represented by at most 3 triangular numbers. So say I have some positive integer X, how do I find which 3 triangular numbers ...
1
vote
1answer
29 views

Circular list from the 2nd element of the result of repeatedly perfect shuffling a magnitude ordered list of natural numbers less than an even number.

Start with a magnitude ordered list of the natural numbers that are less than a chosen even number greater than 0. {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11} Repeatedly 'Perfect Shuffle' this list, ...
1
vote
5answers
66 views

No natural numbers satisfy $n\equiv n^2-4\pmod9$

Prove that for all natural numbers, $n$ is not congruent to $n^2-4\pmod9$. I'm trying to prove this by contradiction and say that if they were congruent $\pmod 9$ it could be expressed as $9\mid ...
2
votes
2answers
52 views

Number theory research topics

I have to do a project for my number theory class (Undergraduate). The professor asked us to explore a topic from number theory and write about 5 to 10 pages on it. I am a computer science major, so ...
11
votes
0answers
121 views

Number theory: $a\in A\iff \frac{1}{2}-a\in A$.

Let $A$ be the set of all $a\in \mathbb{Q}$ for which there exist $x,y,z\in \mathbb{Z}$ not all $=0$ such that $$a=\frac{xy+yz+zx}{x^2+y^2+z^2}.$$ Prove that $$a\in A\iff \frac{1}{2}-a\in A.$$ Note: ...
1
vote
3answers
50 views

Modular Arithmetic with large exponents!

Decide whether each of the following is true or false without using a calculator: The problem is: $$11^{99}\equiv 1\pmod{5}$$ Now I know I can break the $11$ into $(10+1)^{99}$ and maybe rewrite it ...
1
vote
1answer
14 views

Examples of commutative rings where the prime subring is not direct summand?

My question consists almost in the title. My motivation is the study of some tensor products $A\otimes_\mathbb{Z} B$. For a (commutative) ring, let us call prime subring the subring generated by $1$ ...
0
votes
0answers
30 views

How to check if a number is in $\mathbb{Z}_{p}^{\star}$, where $p$ is the product of two primes?

Like the question says, how can I check if a given number $e$ is in the group $\mathbb{Z}_{p}^{\star}$, where $p$ is the product of two primes? It is enough to verify if $\gcd(e, p)=1$? What's the ...
0
votes
1answer
18 views

Find all positive integer $n$ such that there exists $m$ with $2^n-1|m^2+17^2$.

Find all positive integer $n$ such that there exists $m$ with $2^n-1|m^2+17^2$. I have tried to mod $2^n-1$ and use the fact that $2^n \equiv 1 \pmod{2^n-1}$. I have also tried to factorize ...
1
vote
0answers
34 views

On Descartes numbers

This question is an offshoot of this earlier MSE post. Citing Banks, et. al.: "Let us call an integer $n$ a Descartes number if $n$ is odd, and if $n = km$ for two integers $k, m > 1$ such that ...
2
votes
3answers
57 views

Prove that $1+20^1+20^2+\cdots+20^{21}\equiv 0\pmod{23}$

How can I prove that $1+20^1+20^2+\cdots+20^{21}\equiv 0\pmod{23}$?
0
votes
0answers
21 views

Checking a Proof of Apostol's Analysis Exercise 2.20

Let $f: [0, 1] \to \mathbb{R}$ and let there be an $M > 0$ such that $$|f(x_{1}) + \cdots + f(x_{n})| \leq M$$ for $n \geq 1$ and for $x_{1}, \cdots, x_{n} \in [0, 1].$ We are to prove that, if $$S ...
1
vote
1answer
23 views

For what positive integers is this number-theoretic equation true?

For what odd (positive) integers $x$ is this number-theoretic equation true? $$\gcd(x^2, \sigma(x^2)) = 2x^2 - \sigma(x^2)$$ Here, $\gcd(a, b)$ is the greatest common divisor of $a$ and $b$, and ...
0
votes
1answer
29 views

How would I go about calculating Zolotarev symbol for large primes?

How would I go about calculating Zolotarev symbol for large primes? For example: $$\left(487 \over 1009 \right)$$
0
votes
0answers
28 views

Congruence-related primes: $(p,q)$,$\quad q=(n \quad mod \quad p)$ and $2p+q=n (odd)$. Is there any information about them?

I am studying congruences and I have observed this kind of prime pairs $(p,q)$ related to odd numbers. Do this kind of prime pairs have a name or have been studied before? Here is the definition: ...
1
vote
2answers
38 views

Number of solution of Frobenius equation

Oke I am trying to find all presentable of a number $n$ as sum $ax+(a+1)y$ where $a=0,1,\ldots$ and $x,y\geq0$ are integers. I find that $5=1+1+1+1+1=1+1+1+2=1+2+2=2+3=5$ so we have $5$ ways. ...
0
votes
0answers
23 views

Use the euclidean algorithm to express the gcd as a linear combination

Express the GCD(2546,122) as a linear combination of 2546 and 122 I found the gcd to be 8 and I went about writing it as a linear combination but somewhere I went wrong.. can someone find my ...
-2
votes
0answers
132 views

series of numbers

I asked this question some time ago but was closed, but, I think it is interesting and I will ask again. So, if we have the formula $$ \frac{(n+1)n}{2}=1+2+\dotsb+n $$ now, if the difference ...
0
votes
1answer
29 views

Performing one digit operation to compute the result.

Suppose we have $a_i, b_i, c_i \in \{0, 1, \dots , 9\}$ and $A=a_2a_1a_0, B=b_2b_1b_0, C=c_1c_0$. We want to perform the following operations with the restriction that only one digit operation is ...
2
votes
2answers
67 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$, ...
1
vote
2answers
35 views

Show that if $\gcd(r,s_1) =\gcd(r,s_2) = 1$, then $\gcd(r,s_1s_2) = 1$

Never mind the question. I want to try to solve that on my own. What I want to understand is how this: "Hint. $1 = ar + bs_1,\ 1 = ar + bs_2$" relates to solving it. I'm a little confused by this ...
2
votes
3answers
82 views

A problem I didn't know since high school algebra

Determine all positive integers which can be written as a sum of two squares of integers. This is a problem I saw when I was in high school... sum of two squares of integers can be (4k, 4k+1, ...
1
vote
2answers
28 views

Sum $\pmod{1000}$

Let $$N= \sum_{k=1}^{1000}k(\lceil \log_{\sqrt{2}}k\rceil-\lfloor \log_{\sqrt{2}}k \rfloor).$$ Find $N \pmod{1000}$. Let $\lceil x \rceil$ be represented by $(x)$ and $\lfloor x \rfloor$ be ...
1
vote
2answers
22 views

An element a of Zn is only invertible if gcd (a,n) =1

I need help with this: If a is an element of Zn and gcd(a,n) > 1 , then a is not invertible. First you show that if a is an element of Zn and gcd(a,n)>1, then there is an element b of Zn and (b is ...
7
votes
3answers
1k views

How do I find the value of this weird expression?

How can I find the value of the expression $\sqrt{2}^{\sqrt{2}^{\sqrt{2}^...}} $? I wrote a computer program to calculate the value, and the result comes out to be 2 (more precisely 1.999997). Can ...
0
votes
1answer
31 views

How many perfect squares exist (multiples of $24$)

How many positive perfect squares less than $10^6$ are multiples of 24? I quickly realized: $$24 = 2^{3}*3*5^0$$ $$10^6 = 2^6 * 5^6*3^0$$ We are finding numbers in the form $24(k^2)$. But I ...
0
votes
1answer
30 views

Recursive Relations

I've been doing recursive relations and found a question I wasn't able to solve. I'm given a recursive algorithm that finds the $\gcd$ of two numbers $p$ and $q$. Algorithm: ...
0
votes
2answers
69 views

Can a simple plot be used as a proof-without-words?

Can this simple plot be used as a proof-without-words? Edit "No, it suggests but does not prove." Plot of $2^{1 + n} = 1 + 3^n:$ Motivated by this question, I reworked the non-loopback ...
2
votes
1answer
46 views

Help me finding $a+b+c$ in the given question

If $a,b,c$ are three positive integers such that $$abc+ab+bc+ca+a+b+c=1000$$ then what is the value of $a+b+c$?
2
votes
1answer
41 views

A problem with prime powers

I have this problem: if $q$ is a prime and $r$ is a positive integer, I need to understand under which conditions $$\frac{q^r-1}{q-1}$$ is an integer. Thanks in advance
0
votes
1answer
20 views

Decimal expansion of real numbers and countability

Let S be the set of all real numbers in the interval (0,1) whose decimal expansions involve only 0 and 1. Prove that S is uncountable. assume that S is countable. then elements a1, a2, a3, a4 belong ...
2
votes
4answers
30 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 ...
0
votes
0answers
21 views

Comparing a primorial $p\#$ to Dusart's upper bound for the $n$th prime

The number of elements of a reduced residue system modulo a primorial $p$ is $\varphi(p\#)$ I thought that it would be interesting to compare each primorial $p_i\#$ to the Dusart's estimate for the ...