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

learn more… | top users | synonyms (1)

45
votes
13answers
5k views

How can I write the numbers 5 and 7 as some sequence of operations on three 9s?

I want to make the numbers $1, 2, ..., 9$ using exactly three copies of the number $9$ and the following actions: addition, subtraction, multiplication, division, squaring, taking square roots, and ...
3
votes
2answers
34 views

Finding an integer c for which a+c^2 = 0 (mod 2*b-2*c), a & b constant

Looking for a solution for such a challenge, I have a decision problem that is solved if there is a positive integer $c$, which for given integer constants $a, b$ satisfies the equation $a+c^2 \equiv ...
0
votes
1answer
28 views

Legendre symbols with huge “p”s [duplicate]

I am in doubt with an exercise - I need to calculate $$\left(205\mid853\right)$$ I would use the fact Legendre's symbols are multiplicative, but then I would have something like ...
3
votes
2answers
107 views

Positive integers x,y,z such that $x!+y!=z!$ [duplicate]

Find all positive integers $x,y,z$ such that $$x!+y!=z!$$ My Progress: let $x=y=1$ so that you get $2!$ Which is true. How do I compute this algebraically instead of substituting random values?
3
votes
3answers
95 views

Divisor of $3^{2n+1}+61$

I have difficulty to show the following: If $p$ is a prime and $p^2$ divides $3^{2n+1}+61$, then $p$ must be $2$. I appreciate any help.
0
votes
1answer
3k views

Using Fermat's little theorem to find remainders. [duplicate]

I don't understand how to use Fermat's little theorem to find remainders e.g if we are asked to find remainder of 50^50 on division by 13, what is a and what is p in the formula? What is going on?? ...
0
votes
1answer
153 views

7-adic series expansion of square root of 2

Given the sequence $\{ a_n\}$ defined by the (positive and $a_n < 7^n$) solutions of the congruence $x^2 \equiv 2 \mod 7^n$ and $a_{n+1}\equiv a_n \mod 7^n$. e.g. the first one is $a_1 =3$ the ...
2
votes
0answers
201 views

The logarithm of a product

Let $p$ be a prime number, $C\in \mathbb{N}$ and C is not a square. Then define $$F=\prod_{|z| \leq \sqrt{\frac{x}{2}} \atop |y|\leq \sqrt{\frac{x}{2D}}}{|z^2-Cy^2|}.$$ Note that we omit the term with ...
0
votes
2answers
340 views

Numbers in a list which are perfect squares and perfect cubes of numbers

How many numbers in the list $$1,2,3,...,2001$$ are perfect squares and perfect cubes of whole numbers? My progress: Well I do know $$1,4,9,16,25,36,...$$ are perfect squares and $$1,8,27,64,...$$ ...
0
votes
2answers
56 views

Perfect Square and Multiple question

The population of a village is a perfect square. Later, with an increase of 100, the population was 1 more than a perfect square. Now with an additional increase of 100, the population is again a ...
2
votes
1answer
44 views

If $(ord_m(a), ord_m(b)) = 1$ prove that $ord_m(ab) = ord_m(a)*ord_m(b) $

$\DeclareMathOperator\ord{ord}$Let $a, b$, and $m$ be positive integers such that $(a,m) = (b,m) = 1$. Assume that $(\ord_m(a), \ord_m(b)) = 1$. Prove that $\ord_m(ab) = \ord_m(a)*\ord_m(b)$. So ...
6
votes
2answers
157 views

$1+n!=m^{2}$ for some n,m$\in\mathbb{N}$ [duplicate]

I have no idea whether this is known or not and I couldn't find anything related on Google. While I was studying , I come up with this idea $1+n!=m^{2} $ for some $n,m\in\mathbb{N}$ $1+4!=5^{2}$ ...
2
votes
3answers
68 views

prove that if $a$ is not a unit in $\mathbb Z$/m$\mathbb Z$ then $a$ is a zero divisor in $\mathbb Z$/m$\mathbb Z$?

Ho can I prove that if $a$ is not a unit in $\mathbb Z$/m$\mathbb Z$ then $a$ is a zero divisor in $\mathbb Z$/m$\mathbb Z$ ? I am stuck on this problem I would appreciate a lot your help thanks!!
0
votes
1answer
70 views

Digit reversal arithmetic

How many three-digit odd numbers become bigger when their digits are reversed? $$abc<cba$$ and $c$ is either 1,3,5,7,9. This is the furthest I managed to reach.
1
vote
2answers
87 views

Three-Digit numbers divisbile by 3

How many three digit numbers are divisible by 3 and have an additional property that the sum of of their digits is 4 times the middle digit? My approach: let the number be $abc$ so $$abc \equiv ...
3
votes
2answers
101 views

Conjecture on twin primes

Let $p$ and $p+2$ be both prime. I conjectured (with my ignorance) that $$p^{\frac{p+1}{2}}\equiv -1\mod{(p+2)}$$ except for $p=17,41,71,137, 191, 239....$ I verified this on Mathematica. So for ...
2
votes
1answer
95 views

Good introduction to number theory that develops and/or makes heavy use of commutative ring theory and lattice theory?

I'd like to learn some number theory, since it provides a lot of motivation for commutative ring theory and even some motivation for lattice theory (at least, that's the impression I'm under). ...
1
vote
1answer
430 views

Last two digit of number raised to exponents. [duplicate]

Find the last two digits of $3^{3^{2014}}$. Attempt: First I try to work with $3^{2014}$. So we can work on $\text{mod 10}$. Then, $$\begin{align}&3^1 \equiv 3\pmod{10}\\ &3^2 \equiv 9 ...
0
votes
1answer
42 views

Using Fermat's Little theorem to prove that $12\mid n^2-1$ when $(n,6)=1$

I need help proving the first one via Fermat's little theorem. I need a hint, or a good starter!
1
vote
2answers
61 views

Median primes and cryptography

I've been considering something involving median numbers. If an integer is directly in the middle of two integers, is it possible to accurately extrapolate what two it is between? Can a prime be in ...
3
votes
3answers
208 views

How can you proof that the sum of three roots is irrational?

I would like to know how to prove that $\sqrt{2} + \sqrt{5} + \sqrt{7}$ is an irrational number. I know how to do the proof for a sum of two roots. Can I just define $\sqrt{2} + \sqrt{5} :=c$ and then ...
0
votes
0answers
23 views

Geographic representation of summations and floors

I am struggling to write this proof, and cannot figure out how to view this "geometrically:" Let $a$, $b\in\mathbb{N}$ be odd and relatively prime. Show that $$ ...
3
votes
1answer
109 views

Any rational as integer plus sum of $n$ reciprocals

Does there exist an integer $n$ with the following property? For any rational number $r$, there exist integers $a,b_1,\ldots,b_n$ such that $r=a+\sum_{i=1}^n\frac1{b_i}$.
1
vote
1answer
83 views

Prove something is divisible by a prime

Let $p$ be a prime. Prove that $\sum_{k=j}^{p-1} \frac{k!}{ j! (k-j)! }$ is divisible by $p$ $\forall$ $j \in \{0, ..., p-2\}$. Where this problem comes from: I am trying to prove that ...
0
votes
1answer
70 views

Help on a perfect square.

Consider a question, that xyxyxyxy cannot be a perfect square. How should i tackle this problem. All i use is it must be $0,1 ($mod $3,4)$ and then the math, are there any another beatiful ways ...
0
votes
3answers
68 views

Division with remainder (Pos/Neg & Neg/Pos)

I guess it is a elementary school question, however I could not be sure: What are the remainders when: $-8$ is divided by $3$ $8$ is divided by $-3$ According to: $0<r<n$ where $m=qn+r$ ...
4
votes
2answers
125 views

Is this proof rigorus?

Simple abstract algebra proof: Suppose that $a,b,c\in\mathbb{Z}$ with $a$ and $b$ relatively prime. If $a|bc$, then $a|c$. Proof 1 Since $a$ & $b$ relatively prime, $a|bc\Rightarrow a|c$ ...
1
vote
1answer
65 views

Sum of Digit squares

I like to create problems for myself, While playing with my calculator, I found the following result. Take any positive digit $a_0$, and let $a_n$ denote the sum of digit squares of $a_{n-1}$. Then ...
3
votes
1answer
81 views

An easy question on number theory

Let $p$ be an odd prime. Is there any positive integer $k>1$ such that $p^k-1$ be a power of 2, that is $p^k-1=2^{\alpha}$ for some $\alpha\in \mathbb{N}$?
3
votes
2answers
2k views

Last digits, numbers

Can anyone please help me? 1) Find the last digit of $7^{12345}$ 2) Find the last 2 digits of $3^{3^{2014}}$. Attempt: 1) By just setting the powers of $7$ we have $7^1 = 7$, $7^2=49$, $7^3=343$, ...
1
vote
3answers
83 views

Find $m$ such that $4 \nmid \phi(m)$

The above question is taken from Silvermans A Friendly Introduction to Number Theory, volume 3. Here's what I've got so far: I know that $$\phi(m) = \prod_{p|m} (p^{k-1})(p-1)$$ and I tried several ...
2
votes
2answers
237 views

Prove that every positive integer $n$ has a unique expression of the form: $2^{r}m$ where $r\ge 0$ and $m$ is an odd positive integer

Prove that every positive integer $n$ has a unique expression of the form: $2^{r}m$ where $r\ge 0$ and $m$ is an odd positive integer if $n$ is odd then $n=2^{0}n$, but I dont know what to do when ...
0
votes
3answers
78 views

mutliplicative inverse

Let a = 216, M = 342865. Show that gcd(a,M) = 1. Hence find the mutliplicative inverse, a^-1 mod M. I don't really know what to seach up for this question, but if anyone can provide me a example of ...
2
votes
5answers
714 views

prove that $3$ does not divide $n^2+1$ [duplicate]

How do I prove that $3$ does not divide $n^2+1$, for all $n\in\mathbb{Z}$, thought of in separate cases, but did not get, induction also was unable to ....
1
vote
0answers
40 views

Definition of Euler phi function

Why is $\phi(n)$ defined to be $$\phi(n) = |\{ 0 \le b < n \mid gcd(b,n) = 1 \}|$$ rather than $$\phi(n) = |\{ 0 < b < n \mid gcd(b,n) = 1 \}|$$ ? I realize it doesn't make a practical ...
1
vote
2answers
112 views

Dice-Game with two-twenty sided dice.

EDIT: I'll give this another try, trying to be clearer. The game is played like this: Player A roles two-twenty-sided dice and multiplies the two integers together to get some integer, say x, with $ ...
1
vote
2answers
331 views

How to use Fermat's little theorem to find $50^{50}\pmod{13}$?

I don't understand how to use Fermat's little theorem to find remainders e.g if we are asked to find remainder of $50^{50}$ on division by $13$, what is a and what is $p$ in the formula? Also I ...
3
votes
5answers
129 views

$\sqrt[3]{2}$ is not the root of a quadratic with rational coefficients?

How can one show that $\sqrt[3]{2}$ is not a root of a quadratic with rational coefficients? It is clear that if $\sqrt[3]{2}$ is the root of such a quadratic, then it is also the root of a quadratic ...
3
votes
2answers
119 views

Almost perfect numbers

A positive integer $n$ is called almost perfect if the sum of its divisors smaller than $n$ is $n-1$. What are all almost perfect numbers $n$ such that some power $n^k$ is also almost perfect for at ...
4
votes
2answers
92 views

Squares modulo 2^n

How many squares are there modulo $2^n$? If we would deal with $p^n$, where p an odd prime, then we could use Hensel's Lemma, which clearly doesn't work with $2^n$.
2
votes
1answer
62 views

How do i prove this is a metric?

Define a metric $d$ on $\mathbb{Z}$ in the following manner: $d(x,y)=\min\{\frac{1}{n!} : n! \text{ divides } x-y \text{ where } n\in\mathbb{Z}^+ \}$ if $x\neq y$. $d(x,x)=0$ ...
1
vote
3answers
87 views

Prove that $7^{100}+3^{10}=8^{100}$ or $7^{100}+3^{10}<8^{100}$ [closed]

Prove that $7^{100}+3^{10}=8^{100}$ or $7^{100}+3^{10}<8^{100}$ I tried using some theorems of divisibility, to show that one divides the other, and the other also divides the first, but could ...
1
vote
3answers
81 views

Number of quadractic residues $\mod p$ and $\mod n$.

Let $p$ be an odd prime. Then among the integers $\{1,2,3,\cdots,p-1\}$ exactly half are quadratic residues modulo $p$. I believe the above proposition. Let $n$ be an odd, square free ...
2
votes
0answers
75 views

Question on Fermat Numbers Factorization

Let $F_{n}=2^{2^n}+1$ be a Fermat number. A classic idea using orders and Fermat's Little Theorem shows that a prime divisor $p$ of $F_{n}$ must be of the form $p=k .2^{n+1}+1$. Furthermore, using the ...
1
vote
2answers
72 views

Interesting numbers

I was doing some math problems when I came across some interesting numbers such as: $1^3+5^3+3^3=153$ $4^3+0^3+7^3=407$ $3^3+7^3+0^3=370$ $3^3+7^3+1^3=371$ $8^4+2^4+0^4+8^4=8208$ My question is: ...
-1
votes
2answers
97 views

Showing that $x^{11} \equiv 5 \pmod{47}$ has only solution $x \equiv 15$.

I don't understand the proof. Where did they get the first line from, i.e., $21 \times 11=1+5 \times 46$? Fermat's theorem in my view is $a^{46} \equiv 1 \pmod {47}$.
1
vote
1answer
77 views

Why doesn't SAGE understand reduced expressions mod p in a finite field extension?

Suppose I have a finite field $\mathbb{F}_{13}$ and I would like to adjoin an element, $\zeta$, with order $3$, since $\mathbb{F}_{13}$ does not contain one. So consider $\mathbb{F}_{13}(\zeta)$. Then ...
2
votes
1answer
719 views

Prove $\gcd(ka,kb) = k*\gcd(a,b)$ [duplicate]

For all $k > 0,\ k\in \Bbb Z$ . Prove $$\gcd(k*a,\ k*b) = k *\gcd(a,\ b)$$ I think I understand what this wants but I can't figure out how to set up a formal proof. These are the guidelines we ...
1
vote
3answers
72 views

system of linear congruences

How can I solve this system of linear congruences? $$2x\equiv 0\, \text{mod 3}\\ 3x\equiv 2\, \text{mod 5}\\ 5x\equiv 4\, \text{mod 7}$$ I don´t know where to start, I am having a lot of troubles, ...
-1
votes
2answers
63 views

prove: (a|b*c) ^ (gcd(a,b)=1) implies a|c [duplicate]

i need help with the following prove: (a|bc) ^ (gcd(a,b)=1) implies a|c following these writing guidelines http://i.imgur.com/qpIYqPp.png What I know so far: By the Euclidean algorithm there are ...