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

learn more… | top users | synonyms (1)

0
votes
0answers
36 views

Is this curve an elliptic curve

I want to know whether curve $$x^3+21x^2+35x+7=4xy+4y^3$$ is an elliptic curve or not. If that is an EC so what is its Weierstrass form?
3
votes
1answer
44 views

Given $11$ positive integers, we can always make a cube.

I have got the following task: Let us have $11$ positive integers, none of them with a prime divisor greater than $29$. Prove that we can always choose $a_1,\ldots,a_k$ and $b_1,\ldots,b_k$, where ...
6
votes
3answers
125 views

Finding integer solutions of $m^2-n^5 = m - n$

How to list all integer solutions of $m^2-n^5 = m - n$ Here $m$ and $n$ are some positive integers. Also, I want to know the name of this type equations (if name exist). Regards Rosy
1
vote
2answers
37 views

The order of an element [duplicate]

The order of a unit $a \pmod m $ is the least $n \geq 1$ such that $a^n \equiv 1 \pmod m$. my question is : Is true that number and its inverse have the same order?
18
votes
3answers
4k views

Why does (1/3) mod 3016 = 2011?

So I am taking a class where we are working on a cryptography section. Basically, the course says that: $$\frac 1 3 \mod(3016) = 2011$$ or when run through Python - modified with SciPi: $$\frac 1 3 ...
1
vote
2answers
39 views

Proof verification: if $p$ is an odd prime, then any divisor of a Mersenne number is of the form $2kp+1$.

I've proved that if $p$ is an odd prime, then any divisor of a Mersenne number is of the form $2kp + 1$. Proof: If $q$ is a prime divisor of $M_p$, then $qk = 2^p - 1 \rightarrow 2^p \equiv 1 ...
8
votes
1answer
165 views
+100

Equality by iteratively applying $(a,b)\rightarrow [(a+1,2b)\text{ or }(2a,b+1)]$?

I play a game starting with $2$ positive integers $a$ and $b$. At each step of the game I can double one of the integers and add $1$ to the other integer. Is there always a procedure for any ...
2
votes
1answer
40 views

Find all the primes that satisfy $p \mid 2^p - 1$

I just want somebody to verify that my work is correct. Find all prime numbers $p$ such that $p \mid 2^p - 1$. My claim is that there no such prime that satisfies this. If $pk = 2^p - 1$, we ...
1
vote
0answers
31 views

Finding the factors of integer x and its square

What is the the theorem or property that says that $\forall{}x\in{}Z$, the set of all integers, $x^2$ has the same factors as $x$, twice?
0
votes
1answer
25 views

Computing Large Number Modulo and Multiplicative Inverse

Prove that $3^{28}$ is a multiplicative inverse of $9^{34}$ modulo $17$, i.e. show that $3^{28}9^{34}\equiv 1\pmod {17}$. I really have no idea how to approach this example other than applying ...
1
vote
1answer
18 views

Maya Lists the Positive Divisors

Maya lists all the positive divisors of $2010^2$. She then randomly selects two distinct divisors from this list. Let $p$ be the probability that exactly one of the selected divisors is a perfect ...
1
vote
2answers
40 views

$\gcd(1000, 1000 - x)$ if $0 < x < 1000$, $x \in \mathbb{N}$.

Find $\gcd(1000, 1000 - x)$ if $0 < x < 1000$, $x \in \mathbb{N}$ and $x$ is coprime to $1000$. Since $1000 > 1000 -x$, it follows from Euclidean Algorithm, $$1000 = 1(1000 - x) + x$$ ...
0
votes
0answers
31 views

Determining if a rational number has a terminating decimal expansion (proof)

Theorem: $x=\frac pq$ is any given rational number, $n$ and $m$ are any whole numbers (including zero) which you can choose. a) If $q=2^n5^m$ is possible, $x$ has a terminating decimal expansion. ...
1
vote
3answers
32 views

How to prove that $n$ is a prime number iff for every integer $a$: $(a,n)=1$ or $n\mid a$

It seems like it's obvious because if $n$ is prime then its gcd with every number is $1$... But I understand that by intuition and don't know how to formally prove it... I'm confused.
1
vote
2answers
41 views

Euler Phi of a number

I saw an AIME problem where you took $\phi(1000)$ and then divided by $2$. The problem is here: http://www.artofproblemsolving.com/community/u244443h580665p4722095 $\phi(1000)$ gives you how many ...
6
votes
1answer
54 views

Pairs of integers $(a,b)$ such that $\frac{1}{6} =\frac{1}{a} + \frac{1}{b}$

How many pairs of integers are there $(a,b)$ with $a \leq b$ such that $$\frac{1}{6} =\frac{1}{a} + \frac{1}{b}$$ My attempt: Clearing fractions we get $$ab = 6(a+b)$$ $$ \Longrightarrow ...
1
vote
0answers
56 views

Blocks of consecutive natural numbers

Let a < b be natural numbers. Prove that every block of b consecutive natural numbers contains two distinct elements whose product is divisible by ab. Suppose now a < b < c are natural ...
0
votes
1answer
36 views

Prove $a^2+6a+1\perp 375$ for all $a\in \mathbb{Z}$.

Prove $A=a^2+6a+1\perp 375$ for all $a\in \mathbb{Z}$ I thought to write $375=3\cdot5^2$. So if $A$ is coprime with $3\cdot5^2$ they must share no prime factors. Then I test if $3$ or $5$ divide $A$ ...
2
votes
2answers
63 views

Prime $4n+3$ simple proof?

Let $p=4n+3$ be a prime. Prove that $\prod_{k=1}^{p-1}(x+k^2)\equiv (x^{\frac{p-1}{2}}+1)^2\pmod p$. Is there a simple proof that doesn't use say arithmetic in $\mathbb{Z}[i]$? My approach was to ...
0
votes
3answers
36 views

Postage stamp with $6$ and $7$ cents question

What is the largest postage in cents that cannot be paid exactly with an unlimited supply of $6$-cent and $7$-cent stamps? Any hint so that I can proceed?
0
votes
2answers
32 views

The Density Of The Real And Rationals

I am trying to get better understanding of the density property of the real numbers and the rational. As for the rational if we take for example $\frac{1}{100} $ and $\frac{1}{101}$ which number can ...
4
votes
1answer
48 views

Why is there only one group of order $n$ for some non-primes?

I would like to understand for which integers $n$ is there only one group of order $n$. (up to isomorphism). I understand that if $n$ is prime there is only one group of order $n$. In Sloane's OEIS ...
0
votes
1answer
24 views

Contraharmonic mean given harmonic mean

Given that two positive integers, $X$ and $Y$, have a harmonic mean of $6.875$, what is their contraharmonic mean. Harmonic mean is $(2XY)/(X+Y)$ and contraharmonic mean is $(X^2 +Y^2)/(X+Y)$. I began ...
3
votes
3answers
99 views

Prove there exists $m > 2010$ such that $f(m)$ is not prime

Let $$f(x) = \sum_{i = 0}^n a_ix^i$$ be a polynomial with $a_i \in \mathbb Z, n > 0, a_n \neq 0$. Prove that there exists some natural number $m>2010$ such that $|f(m)|$ is not a prime number. ...
3
votes
2answers
71 views

“$111 \dots$ upto $3^n$ digits” is divisible by $3^n$

Prove that an integer of the form "$111 \dots$ upto $3^n$ digits" is divisible by $3^n$ My attempt For $n=1,$ $111$ is divisible by 3. Let $T_n=111...$ upto $3^n$ digits is divisible by $3^n$. ...
1
vote
3answers
74 views

Solve in non-negative integers: $m^2+n^2=1997 (m-n)$

Solve in $\mathbb{N}$:$$m^2+n^2=1997(m-n)$$ I try with quadratic equation or with factorising, but I have no idea what to do after that.
0
votes
1answer
26 views

A question in Number Theory - prove there exist m>2010 s.t f(m) is not prime [duplicate]

Let $$f(x)=\sum_{i=0}^n a_nx^n$$ be a polynomial with $$a_n \in Z,n>0,a_n\neq0$$ Prove that there exists some natural number $$m>2010$$ such that $$|f(m)|$$ is not a prime number. I tried to ...
0
votes
1answer
38 views

A question about primes, number theory [duplicate]

I tried to solve this question but without a success: Let $p$ be a prime number,and $p^2+2$ is also prime, prove that $p=3$. I tried to show $p^2+2$ as a product of numbers and then to show that ...
0
votes
2answers
30 views

Number Theory - Multiple of $36$ problem

Let $N$ be the greatest integer multiple of $36$ all of whose digits are even and no two of whose digits are the same. Find the remainder when $N$ is divided by $1000$. $$N = \overline{abcd....} ...
1
vote
1answer
66 views

Rational points on circle

I need help for the following questions. Give the necessary and sufficient condition for $r$ such that the circle $x^{2}+y^{2}=r^{2}$ passes the rational points. I know the obvious sufficient ...
0
votes
0answers
53 views

Is 1 the geometric mean of a positive number and its inverse? (same for -1 and neg numbers) [closed]

Recently, I realized that all of multiplication in the interval [1, infinity) is contained as division in (0, 1} (same the other way around with neg numbers). It also seems to me that 1 is the ...
9
votes
4answers
19 views

A 10-digit number whose $n$th digit gives the number of $(n-1)$s in it

There is a ten-digit number $X$ such that its first (left-most) digit is equal to the number of $0$s in $X$, the second digit gives the number of $1$s in $X$, and so on. The last (right-most) digit ...
0
votes
1answer
30 views

if $a = 0 \mod p $ and $a \not = 0 \mod p ^2$

let $a = bc$ if $a = 0 \mod p $ and $a \not = 0 \mod p ^2$ with $p$ prime. what can we deduce? ($a,b,c \in \mathbb{Z}$) I have that if $a = 0 \mod p$ then either $b = 0 \mod p$ or $c = 0 \mod p$ (can ...
0
votes
5answers
73 views

Mathematical induction [duplicate]

Prove that $9$ divides $n^3 + (n+1)^3 + (n+2)^3$ where $n$ is a nonnegative integer. I have seen many questions on this site that contain the answer to this problem and I already know the solution, ...
3
votes
1answer
51 views

Negative Pell's Equation: Prove that $k=3$.

I made this problem (while solving another problem) but I haven't been able to prove it. Let $x,y,k\in \mathbb{Z}^+$. Prove that if $x^2-(k^2-4)y^2=-1$ then $k=3$. Any pointers are appreciated, but ...
2
votes
1answer
57 views

Why does the graph of $y=\gcd \left(\frac{x}{y},xy\right)$ seem to have 4 “straight” lines?

Why does the graph of $y=\gcd \left(\frac{x}{y},xy\right)$ seem to have 4 "straight" lines? Using https://www.desmos.com/calculator for plotting.
-1
votes
1answer
25 views

Show all final 2-digit numbers of the decimal expansions of squares are to be found among those of $0^2, 1^2,…25^2$ [duplicate]

I'm not really sure where to begin. The first part of the question states that "every positive integer has a unique representation in the form $50k+l$, with $-24\lt l \le 25$," which isn't even true, ...
0
votes
2answers
38 views

Show that every positive integer has a unique representation in the form $50k+l$…?

with -24 $\lt l \le$ 25. Then I need to conclude that all final 2-digit numbers of the decimal expansion of squares are to be found among those of $0^2, 1^2, 2^2,...., 25^2$. I'm thinking that I ...
0
votes
1answer
35 views

Find two numbers, given their greatest common divisor and least common multiple [closed]

Highest common factor (HCF) of two numbers is $20$. Least common multiple (LCM) of the same two numbers is $420$. Both numbers are higher than $50$. Find the $2$ numbers. I used factorising trees ...
0
votes
0answers
32 views

quick question about prime numbers and division

suppose that $a,b \in \mathbb{Z}$ and that $ab = kn$ where $k \in \mathbb{Z}$ and $n$ is prime. My book says that since $n$ is prime, then $ n $ divides $a$ or $n$ divides $b$. Could someone explain ...
1
vote
2answers
39 views

n is either a prime or has at least three prime factors

if $\phi(n) |n-1$ then n is square-free. Show also that n is either a prime or has at least three prime factors. n prime if is obvious. $\phi(p)|p-1$ since $\phi(p)=p-1$.
10
votes
1answer
100 views

Last nonzero digit of $2010!$ [closed]

I have to calculate the last nonzero digit of $2010!$ Till now I couldn't find any pattern.
4
votes
5answers
109 views

Proving $6^n - 1$ is always divisible by $5$ by induction

I'm trying to prove the following, but can't seem to understand it. Can somebody help? Prove $6^n - 1$ is always divisible by $5$ for $n \geq 1$. What I've done: Base Case: $n = 1$: $6^1 - 1 = ...
-1
votes
0answers
24 views

Prove or disprove : if $a\mid bc$ and $\gcd (a,b) = 1$, then $a\mid c$ [duplicate]

If $a\mid bc$ and $\gcd (a,b) = 1$, then $a\mid c$. How do I prove this?
0
votes
3answers
18 views

system of conguences

I am trying to figure out how to solve: Find $x, y \in \mathbb{Z}$ such that $$2x+y\equiv 4\pmod{17}$$ and $$5x-5y\equiv 9\pmod{17}.$$ I know this means $2x+y-4$ and $5x-5y-9$ are multiples of $17$, ...
0
votes
1answer
27 views

Prove that in $\Bbb{Z}$, $\forall a,b\in\Bbb{Z}$ such that $a = bq +r$, we can find $r$ such that $-\frac{1}{2}b \leq r \leq \frac{1}{2}b$

In $\Bbb{Z}$, we know that for all $a, b \in \Bbb{Z}$, we can express $a = bq + r$ such that $|r| < |b|$. However, I read from this post Prove that the Gaussian Integer's ring is a Euclidean ...
5
votes
1answer
41 views

Find all the primes $p,q$ such that $2^{p-q}+1\equiv0\pmod{pq}$

Find all the primes $p,q$ such that $2^{p-q}+1\equiv0\pmod{pq}$ I'm not sure how to start this. I am guessing Fermat's little theorem has something to do with this as $2^p\equiv 2\pmod{p}$ and ...
5
votes
1answer
68 views

An Impossible Sequence of Prime Powers

Let $x_1,x_2,\ldots$ be a sequence of positive integers that satisfies the recurrence relation $$x_{n+1}=2x_n(x_n-1)+1$$ for all positive integers $n$. It seems impossible that every term in this ...
2
votes
1answer
37 views

Proving $k$ is divisible by $3$ iff the sum of the digits of $k$ is divisible by 3 [duplicate]

I am trying to prove that $k$ is divisible by $3$ iff the sum of the digits of $k$ is divisible by 3 for all $k \in Z$. I am not even sure what tags to use because I am not sure of right methods to ...
1
vote
1answer
41 views

If $r$ is a primitive root of an odd prime $p$, then $s$ is a residue of $p$ iff $s \equiv r^{2n} \pmod{p}$.

If $r$ is a primitive root of an odd prime $p$, then prove that $s$ is a residue of $p$ iff $s \equiv r^{2n} \pmod{p}$. The above was the original statement of an elementary number theory ...