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

learn more… | top users | synonyms (1)

4
votes
6answers
419 views

Elementary number theory - prerequisites

Since summer comes with a lot of spare time, I've decided to select a mathematical subject I want to learn as much as possible about over the next three months. That being said, number theory really ...
0
votes
0answers
40 views

Nice statements about the “opposite properties” of $0$ and $1$.

Some of $0$ and $1$'s properties as natural numbers are pleasingly opposite of one another, such as: 1a.) $0$ has infinitely many divisors, but no (non-zero) multiples. 1b.) $1$ has infinitely many ...
0
votes
1answer
72 views

Can this expression be made true ? 2 _ _ _ _ = 2015

Make this expression true: 2 _ _ _ _= 2015 The underscores must be replaced by any 2 of of the operational symbols +, - , x, / (divide). And any 2 of the digits 0,1,2..9. So, you basically need 2 ...
0
votes
1answer
57 views

About the vertices of a regular polygon in the plane having rational coordinates [closed]

I have to prove that, except in the case $n=4$, the vertices of a regular $n$-agon in the Euclidean plane cannot have all rational coordinates $(x,y)$. Some idea?
1
vote
3answers
61 views

Determining the relative size of $a^n$ and $b^m$ without using logarithms

Example, which is larger $ 17^{105} $ vs $ 31^{84} $? Make the deternimination without resorting to logs, or Excel either.
1
vote
1answer
23 views

$p$ and $r$ are primes greater than $2$. $p+r$ vs $p+2r$, which could be a prime number?

For $p+2r$, a example would be $3$ and $5$. Since $6+5 = 11$, I am led to believe $p+2r$ to be the right answer. But I don't know how it works?
1
vote
1answer
51 views

Addition of points on elliptic curves over a finite field

I have found the following formulas for the coordinates of $P+Q$ given that $P = (x_{1}, y_{1})$ and $Q = (x_{2}, y_{2})$ are points on a general curve $y^2 = x^3 + ax + b$ over $\mathbb{R}$: $$P + Q ...
0
votes
1answer
26 views

Factor RSA number $n$.

An RSA number $n=p\cdot q$, where $q=2\cdot d +1$, $d$ an odd integer, is given. Assuming $a \in \mathbb{Z}_n$ with $a^4=1$ and $a^2 \neq 1$. How can this information lead to finding $p$ and $q$? I ...
4
votes
2answers
54 views

Irrational numbers, induction

I have $\sqrt[3]{2}^{2^n}$. Can I prove that this number is irrational by showing that $3$ does not divide $2^n$?
4
votes
5answers
96 views

Prove every integer is of the form $5k+r$ with $0\le r<5$

I have came across this question from my text book: Prove or disprove: any integer $n$ is of the form: $5k$, $5k + 1$, $5k + 2$, $5k + 3$ or $5k + 4$ for some integer $k$. I'm not sure what would be ...
1
vote
1answer
35 views

$r! \equiv (−1)^k \pmod p$

Suppose that p ≡ 3 (mod 4) and $r = \frac {p-1}2$ Show that $r! \equiv (−1)^k \pmod p$ where k is the number of non-quadratic residues modulo p which are smaller than $\frac p2$ I know from ...
0
votes
1answer
30 views

Show that $(r!)^2 ≡ (−1)^{r−1} \pmod p$ [duplicate]

I need to prove that if p is an odd prime and $r = (p-1)/2$ then $(r!)^2 ≡ (−1)^{r−1} \pmod p$ I think it has something to do with gauss's lemma ...
1
vote
1answer
62 views

Prove that $\sin{\frac{2\pi x}{x^2+x+1}}=\frac{1}{2}$ has no rational roots.

Show that the following equation has no rational roots. $$\sin{\frac{2\pi x}{x^2+x+1}}=\frac{1}{2}$$ This is what I've tried: $$\left ( \frac{2\pi x}{x^2+x+1}=\frac{\pi}{6}+2k\pi ...
1
vote
1answer
31 views

Prove/disprove the following asymptotic bound

Indicating with $p$ and $q$ prime numbers, is it true that for $x\rightarrow\infty$ $$ \sum_{\substack{p\leq x \\ p\equiv 1 ...
3
votes
3answers
49 views

Finding the last digit of $7^n$, $n\ge 1$.

I have noticed a cycle of 7,9,3,1. Meaning: $7^1\equiv 7\pmod {10}, 7^2\equiv 9\pmod {10}, 7^3\equiv 3\pmod {10},7^4\equiv 1\pmod {10}, 7^5\equiv 7\pmod {10}$ and so on. Therefore, if $n=4k+1$ the ...
2
votes
3answers
50 views

Proof for $\left\lfloor\frac 1j\left\lfloor\frac nk\right\rfloor\right\rfloor=\left\lfloor\frac n{jk}\right\rfloor$

Problem: For positive integers $n,j,k$, prove that the following holds: $$\left\lfloor\frac 1j\left\lfloor\frac nk\right\rfloor\right\rfloor=\left\lfloor\frac n{jk}\right\rfloor$$ I simply ...
4
votes
2answers
383 views

Is there any simple trick to solve the congruence $a^{24}\equiv6a+2\pmod{13}$?

Which of the following primes satisfy the congruence $$a^{24}\equiv6a+2\pmod{13}$$ 1) 41 2) 47 3) 67 4) 83 I am interested in Theorem statement, corollary, or Trick or Logic which solves this ...
2
votes
4answers
54 views

Question on Math.floor on negative number [closed]

why do these return different results? Math.floor(-1735)=-1735 Math.floor(-17.35*100)=-1736
1
vote
2answers
59 views

solve $x^2 \equiv 24 \pmod {60}$

I need to solve $x^2 \equiv 24 \pmod {60}$ My first question which confuses me a lot - isn't a (24 here) has to be coprime to n (60)??? most of the theorems requests that. what i tried - $ 60 ...
1
vote
2answers
26 views

How to find the indexes given the element index in a vector?

I have a vector $\mathbf{x} = [x_{11}, x_{12}, \ldots, x_{1n}, x_{21}, x_{22}, \ldots, x_{2n}, \cdots, x_{m1}, x_{m2}, \ldots, x_{mn}]^T$ of size $m\cdot n$. My problem is this: Given an index ...
0
votes
3answers
41 views

Is it true that $x \nmid (q-1) \implies 2^x \not \equiv 1 \mod q$

If $q$ is a prime number, then from little fermat theorem it is known that $$2^{q-1} \equiv 1 \mod q$$ My doubt is that If $x \nmid (q-1)$ then $2^x \not \equiv 1 \mod q$ is true statement or not? ...
0
votes
0answers
20 views

Function for the number of divisor of a number [duplicate]

Is there a formula/function that given any $n$ produces the number of divisors of $n$ ? And has that something to do with Euler function?
0
votes
3answers
27 views

binary representation of integers congruent 1 and 3 modulo 4

Let $k=b_nb_{n-1}\ldots b_3b_2b_1b_0$ be the binary representation of an odd positive integer. Prove: If $k\equiv 1 \mod 4$ then $b_1=0$. If $k\equiv 3 \mod 4$ then $b_1=1$. I think that to prove ...
0
votes
1answer
52 views

When does Fermat's little theorem not hold for coprimes $a$ and $p$ , but $p$ being non-prime and why?

When does Fermat's little theorem not hold for coprimes $a$ and $p$, but $p$ being non-prime and why? I tested some non-prime values of $p$ and it seems to still hold.
-3
votes
2answers
51 views

Why is $a^{-1}$ mod $p$ equal to $a^{p-2}$ mod $p$? [closed]

Why is $a^{-1}$ mod $p$ equal to $a^{p-2}$ mod $p$ in modular arithmetic?
0
votes
1answer
20 views

Show how one can decrypt RSA message with e = 3 and $m<N^{1/3}$ without knowing the private key

Show how one can decrypt RSA message with e = 3 and $m<N^{1/3}$ without knowing the private key. I really don't know how to solve this one. we just learned about quadratic residues so i guess it ...
0
votes
0answers
38 views

The amount of the third degree.

Often have to deal with such a cubic Diophantine equation. $$q(a^3+b^3)=t(x^3+y^3)$$ $q,t - $ are specified for the problem. Interesting - in all the values of the coefficient of solutions are ...
-4
votes
2answers
60 views

Find all $n$ such that $n^2+3^n$ is a square number [closed]

Find all $n$ such that $n^2+3^n$ is a square number .
6
votes
6answers
117 views

What are the last two digits of $77^{17}$?

I'm trying to solve current task referenced the following but I stuck at $\displaystyle77^{17}\equiv x\pmod{100}$. As it is described on above link it uses Binomial Theorem. But I read a lot about the ...
4
votes
1answer
36 views

Divide a square into different parts

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 geometry, which perhaps yields the shortest, simplest proofs, but other ...
2
votes
2answers
42 views

Show that $b \equiv a^k \pmod p$ for some integer $k$ such that $(k, d) = 1$.

Let $p$ be a prime number and let $d \mid (p − 1)$. Let $a$ be an integer such that $p \not\mid a$ and $\text{ord}_p (a) = d$. Show that if $b$ is any integer such that $p \not\mid b$ and ...
4
votes
3answers
129 views

Solve in positive integers: $5^x 7^y +4=3^z$

Solve in positive integers: $5^x 7^y +4=3^z$. I tried to solve it with log but I couldn't complete.
3
votes
2answers
55 views

$x^2 + 3x + 7 \equiv 0 \pmod {37}$

I'm trying to solve the following $x^2 + 3x + 7 \equiv 0 \pmod {37}$ What I've tried - I've tried making the left side as a square and then I know how to solve but couldn't make it as a square ...
2
votes
2answers
20 views

Does every $\mod p$ have at least one element with a non-identical inverse?

Does every mod p have at least one element with a non-identical inverse? I very much suspect this is true, but how can I prove it? For example, in mod 5, some elements have inverses that are not ...
2
votes
2answers
39 views

Reference for the p-adic numbers

Can anyone give me a reference (book or a paper) that introduces the p-adic numbers and their important properties? Also, I would love if that reference contained some not to advanced applications ...
5
votes
2answers
71 views

LCM of irrationals

So, I was recently asked by a friend about the lcm of two irrational numbers. As far as I know, mathematically speaking, lcm is generally defined only for positive integers (and sometimes extended to ...
3
votes
3answers
51 views

Monic polynomial $= 0 \mod p$ for all $x$

For a monic polynomial with integer coefficients (leading coefficient of $1$) $f(x)$ where $f(x) \equiv 0$ mod $p$ for all $x$, where $p$ is a prime number how do I show that the degree of the ...
0
votes
2answers
50 views

solve $3x^2 + 6x +1 \equiv 0 \pmod {19}$

I need to solve $3x^2 + 6x +1 \equiv 0 \pmod {19}$ I saw the same problem here - Solving the congruence $3x^2 + 6x + 1 \equiv 0 \pmod {19}$ but didn't understand how he got to the conclusion ...
5
votes
3answers
101 views

If $a^b=c^d$, then $c$ and $a$ are powers of the same number?

I want to know in which situations two numbers that can be expressed as powers can be equal. I think it's intuitive that if two powers (say $a^b$ and $c^d$) are equal, then the bases must be ...
-3
votes
2answers
85 views

Remainder of $2^{2014^{2013}}$ when divided by $41$ [duplicate]

What is the remainder of $2^{2014^{2013}}$ when divided by $41$? The hint I have to use is that $2^{10}\equiv -1\mod 41$. Can I use the Chinese remainder theorem here? And if so, how?
2
votes
1answer
23 views

Are there variants (described below) of $3n + 1$ conjecture where the answer is known?

The $3n + 1$ conjecture states that if you take any natural number $n_j$, and if it is even then set $n_{j+1} = n_j/2$, otherwise set $n_{j+1} = 3n_j + 1$, then no matter what natural number $n_0$ you ...
2
votes
0answers
63 views

Ulam spiral and triangular numbers

Is there any explanation for the twister-like pattern build by triangular numbers $$\Delta_n = \frac{n\cdot(n+1)}{2}$$ in the Ulam Spiral? Here for $1,\ldots,100$: Here's a picture with many more ...
1
vote
4answers
121 views

Final numbers of $2003^{2003}$ and $2003^{2003^{2003}}$

What are the three final numbers of $2003^{2003}$ and $2003^{2003^{2003}}$? Do I use the Chinese Remainder Theorem here, and if so, how?
-4
votes
1answer
54 views

Is $2^{p-1}\,\%\, p=1$ for all p such that p is a prime? [closed]

Is $2^{p-1}\,\%\, p=1$ for all $p$ such that $p$ is a prime and $\%$ represents modulo operation ? Please explain in detail if possible.
1
vote
5answers
147 views

Finding integers of the form $m+n$ that satisfies $m+n+mn=118$

Let $m$ and $n$ be two positive integers such that $m+n+mn=118.$ My question is: Can the value of $(m+n)$ be uniquely determined? I find by inspection that the pair $(m,n)=(16,6)$ (or the ...
11
votes
1answer
72 views

How many unique numbers can be obtained from multiplying two natural numbers less than $N$?

The question seems simple, but I cannot wrap my head around how to properly count it, or even give a good estimate. I can't find the answer either. We have two integer numbers $1 < a,b < N$, ...
-1
votes
2answers
53 views

Difference of two digit square numbers

So I've just bought a math notebook for the summer and I've encountered a problem that seems very simple but I can't find its solution. It says as following: Prove the fact that there is not a ...
2
votes
4answers
124 views

A man died. Let's divide the estate!!! How?

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 plain old algebra, which yields the shortest, simplest answers, but other ...
6
votes
1answer
43 views

Are Pythagorean triples $(a,b=\frac{a^2-1}{2},c=\frac{a^2-1}{2}+1)$ able to generate always primes through this property?

I was testing the properties of the Pythagorean triples of the form $(a,b=\frac{a^2-1}{2},c=\frac{a^2-1}{2}+1)$ and by chance I found that the following expression seems to be true for all the pairs ...
1
vote
1answer
25 views

Do we need to apply the Euclidean Algorithm before applying the Extended Euclidean Algorithm?

As the title says, do we need to apply the Euclidean Algorithm before applying the Extended Euclidean Algorithm? For example, we have $\gcd(24,17)$, so we can find $x,y$ such that $24x+17y=1$. ...